Division Relation, Equality in Division, Reminder, Residue, Euclidean Algorithm   나눗셈 관계식, 나눗셈 정리, 나머지(Reminder), 잉여(剩餘), 유클리드 알고리즘

(2016-08-31)
1. 나눗셈 관계식 (Division Relation)

  ㅇ 피제수(dividend) a 를 제수(divisor) b 로 나눌 때,
     -  몫(quotient)을 q, 나머지/잉여(remainder,residue)를 r 이라 하면, 

  ㅇ 4개 항(a,b,q,r) 사이의 나눗셈 관계식
     -  a = q x b + r  또는  a / b = q + r / b   (0 ≤ r < b)


2. 정수의 나눗셈 정리/알고리즘 (Division algorithm)

  ※ 비록, 여기서 알고리즘이라는 표현은 부적절하지만, 관례로 호칭됨

  ㅇ 어떤 정수를 또다른 정수로 나누었을 때, 그 몫 q 및 나머지 r는 유일하게 존재함
     -  a = q x b + r  (0 ≤ r < b)
        .  몫 q, 나머지 r의 존재성 및 유일성 정리

     - 例) -5 = 2 * (-2) + (-1)  (X, ∵ 나머지가 음수),  -5 = 2 * (-3) + 1  (O)


3. 유클리드 호제법/알고리즘 (Euclidean Algorithm)

  ㅇ 두 정수의 최대공약수를 빠르게 계산해내는 알고리즘
     
ㅇ 입력 : r[0], r[1]
ㅇ 출력 : gcd ( r[0], r[1] )

Euclidean ( r[0], r[1] ) {
    초기화 : i = 1 ;
    while ( r[i] ≠ 0 ) {
       r[i] = r[i-2] mod r[i-1] ; 
    }
    return gcd ( r[0], r[1] ) = r[i-1]
}
ㅇ 例) gcd(21,9) → a = 21, b = 9 - a = b x q + r - 21 = 9 x 2 + 3 → b = 9, r = 3 - 9 = 3 x 3 + 0 → b = 3, r = 0 - 따라서, gcd(21,9) = 3


[나눗셈(가분성)]1. 약수,배수  2. 나눗셈 관계식  3. 잉여류,잉여계  

 
        최근수정     모바일웹     참고문헌