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