확장 유클리드 호제법의 재귀적 구현

https://rebro.kr/97 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..

원문링크 : 확장 유클리드 호제법의 재귀적 구현