유클리드 알고리즘은 공약수를 보존하는 더 작은 쌍으로 두 비음수 정수를 반복해서 바꾸어 가며 최대공약수(gcd)를 구하는 방법이다.
핵심 항등식
$b>0$인 비음수 정수 $a,b$를 생각하자. 유클리드 나눗셈에 따라 다음을 만족하는 정수 $q,r$가 유일하게 존재한다.
\[a=bq+r,\qquad 0\le r<b.\]핵심은 다음 항등식이다.
\[\gcd(a,b)=\gcd(b,r).\]이를 증명하기 위해 두 쌍의 공약수를 비교하자. 정수 $d$가 $a$와 $b$를 모두 나누면, $a-bq=r$도 나누므로 $b$와 $r$도 모두 나눈다. 반대로 $d$가 $b$와 $r$을 모두 나누면 $bq+r=a$를 나누므로 $a$와 $b$도 모두 나눈다. 따라서 $(a,b)$의 공약수 집합과 $(b,r)$의 공약수 집합은 정확히 같고, 특히 최대공약수도 같다.
반복 적용
$r>0$이면 $(b,r)$에 같은 항등식을 다시 적용한다. 각 나머지는 직전의 제수보다 작은 비음수 정수이므로, 나머지는 엄격히 감소하다가 결국 0이 된다. 예를 들면,
\[252=105\cdot2+42,\qquad 105=42\cdot2+21,\qquad 42=21\cdot2+0.\]따라서
\[\gcd(252,105)=\gcd(105,42)=\gcd(42,21)=\gcd(21,0)=21.\]비음수 정수 $a$에 대해 종료 단계는 $\gcd(a,0)=a$이다. 모든 비음수 정수는 0을 나누며, $a$와 0의 최대 비음수 공약수는 $a$이기 때문이다. 이에 따라 관례적으로 $\gcd(0,0)=0$으로 둔다. 따라서 처음 입력의 $b$가 0이어도 바로 처리할 수 있다.
반복형 C++ 구현
다음 함수는 비음수 int 값만 받는다. 두 인수가 모두 비음수이고 int로 표현 가능하다는 것이 전제 조건이며, $\gcd(0,0)=0$을 포함해 최대공약수를 반환한다.
1
2
3
4
5
6
7
8
9
int gcd(int a, int b) {
// 전제 조건: a >= 0, b >= 0.
while (b != 0) {
int remainder = a % b;
a = b;
b = remainder;
}
return a;
}
각 반복에서 remainder는 $a=bq+r$의 $r$에 해당하므로, 쌍이 $(b,r)$로 바뀌어도 $\gcd(a,b)$는 변하지 않는다. b가 0이 되면 a가 최대공약수다.