[정수론] 유클리드 호제법

✔ 유클리드 호제법

유클리드 호제법이란?

• 두 수의 최대 공약수를 구하는 알고리즘

최대 공약수와 최소 공배수

• 최대 공약수(GCD)란 두 자연수의 공통된 약수 중 가장 큰 수
• 최소 공배수(LCM)란 두 자연수의 공통된 배수 중 가장 작은 수
• 최소 공배수는 두 자연수의 곱 / 최대 공약수

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

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

✔ 확장 유클리드 호제법

확장 유클리드 호제법이란?

• 방정식 ax + by = c의 해를 구하는 알고리즘 (a, b, c, x, y는 정수)
• 이 때 위 방정식은 c % gcd(a, b) = 0인 경우에만 정수해를 가지게 됨
  • 즉, c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가지게 됨
  • 그러므로 ax + by = c가 정수해를 갖게 하는 c의 최솟값은 gcd(a, b)

확장 유클리드 호제법의 원리

1. ax + by가 정수해를 갖게 하는 c의 최솟값이 gcd(a, b)라는 것을 적용하여 식을 다시 놓음
   • gcd(a, b) = d이므로 ax + by = d로 식을 다시 놓고 다음 단계를 진행
2. a, b로 유클리드 호제법을 반복 실행하며 몫, 나머지를 저장함
   • 반복은 나머지가 0이 되면 중단
3. 반복으로 구한 나머지와 몫을 이용하여 거꾸로 올라가며 x = y', y = x' - y' * q를 계산함
   이때 처음 시작하는 x, y는 이전 x와 이전 y가 없으므로 각각 1, 0으로 지정하여 역계산을 진행함
   
   • x'는 이전 x
   • y'는 이전 y
   • q는 현재 보고 있는 몫
4. 재귀 방식으로 알아낸 최종 x, y는 ax + by = gcd(a, b)를 만족하므로
   c / gcd(a, b) = K를 가정하면 최초 방정식의 해는 Kx, Ky로 구해지게 됨

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn