[Math/Theory of number] GCD의 증명

정수론

기반 지식

• 소수 : 약수가 1 또는 자기 자신인 수
• 서로소 : 두 정수의 공약수가 1
• 약수와 배수 : a*b = c -> a|c, b|c 로 나타냄, a의 배수인 c, b의 배수인 c 정도로 보면 될 듯
• 공배수 : a|b c|b라면 b는 a, b의 공배수가 됨
• 공약수 : a|b a|c라면 a는 b, c의 공약수가 됨

서론

• 정리 1
  
  • m, n, c가 정수일 때
  • c가 만약 m, n의 공약수이면 c|(m+n), c|(m-n)가 성립함
  • c|m 이면 c|m*n임
• 정리 2
  
  • 두 정수 a, b가 있을 때, a = b*q + r이면 gcd(a,b) == gcd(b,r)이다.
  • 증명
    c를 a, b의 공약수로하고 했을 때
    c|b*q 는 성립
    c|a와 c|b*q가 성립하니, 정리에 의해 c는 b, r의 공약수 (왜냐하면, b*q=a-r이기 떄문에 c|a, c|a-r(=b*q)가 된다는 건 증명되어 c|r또한 성립
    반대로 c|r, c|b이면 c|b*q, c|b*q+r이 성립
    즉, c는 a, b의 공약수임(= 위 정리에 의해 c|a, c|b 이면 c|b, c|r)
    그러므로 a, b의 공약수의 집합은 b, r의 공약수와 같음
    gcd(a,b) == gcd(b,r)

유클리드 알고리즘

• 정리 2에 근거해서 gcd를 빠르게 찾는 알고리즘
• a = b*q + r 인경우
• gcd(a, b) == gcd(b, a mod b)

• 예
  gcd(385, 175)
  gcd(175, 35)
  gcd(35, 0)
  = 35

• 의사코드

while(b > 0) {

}

return a;