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

728x90

디오판토스 방정식 ( $a x + b y = c$ )

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

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

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

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

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

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

해의 존재성 증명

$a x + b y = c has a solution ⟺ d ∣ c, where d = gcd (a, b)$

(i) $\Rightarrow$

$a x + b y = c$ 의 해가 존재한다고 하자.

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

$c = a x + b y = d r x + d s y = d (r x + s y)$ 이므로 $d ∣ c$ 이다.

(ii) $\Leftarrow$

유클리드 호제법에 의해, $a x_{0} + b y_{0} = d$ 인 $x_{0}, y_{0}$ 가 존재한다.

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

따라서 $c = d t = a (t x_{0}) + b (t y_{0}) = a x + b y$

일반해(General Solution) 구하기

$x^{'}, y^{'}$ 를 $a x + b y = c$ 의 general solution이라 하자.

$c = a x^{'} + b y^{'} = a x_{0} + b y_{0}$ 이므로 $a (x^{'} - x_{0}) = b (y_{0} - y)$

$a = d r, b = d s$ 인 소수 $r, s$ 가 존재하므로 $r (x^{'} - x_{0}) = s (y_{0} - y^{'})$ 로 쓸 수 있다.

그리고 $r ∣ s (y_{0} - y^{'})$ 이고 $g c d (r, s) = 1$ 이기 때문에 $r ∣ (y_{0} - y^{'})$

따라서 $y_{0} - y^{'} = r t$ 인 정수 $t$ 가 존재한다.

정리하면 $y^{'} = y_{0} - r t = y_{0} - (\frac{a}{d}) t$ 이고 $x^{'} = x_{0} + (\frac{b}{d}) t$ 이다.

예제 1.

$216 x + 152 y = 16$

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

$\begin{aligned} 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{aligned}$

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

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

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

※ 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} + \dots + a_{n} x_{n} = c$
의 해가 존재할 필요충분조건은 $d ∣ c$ 이다.

일반해를 구하는 방법

$d_{1} = (a_{1}, a_{2})$ 라 하자. 그러면 $n - 1$ 개의 미지수 $u, x_{3}, x_{4}, \dots, x_{n}$ 을 갖는 방정식

$(a_{1} λ_{1} + a_{2} λ_{2}) u + a_{3} x_{3} + a_{4} + x_{4} + \dots + a_{n} x_{n} = c$ 를 푼다.

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

예제 2.

$21 x + 14 y + 12 z = 4$

의 해를 구해보자.

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

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

$7 u + 12 z = 4, u = 3 x + 2 y$

이다.

$7 u + 12 z = 4$ 의 특수해는 $x_{0} = - 20, y_{0} = 12$ 이므로

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

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

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

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

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

따라서 정수해는

$x = - 20 + 12 t + 2 s, y = 20 - 12 t - 3 s, z = 12 - 7 t$

이다.

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

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

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

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

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

$k x + 1 = c n$ 을 $c n + k (- x) = 1$ 로 보고, $a x + b y = 1$ 의 형태로 간주하여 푼다.

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

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

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

정수범위에서는 $t_{m i n} = ⌈ - \frac{n_{0}}{k} ⌉$ 가 된다.

범위 안에 $n$ 이 있으면 아무거나 출력하면 되므로 $t_{m a x}$ 와 $n_{m a x}$ 는 굳이 구할 필요가 없다.

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)

728x90

'스터디 > 정수론' 카테고리의 다른 글

[정수론] 소수와 관련된 알고리즘 (소수 판정, 에라토스테네스의 체, 오일러 피 함수) (0)	2024.08.11
[정수론] 약수, 배수, 최대공약수, 최소공배수와 관련된 알고리즘 (0)	2024.08.10
[정수론] 오일러의 정리, 페르마의 소정리, 중국인의 나머지 정리, 윌슨의 정리 (0)	2024.08.06

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

궁금한게많은joon

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