1. 나눗셈 관계식 (Division Relation)
ㅇ 4개 항(a,b,q,r) 사이의 나눗셈 관계식은,
- a = q x b + r 또는 a / b = q + r / b (0 ≤ r ＜ b)
ㅇ 위 관계식에서, 항들 간의 관계 및 명칭은,
- 피제수(dividend,나눠지는 수) a 를 제수(divisor,나누는 수) b 로 나눌 때,
- 몫(quotient)을 q, 나머지/잉여(remainder,residue)를 r 이라고 함 ☞ 잉여류 참조
- 이때, 2개 입력과 2개 출력을 갖음 (입력 : a,b, 출력 : q,r)
2. 정수의 나눗셈 정리 또는 나눗셈 알고리즘 (Division Algorithm)
※ 두 정수 사이에서 몫 또는 나머지의 존재성/유일성 정리 또는 몫을 구하는 알고리즘
- 비록, 여기서 알고리즘이라는 표현은 다소 부적절하지만, 관례로써 호칭됨
- 그 이유는, 최대공약수를 빠르게 구하는 유클리드 알고리즘과의 연계성 때문임
ㅇ 어떤 정수 a를 또다른 정수 b로 나누었을 때, 그 몫 q 및 나머지 r는 `유일하게 존재함`
- a = q x b + r (0 ≤ r ＜ b)
. 피제수 a, 제수 b가 주어질 때,
. 몫 q, 나머지 r의 존재성 및 유일성 정리
- 例1) -5 = 2 x (-2) + (-1) (X, ∵ 나머지가 음수)
- 例2) -5 = 2 x (-3) + 1 (O)
3. 나눗셈 정리의 응용
※ ☞ 유클리드 알고리즘(유클리드 호제법) 참조
- 두 정수의 최대공약수를 빠르게 계산해내는 알고리즘