디오판투스 방정식
이름이 거창해보이지만 내용은 정수 계수 부정 방정식이다.
예를 들면 $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
정해는 모듈러 역원을 사용하는 것이지만 디오판투스 방정식을 확장 유클리드 알고리즘으로 해결함으로써 답을 구할 수 있었다.
우선 어떻게 해서든 $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$이고 방정식의 정수해는 반드시 존재한다.
'수학 > 정수론' 카테고리의 다른 글
[정수론] 6. 중국인의 나머지 정리 (0) | 2022.04.21 |
---|---|
[정수론] 5. 고차 합동 방정식 (0) | 2022.04.20 |
[정수론] 4. 합동 (0) | 2022.04.17 |
[정수론] 2. 유클리드 호제법 (0) | 2022.04.06 |
[정수론] 1. 피타고라스 세 수 (4) | 2022.04.06 |