유클리드 호제법 이론 (최대 공약수 구하기)

원리

즉, a, b의 최대공약수와 b, r의 최대공약수가 같음을 이용해서 최대공약수를 빠르게 구하는 방법이다.

예를들어

78696과 19332의 최대 공약수를 구하고자 한다면

78696 = 19332 * 4 + 1368

19332 = 1368 * 14 + 180

1368 = 180 * 7 + 108

180 = 108 * 1 + 72

108 = 72 * 1 + 36

72 = 36 * 2 + 0

최대공약수가 36가 된다

위의 예시를 보면 알겠지만

a와 b의 최대 공약수를 구할때

a에다가 b를 나눈 몫에 나머지를 나누는것을

나머지가 0이 될때 까지 반복하면 된다.

확장된 유클리드 호제법과 코드

[확장된 유클리드 호제법 (gcd)

이전의 유클리드 호제법으로 최대공약수를 구하는법을 알았다 유클리드 호제법 이론 (최대 공약수 구하기) 즉, a, b의 최대공약수와 b, r의 최대공약수가 같음을 이용해서 최대공약수를 빠르게

fullfish.tistory.com](https://fullfish.tistory.com/130)