Division Relation, Equality in Division   나눗셈 관계식, 나눗셈 정리

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. 나눗셈 정리의 응용

  ※ ☞ 유클리드 알고리즘(유클리드 호제법) 참조
     - 두 정수의 최대공약수를 빠르게 계산해내는 알고리즘