PS를 위한 정수론 - (2) 유클리드, 확장 유클리드 호제법
[목차] 1. 유클리드 호제법 2. 확장 유클리드 호제법 3. 모듈러(modular) 연산에서의 곱셈의 역원 4. 예시 문제 1. 유클리드 호제법 유클리드 호제법은 정수론을 조금이라도 공부했다면, 혹은 공부하
rebro.kr
오랜만에 확장 유클리드가 필요해서 내용을 찾아봤는데, 위의 블로그의 코드를 찾게 되었다.
블로그 설명에서는 해당 코드를 완벽히 설명한거 같진 않아서 정리해 본다.
재귀적으로 작성하였는데, 그 부분을 설명해 보자면,
\[gcd(a, b)=sb+t(a \% b)\]
를 만족한다고 두고,
\[a\%b=a-(a/b)b\]
를 대입하면
\[gcd(a,b)=ta+\left\{s-t\left(a/b\right)\right\}b\]
코드에서 제시하는 식이 얻어짐을 확인할 수 있다.
이를 반복하도록 잘 구현한 것이 위의 블로그의 코드이다.
옛날에 KMO 정수론 공부할 때 이런 식으로 배운거 같은데 다 까먹어서 지금이라도 정리해 둔다.
