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

(2022-07-03)

Remainder, Residue, 나머지 , 나머지 (Reminder), 잉여 (剩餘)


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

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



Copyrightⓒ written by 차재복 (Cha Jae Bok)
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"