Diophantine Equation(디오판틴 방정식)과 파이썬 코드

주어진 정수 \(a, b, c\)에 대하여 \[ax + by = c\]를 만족하는 정수 \(x, y\)를 찾는게 목적이다.

\(d\)는 \(a, b\)의 최대공약수라고 하자. 이 때, \(d\mid c\)인 경우 무한한 \(x, y\)가 존재하고, \(d\nmid c\)인 경우 해는 존재하지 않는다. (\(a\mid b\)의 의미는, \(a\)는 \(b\)를 나눌 수 있다는 의미이다.)

해가 존재할 경우, 특수해(Particular Solution)는 \(x_0=c/d\times s, y_0=c/d\times t\)로 구한다. 이 때 s와 t는 Extended Euclidean Algorithm으로 구한 값이다.

일반해(General Solution)는 \(x=x_0+k(b/d), y=y_0-k(a/d) \mbox{ where } k\in \mathbb Z\)로 구할 수 있다.

예를 들어 방정식 \(21x +14y =35\)를 풀어보자. 우선 \(d=\mbox{gcd}(21, 14)=7\mid 35\)이므로 무수히 많은 해가 존재한다. 그럼 양변을 7로 나누면 \(3x+2y=5\)로 간소화할 수 있다. 이제 \(s\)와 \(t\)를 구하기 위해 Extended Euclidean Algorithm을 사용하면

\(q\)	\(r_1\)	\(r_2\)	\(r\)	\(s_1\)	\(s_2\)	\(s\)	\(t_1\)	\(t_2\)	\(t\)
1	3	2	1	1	0	1	0	1	-1
2	2	1	0	0	1	-2	1	-1	3
	1	0		1	-2		-1	3

따라서 \(s=1, t=-1\)이므로 특수해는 \(x_0=35/7\times 1=5, y_0=35/7\times -1=-5\)이고, 일반해는 \(x=5+2k, y=-5-3k\)가 된다.

디오판틴 방정식의 특수해(\(x_0, y_0\))를 구하는 파이썬 코드를 작성해보자.

def diophantine(a, b, c):
	'''returns (x, y) where ax+by=c'''
	r1, r2 = a, b
	s1, s2 = 1, 0
	t1, t2 = 0, 1
	
	while r2!=0:
		q = r1/r2
		r1, r2 = r2, r1%r2
		s1, s2 = s2, s1-q*s2
		t1, t2 = t2, t1-q*t2
	# gcd: r1
	return (c/r1*s1, c/r1*t1)

diophantine(21, 14, 35)를 하면 (5, -5)가 반환되는 것을 볼 수 있다.