확장 유클리드 알고리즘

두 정수 n, m 이 있을때, nx+my=gcd(n,m) 을 만족시키는 정수 x와 y가 반드시 존재한다

정수 x와 y에 대해서 nx+my=d 를 만족시키는 정수 d는 항상 gcd(n,m)의 배수이다.

nx+my=c 라는 부정방정식이 있을때, c가 gcd(n,m)의 배수가 아니라면 x,y의 정수해가 존재하지 않는다

(x0, y0)가 nx+my=d 의 하나의 해일때, 일반해는 (x0 + k*m/gcd(n,m), y0 - k*n/gcd(n,m)) 이 된다.

확장 유클리드 알고리즘을 통해서 gcd(n,m)과 nx+my=gcd(n,m)를 만족시키는 x0, y0 를 구한다

c % gcd(n,m) != 0이면 해가 없다. 그렇지 않으면 x0*c/gcd(n,m), y0*c/gcd(n,m) 이 nx+my=c 의 해가 된다

일반해는 (x0*c+k*m)/gcd(n,m), (y0*c-k*n)/gcd(n,m) 이 된다

a의 m에 대한 모듈러 역원 x는 a*x % m = 1 을 만족하는 x이다

이걸 다시 쓰면 ax-my = 1 이 된다. 즉, gcd(a,m)이 1보다 크면 역원이 없고, 서로소라면 a,m에 대해서 확장 유클리드 알고리즘을 돌리면 x값을 찾을수 있다.

nx+my=gcd(n,m)를 만족하는 정수 x0,y0을 찾는다고 하자.

먼저 math.gcd를 이용해서 gcd(n,m) = g 를 계산하자

양변을 g로 나눠서 (n/g)x + (m/g)y = 1 로 만들고 이항하면, (n/g)*x ≡ 1 mod (m/g) 가 되므로 x=pow(n/g, -1, m/g)로 계산할수 있다. y도 마찬가지로 y=pow(m/g, -1, n/g) 으로 계산하면 된다.

gcd를 먼저 구하고 역원을 다시 구해야 하므로 속도상으로는 좀 비효율적일수 있지만, 계산 자체가 가벼워서 별로 차이는 안난다. 확장 유클리드 알고리즘을 반복해서 적용해야 하는 문제를 본적도 없어서 별 신경 안써도 될것 같다

그것보다는, 그냥 확장 유클리드 알고리즘 코드를 구현해도 워낙 심플하기 때문에 굳이 이렇게 회피해야 하는가 하는 생각은 든다.