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

*이 글에서는 두 수의 최대공약수만 다룹니다.* 최대공약수 중학교 때 배우는 개념인 최대공약수는 인수분해를 통해 구할 수 있다. 하지만 큰 수, 예를 들어 5778, 543이 주어진다면 인수분해부터가 막막할 것이다. 이런 문제를 쉽게 해결하기 위한 알고리즘이 바로 유클리드 호제법이다. 호제법을 알기 전에 먼저 최대공약수란 무엇인지 더 자세히 알아보자! (넘어가도 되는 부분입니다.) "a와 b를 동시에 나누는 양의 정수 d가 있다. 이 때 d 처럼 a와 b를 동시에 나누는 모든 c 들은 d를 나눈다" 쉽게 말하면 "a와 b를 나누는 수들 중에 가장 큰 수 d가 최대공약수이고, 나머지 수들이 d를 나눈다" 라고 볼 수 있다. 정수론 책에서는 gcd의 존재성과 유일성까지 증명하지만 생략한다. 유클리드 호제법 먼저 정의는 다음과 같다. 즉 정수 a와 b의 최대공약수는 b와 a를 b로 나눈 나머지 r의 최대 공약수이다. 유클리드 호제법을 통해 큰 수인 a와 b를 계속해서 작은 수로 줄여나...

원문링크 : 유클리드 호제법과 확장된 유클리드 호제법