두 수의 최대공약수는 유클리드 호제법

유클리드 호제법은 다음과 같이 정리할 수 있습니다.

 

정수 X와 Y(X>=Y)가 주어졌을 때 X를 Y로 나눈 나머지를 R이라고 하면, X와 Y의 최대공약수는 Y와 R의 최대공약수와 같다. 그러나 X와 0이 남았을 경우 최대공약수는 X로 한다.

 

이를 활용해서 126과 90의 최대 공약수를 구해보자

 

126(X)와 90(Y)의 나머지 값은 36(R),

90(X) 와 36(Y) 의 나머지 값은 18 (R) ,

36(X) 와 18(Y) 의 나머지 값은 0 (R)

따라서 126과 90의 최대공약수는 18이 된다.

 

참고도서 : 그림으로 배우는 알고리즘 basic - 스기우라 켄