유클리드 호제법(Euclidean algorithm)?

참조

https://ko.wikipedia.org/wiki/유클리드_호제법

유클리드 호제법

유클리드 알고리즘은 두 자연수의 최대공약수를 구하는 알고리즘의 하나이다.
호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 의마한다.
2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
a : kx
b : ky
k : 최대공약수
r : a%b = kx%ky = x%y

a = bq + r
kx = kyq + r
-> x과 yq는 서로소

r = k(x - yq) = kp
-> 나머지인 r 또한 k의 배수

kx = k(yq + p)
x = yq + p
p = x - yq
-> x와 yq는 서로소이므로 1 이외에 공약수가 존재하지 않는다.

따라서 나머지 r은 x와 yq에 대하여 서로소이다.

그러므로, a와 b의 최대공약수는 k인 것과 같이 b와 r의 최대 공약수도 k이다.