[정수론] 디오판토스 방정식 (Diophantine equation)

디오판토스 방정식 ($ax + by = c$)

정수를 계수로 갖는 방정식의 정수해를 구하는 문제를 디오판토스 방정식 (또는 부정방정식)이라 한다.

요즘에도 그런지 모르겠는데, 필자가 고등학생일때 수학의 정석에 간단한 경우(상황이 특수한 경우)에 소개되어있다.

정수론에서 보다 일반적인 방법으로 이 방정식을 푸는 방법을 소개한다.

$a, b, c \in \mathbb{Z}$이고 (적어도 하나는 $0$이 아니다.) $d=\gcd(a, b)$라 하자. 이 때,
(1) 방정식 $ax + by = c$의 해가 존재하기 위한 필요충분조건은 $d \mid c$ 이다.
(2) $x_0, y_0$가 $ax + by = c$의 특수해(particular solution)일 때, 일반해는 다음과 같다.
\[ x = x_0 + \bigg( \frac{b}{d} \bigg) t, \quad y = y_0 - \bigg( \frac{a}{d} \bigg) t \]
(단, $t$는 정수)

 

방정식 $3x + 6y = 18$의 경우, $(3, 6)=3$이고 $3 \mid 18$ 이므로 해가 존재한다.

방정식 $2x + 10y = 17$의 경우, $(2, 10)=2$이고 $2 \nmid 17$이므로 해가 존재하지 않는다.

 

해의 존재성 증명

\[ ax + by = c \text{ has a solution} \iff d \mid c\text{, where } d = \gcd(a, b) \]

(i) $\Rightarrow$

$ax + by = c$의 해가 존재한다고 하자.

$d = \gcd(a, b)$라 하면 $a = dr$이고 $b = ds$인 정수 $r, s$가 존재한다.

$c = ax + by = drx + dsy = d(rx + sy)$ 이므로 $d \mid c$이다.

(ii) $\Leftarrow$

유클리드 호제법에 의해, $ax_0 + by_0 = d$인 $x_0, y_0$가 존재한다.

$d \mid c$이므로 $c = dt$인 정수 $t$가 존재한다.

따라서 $c = dt = a(tx_0) + b(ty_0) = ax + by$

 

일반해(General Solution) 구하기

$x', y'$를 $ax + by = c$의 general solution이라 하자.

