[D-17] 유클리드 호제법 & MOD 연산

📍 유클리드 호제법

✅ 정의

유클리드 호제법(euclidean-algorithm)은 두 수의 최대 공약수(gcd)를 구하는 알고리즘이다.
소인수분해보다 간단한 방법이다.

• 소인수분해 : 공통된 소수들의 곱으로 최대 공약수를 구하는 방법
• 최대공약수 : GCD(Greatest Common Divisor)

✅ 핵심 이론

유클리드 호제법을 수행하려면 먼저 MOD 연산을 이해하고 있어야 한다.
MOD 연산이 최대 공약수를 구하는 데 사용하는 핵심 연산이기 때문이다.

✅ MOD 연산

모듈러 연산이란, 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산을 말한다.
예를 들어, 두 정수 A, B에 대하여 A를 B로 나누어 나머지가 C가 나왔다면
"A mod B = C" 또는 "A % B = C"라고 표현할 수 있다.

✔️ 참고 : Khan Acdemy, 모듈러 연산이란?
✔️ 참고 : gliver, 나머지 연산

✅ MOD 연산으로 구현하는 유클리드 호제법

1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
2. 앞 단계에서의 작은 수와 MOD 연산 결과값(나머지)으로 MOD 연산을 수행한다.
3. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.
   

📍 확장 유클리드 호제법

✅ 정의

방정식의 해를 구하는 것이다.
해를 구하고자 하는 방정식은 다음과 같다.
ax + by = c (a, b, c, x, y는 정수)

✅ 핵심 이론

c % gcd(a,b) = 0인 경우에만 정수해를 가진다.
구현에는 재귀 함수를 사용한다.