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. 잉여류,잉여계
  1.   기술공통
  2.   기초과학
        1. 과학
    1.   수학
      1.   기초수학
      2.   집합,논리
      3.   정수론(수론)
            1. 정수론
            2. 절대값
            3. 짝수,홀수,패리티
        1.   수의 구분
        2.   셈법(Counting)
        3.   나눗셈(가분성)
          1.   1. 약수,배수
              2. 나눗셈 관계식
              3. 잉여류,잉여계
        4.   디오판투스 방정식
        5.   소수,최대공약수
        6.   합동
      4.   해석학(미적분 등)
      5.   대수학
      6.   확률/통계
      7.   수치해법
    2.   물리/화학
    3.   지구,천체 과학
    4.   생명과학
  3.   파동/광학/음향
  4.   방송/멀티미디어/정보이론
  5.   전자/전기/제어
  6.   통신/네트워킹
  7.   정보기술(IT)
  8.   기계/재료/공업일반
  9.   표준/계측/품질
  10.   기술경영

 
        최근수정     참고문헌