$c = ax' + by' = ax_0 + by_0$이므로 $a(x' - x_0) = b(y_0 - y)$

$a = dr, b = ds$인 소수 $r, s$가 존재하므로 $r(x' - x_0) = s(y_0 - y')$로 쓸 수 있다.

그리고 $r \mid s(y_0 - y')$이고 $gcd(r, s)=1$이기 때문에 $r \mid (y_0 - y')$

따라서 $y_0 - y' = rt$인 정수 $t$가 존재한다.

정리하면 $y' = y_0 - rt = y_0 - \left( \frac{a}{d} \right)t$이고 $x' = x_0 + \left( \frac{b}{d} \right)t$ 이다.

 

예제 1. 

\[ 216x + 152y = 16 \]

유클리드 알고리즘을 이용하여 $\gcd(216, 152)$를 구해보면

\begin{align} 216 &= 152 \cdot 1 + 64 \\ 152 &= 64 \cdot 2 + 24 \\ 64 &= 24 \cdot 2 + 16 \\ 24 &= 16 \cdot 1 + 8 \\ 16 &= 8 \cdot 2 \end{align}

$\gcd(216, 152) = 8$이고 $8 \mid 16$ 이므로 해가 존재한다.

즉 $216 \cdot (-7) + 152 \cdot 10 = 8$이므로 $2$를 곱해서 특수해 $x_0 = -14, y_0=20$을 찾을 수 있다.

따라서 일반해는 $x = -14 + 19t, \ y = 20 - 27t$ 이다.

※ particular solution을 유클리드 알고리즘을 이용하지 않아도 된다. 그러나 직관이나 운에 의존하지 않고 특수해를 찾을 수 있다.

Python Code

def ext_gcd(a, b):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while b != 0:
        q = a // b
        a, b = b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
        
    return a, x0, y0

a = 216
b = 152
c = 16

print(f'{a}x + {b}y = {c}')
d, x0, y0 = ext_gcd(a, b)
if c % d == 0:
    x0 *= c // d
    y0 *= c // d
    print(f'Particular Solution: x = {x0}, y = {y0}')
    print(f'General Solution: x = {x0} + {b // d}t, y = {y0} - {a // d}t')
else:
    print('No solution.')​

 

디오판토스 방정식의 확장

이제 $n$개의 미지수 $x_1, x_2, \dots, x_n$를 갖는 디오판토스 방정식을 구하는 방법을 알아보자.

$a_1, a_2, \dots, a_n$이 모두 $0$은 아닌 정수고, $d = (a_1, a_2, \dots, a_n)$이라 하자. 이 때 방정식
\[ a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = c \]
의 해가 존재할 필요충분조건은 $d \mid c$ 이다.

 

일반해를 구하는 방법

$d_1 = (a_1, a_2)$라 하자. 그러면 $n-1$개의 미지수 $u, x_3, x_4, \dots, x_n$을 갖는 방정식 

$(a_1 \lambda_1 + a_2  \lambda_2)u + a_3 x_3 + a_4 + x_4 + \dots + a_n x_n = c$를 푼다.

이렇게 계속 미지수를 줄여가다보면 미지수가 $2$개인 방정식의 해를 구하는 문제로 귀결된다.

 

예제 2.

\[ 21x + 14y + 12z = 4 \]

의 해를 구해보자.

먼저 $(21, 14, 12) = (7, 12) = 1$이고 $1 \mid 4$이므로 해가 존재한다.

$(21, 14)=7$이므로 위 방정식은 

\[ 7u + 12z = 4, \quad u = 3x + 2y \]

이다.

 

$7u + 12z = 4$의 특수해는 $x_0 = -20, y_0 = 12$이므로

$u = -20 + 12t$, $z = 12 - 7t$ 이다.

$u = 3x + 2y$이므로 $3x + 2y = -20 + 12t$

$(3, 2)=1$이고 $1 | (-20 + 12t)$이므로 해를 갖는다.

한편 (유클리드 알고리즘을 이용하지 않고도 보인다) $3 \cdot 1 + 2 \cdot (-1) = 1$이므로

$3(-20 + 12t) + 2(20 - 12t) = -20 + 12t$ 임을 알 수 있다.

따라서 정수해는

\[ x = -20 + 12t + 2s, \quad y = 20 - 12t - 3s, \quad z = 12 - 7t \]

이다.

 

BOJ 3955, 캔디 분배, 플레티넘 5

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

문제를 해석하면 다음과 같다.

• $kx + 1 = cn$을 만족하는 $n$을 구한다. $n$이 존재하지 않으면 "IMPOSSIBLE"을 출력한다.
• $k$, $c$, $n$의 범위는 모두 $1$이상 $10^9$ 이하이다.

디오판토스방정식의 조금 전 단계인 베주항등식을 푸는 문제이다.

$kx + 1 = cn$을 $cn + k(-x) = 1$로 보고, $ax + by = 1$의 형태로 간주하여 푼다.

확장 유클리드 호제법으로 구할 수 있다.

그리고 $n$의 특수해를 구한 후($n_0$), 일반해의 범위에서 최솟값을 찾는다. $n = n_0 + kt$

이때 $k$는 항상 양수임이 보장되므로 부등식 $n_0 + kt > 0$을 만족하는 $k$의 범위는 $k > -\frac{n_0}{k}$

정수범위에서는 $t_{min} = \lceil -\frac{n_0}{k} \rceil$ 가 된다.

범위 안에 $n$이 있으면 아무거나 출력하면 되므로 $t_max$와 $n_max$는 굳이 구할 필요가 없다.

import sys
#sys.stdin = open('input.txt', 'r')
#sys.setrecursionlimit(10 ** 7)
input = lambda: sys.stdin.readline().rstrip()

MIN = 0
MAX = 10 ** 9

def ext_gcd(a, b):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while b != 0:
        q = a // b
        a, b = b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
        
    return a, x0, y0

def solve(K, C):
    # C * N + K * (-X) = 1
    if C == 1:
        if K + 1 <= MAX:
            return K + 1
        else:
            return 'IMPOSSIBLE'
        
    if K == 1:
        return 1
    
    # C * N + K * (-X) = 1
    d, n0, x0 = ext_gcd(C, K)
    #print(d, n0, x0)
    if d != 1:
        return 'IMPOSSIBLE'
    
    t_min = (-n0 + K - 1) // K
    n_min = n0 + K * t_min
    #t_max = (10 ** 9 - n0 - 1) // K
    #n_max = n0 + K * t_max    
    #print(n_min, n_max)
    
    if n_min > MAX:
        return 'IMPOSSIBLE'
    else:
        return n_min

T = int(input())
LOWER = 0
UPPER = 10 ** 9
for _ in range(T):
    K, C = map(int, input().split())
    ans = solve(K, C)
    print(ans)