유클리드 호제법은 두 정수의 최대공약수(GCD: Greatest Common Divisor)를 구하는 방법입니다. 큰 수와 작은 수를 반복적으로 나눗셈하면서 나머지를 이용해 최대공약수를 찾는 방식입니다. 이 알고리즘은 오랜 역사를 지닌 만큼 단순하면서도 매우 효율적입니다.
두 수 a와 b (a>b)의 최대공약수 gcd(a,b)는 다음과 같이 정의됩니다: gcd(a,b)=gcd(b,amodb)
aa
bb
a>ba > b
gcd(a,b)gcd(a, b)
gcd(a,b)=gcd(b,a b)gcd(a, b) = gcd(b, a \bmod b)
이 과정을 나머지( \bmodmod)가 0이 될 때까지 반복합니다. 마지막에 나머지가 0이 되기 직전의 값이 최대공약수입니다.
572÷209=2572 \div 209 = 2572÷209=2 (몫), 나머지: 572mod209=154
572 209=154572 \bmod 209 = 154
209÷154=1209 \div 154 = 1209÷154=1 (몫), 나머지: 209mod154=55
209 154=55209 \bmod 154 = 55
154÷55=2154 \div 55 = 2154÷55=2 (몫), 나머지: 154mod55=44
154 55=44154 \bmod 55 = 44
55÷44=155 \div 44 = 155÷44=1 (몫), 나머지: 55mod44=11
55 44=1155 \bmod 44 = 11
44÷11=444 \div 11 = 444÷11=4 (몫), 나머지: 44mod11=0
44 11=044 \bmod 11 = 0
따라서, gcd(209,572)=11gcd(209, 572) = 11gcd(209,572)=11입니다.
분수의 약분: 분수를 가장 간단한 형태로 만들기 위해 사용합니다.
확장 유클리드 호제법: ax+by=gcd(a,b) 형태의 디오판토스 방정식의 해를 찾을 때 사용됩니다.
ax+by=gcd(a,b)ax + by = gcd(a, b)
RSA 암호화: 암호화 키 생성 시 두 수의 최대공약수를 계산하여 소수를 찾고, 서로소인 수를 판별할 때 활용됩니다.
에라토스테네스의 체는 주어진 범위 내의 소수를 효율적으로 찾는 방법입니다. 고대 그리스 수학자 에라토스테네스가 고안한 이 알고리즘은 단순한 배수 제거 방식으로 작동합니다.