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. 나눗셈 정리의 응용
※ ☞ 유클리드 알고리즘(유클리드 호제법) 참조
- 두 정수의 최대공약수를 빠르게 계산해내는 알고리즘