[정수론](3)[가약성과 최대공약수]

용어
    a|b: a가 b를 나눈다 = a는 b의 약수다
    공약수: 두 수를 모두 나누는 수
        즉, d|a, d|b인 d는 a와 b의 공약수
    최대공약수: 공약수 중 가장 큰 수
예전에 공약수를 구할 때는 오로지 자연수 범위에서 했지만, 이제는 정수 범위에서 구할 수 있다.
예) 12, 18의 공약수는?
    (자연수 범위): 2, 3, 6
    (정수 범위): -2, -3, -6, 2, 3, 6

 

 

gcd(a, b): a와 b의 최대공약수

    예) gcd(12, 18) = 6
    gcd(0, k) = k
    gcd(0, 0) = ? (정의 안함)
    gcd(m, n) = 1 <- m, n이 서로소

 

 

유클리드 호제법: gcd 빠르게 구하기

예) gcd(36, 132)
    132 = 36 * 3 + 24
    36 = 24 * 1 + 12
    24 = 12 * 2 + 0
    따라서, gcd(36, 132) = 12

• 증명
  gcd(a, b), (a>b라 가정)에서 유클리드 호제법을 적용하면,
  a = b*q1+r1
  b = r1*q2+r2
  r1= r2*q3+r3
  ...
  r(n-3) = r(n-2)*q(n-1)+r(n-1)
  r(n-2) = r(n-1)*q(n)+r(n)
  r(n-1) = r(n)*q(n+1)+0
  추측: r(n) = gcd(a, b)이다.
  • 공약수 증명
    r(n-1) = r(n)*q(n+1)
    따라서 r(n)|r(n-1)
    r(n-2) = r(n-1)*q(n)+r(n) = r(n)*q(n+1)*q(n)+r(n) = r(n){q(n+1)q(n)+1}
    따라서 r(n)|r(n-2)
    이걸 계속 반복한다면 r(n)|b, r(n)|a이므로, r(n)은 a, b의 공약수가 된다.
  • 최대공약수 증명
    a, b의 공약수 d가 있을때,
    임의의 약수 d는 d|r(n)이므로 r(n)은 최대공약수