[알고리즘] 유클리드 호제법, 간단하게 증명하기

안녕하세요, 

모처럼 맑은 날씨의 모스크바에서 겨울을 지내고 있는 개발자 윤진입니다.

알고리즘 책을 뒤적거리다가 유클리드 호제법을 이용하여 최대공약수를 구하는 코드를 읽었습니다.

호제법 자체가 워낙 깔끔한 공식인지라 코드도 군더더기가 없더군요.

학창시절때 호제법을 증명했었던 기억이 나는데요,

문득 다시 증명을 도출하고 싶어 기억을 더듬고자 합니다.

호제법 증명법에서 가장 재미난 국면은 2군데입니다.

처음은 나머지값의 공약수를 구하는 곳이죠.

그리고 두번째는,

나머지의 공약수가 최대공약수인 것을 귀류법으로 도출해내는 국면입니다.

비록, 코드는 없지만,

이런 깔끔한 알고리즘은 경이롭네요. :)