[정수론] 3. 디오판투스 방정식

디오판투스 방정식

이름이 거창해보이지만 내용은 정수 계수 부정 방정식이다.

예를 들면 $3x+2y=5$ 이런 것이다.

 

지난시간에 $ax+by=c$가 정수 해를 가지려면 $\gcd(a,b) | c$를 만족해야 한다고 했다.

이를 이용하여 다양한 작업을 해보자.

 

>> Theorem)

소수 $p$에 대해서 $p | ab$ 이면 $p|a$이거나 $p|b$이다.

proof

case 1) $p | a$

자명히 성립한다.

case 2) $ p \nmid a$

$p$는 소수이므로 $\gcd(a,p) = 1$

그럼 유클리드 알고리즘에 의해 $ax + py = 1 (=\gcd(a,p))$를 만들 수 있다.

위 식은 해를 가지고 양변에 $b$를 곱하면 $abx + bpy = b$가 된다.

$p | abx$이고 $p | bpy$이기 때문에 좌변은 $p$로 나누어 떨어진다.

우변도 $p$로 나누어 떨어져야 하기 때문에 $p | b$가 된다. $\Box$

 

위 이론을 Prime Divisor Property라고 한다.

 

일반적인 상황에서 디오판투스 방정식을 풀어보자.

$ax + by = \gcd(a,b)$는 지난시간 유클리드 알고리즘을 역연산해서 해결할 수 있었다.

$ax + by = c$도 해결해보자.

우선 $\gcd(a,b)|c$는 반드시 성립해야 한다.

그리고 서로소가 되도록 $a,b,c$를 모두 $\gcd(a,b)$로 나누고 시작한다.

$ax_0+by_0 = \gcd(a,b)$를 만족하는 $(x_0,y_0)$이 있다고 하자. (유클리드 알고리즘으로 구할 수 있다.)

$c = d\gcd(a,b)$라고 하면 해결할 방정식을 $adx_0+bdy_0=d\gcd(a,b)$로 나타낼 수 있고 $x = dx_0, y = dy_0$으로 두면 충분하다.

여기서 더 나아가서 일반해까지 구해보려고 한다.

위에서 구한 해를 $x_1=dx_0, y1=dy_0$으로 두자.

$ax+by=c$, $ax_1+by_1=c$가 있고 두 방정식을 각각 빼면 $a(x-x_1)+b(y-y_1) = 0$이고 $a(x-x_1)=-b(y-y_1)$이 된다.

위에서 $a,b$를 서로소로 만들었으므로 $a | y-y_1, b|x-x_1$을 만족해야 한다. (prime divisor property)

$u|v$는 $v=ku(k \in \mathbb{Z})$라는 뜻과 같다.

따라서 $y-y_1 = ka \rightarrow y = ka+y_1 $, $x = kb+x_1$ $(k \in \mathbb{Z})$이 일반해가 된다.
처음에 $a,b$를 $\gcd(a,b)$로 나누고 시작했으므로 여기서 다시 곱해주면 된다.

 

숭고한 알고리즘 contest에서 이 내용을 사용해서 문제를 해결할 수 있었다.

https://www.acmicpc.net/problem/24892

24892번: 이차 함수

정해는 모듈러 역원을 사용하는 것이지만 디오판투스 방정식을 확장 유클리드 알고리즘으로 해결함으로써 답을 구할 수 있었다.

우선 어떻게 해서든 $p,q$를 서로소인 정수꼴로 나타낸다. (나는 사다리꼴 공식을 사용했다.)

구하고자 하는것이 $qv \equiv p \mod 1000000007$이므로 $qv = 1000000007k + p (k \in \mathbb{Z})$로 나타낼 수 있다.

식을 변형하면 $qv-1000000007k = p$인 디오판투스 방정식이 되고 $p,q$는 구해놨으니 방정식을 풀어서 $v, k$를 구하면 된다.

$1000000007$은 소수이고 문제에서 $0 \le v < 1000000007$이라고 했으므로 $\gcd(v, 1000000007) = 1$이고 방정식의 정수해는 반드시 존재한다.