부정방정식

방정식 $x+y=3$의 해를 생각해 보자. 아무런 조건이 없다면 해는 무수히 많다. 직선 위에 있는 모든 점들이 해가 된다. 이처럼 해가 너무 많아서 정할 수 없는 방정식을 부정방정식으로 부른다. 연립방정식에서 미지수 개수보다 방정식 개수가 적다면 부정방정식이다. $x,y \in \mathbb{N}$이란 조건을 더하면 해는 $(1,3),\;\;(2,2)\;\;(3,1)$이다. 이처럼 부정방정식 해 가운데 조건에 맞는 해를 찾는 문제가 있다. 부정방정식 가운데 정수해만을 구하는 것을 디오판토스 방정식이라고 한다. 예를 들면

$$a_1 x_1 +a_2 x_2 +\cdots +a_n x_n =b\;\;(a_i , b \in \mathbb{Z}),\;\;x^2 +y^2 =z^2$$

이 있다. 이제 간단한 디오판토스 방정식 풀이를 알아 보자.

유클리드 알고리즘

두 정수 $a,b $의 최대공약수는 $(a,b)$로 쓰기로 하자.

$$a=qb+c\;\;(q\in \mathbb{Z}, 0 \leq c <b)$$

$(a,b)|a,\;\;(a,b)|b,\;\;c=a-qb$이므로 $(a,b)|c$이다. 따라서, $(a,b)|(b,c)$이다.

$(b,c)|b, \;\;(b,c)|c, \;\;a=qb+c$이므로 $(b,c)|a$이다. 따라서, $(b,c)|(a,b)$이다.

$$a=qb+c\;\;(q\in \mathbb{Z}, 0 \leq c <b) \implies \;\;(a,b)=(c,d)$$

다시 $b$를 $c$로 나누었을 때 나머지를 $d$라고 하면, $(b,c)=(c,d)$이다. 이와 같이 계속하면 $$a>b>c>d>\cdots$$이므로 결국 나머지는 $0$이 된다. 만약 $c$가 $d$로 나누어떨어진다면 $$(a,b)=(b,c)=(c,d)=(d,0)=d$$이 과정을 유클리드 알고리즘(최대공약수를 구하는)이라 부른다.

등식 $(3654,1365)=d=3654x+1365y$를 만족하는 정수 $d,x,y$를 유클리드 알고리즘으로 구해보자.

$3654=2\cdot 1365+924$

$1365=1\cdot 924 +441$

$924=2\cdot 441+42$

$441=10\cdot 42 +21$

$42=2\cdot 21$ 이므로 $d=21$이다. 이제 거꾸로 정리하면

$$21=441-10\cdot 42=441-10(924-2\cdot 441)=21\cdot 441-10\cdot 924=21(1365-924)-10\cdot 924 \\ =21\cdot 1365-31\cdot 924=21\cdot 1365-31(3654-2\cdot 1365)=83\cdot 1365+(-31)3654$$이다.

그러므로 $x=-31,\;y=83$이다.

유클리드 알고리즘에 의하면 정수 $a,b\;(a\not=0)$에 대해서 $ax+by=d$를 만족하는 정수 $x,y$를 구할 수 있다. 이때, $d=(a,b)$이다. 보기를 들면 $(18,30)=6$이므로 $18x+30y=6$을 만족하는 $x,y$ 

$$18\times 2 +30\times(-1)=6$$와 같이 구할 수 있다.

정리하면 유클리드 알고리즘은 $(a,b)=d$일 때, 부정방정식 $ax+by=d$는 적어도 한쌍의 정수해 $x_0 , y_0$를 가짐을 보여준다. 부정방정식 $ax+by=c$가 정수해를 가질 필요충분조건은 $d|c$이다. 또 $d|c$일 때 하나의 특수해를 $x_0, y_0$라고 한다면 모든 정수해를 $x_0 ,y_0 $로 나타낼 수 있다.

$x_0, y_0$와 $x_1, y_1$이 모두 방정식 $ax+by=d$의 해라고 하자.

$$ax_0 +by_0 =d\;\;\cdots \cdots (1)$$

$$ax_1 +by_1 =d\;\;\cdots \cdots (2)$$

$$(1)\times y_1 - (2)\times y_0$$

$$a(x_0 y_1 -x_1 y_0)=d(y_1-y_0)$$

$$y_1 =y_0 + \frac{a}{d} k \quad \quad (k=x_0 y_1 -x_1 y_0 )$$

마찬가지로 

$$(1)\times x_1 - (2)\times x_0$$

$$b(x_1 y_0 -x_0 y_1)=d(x_1-x_0)$$

$$x_1 =y_0 - \frac{b}{d} k \quad \quad (k=x_0 y_1 -x_1 y_0 )$$

정리하면 $ax+by=d$가 특수한 정수해 $x_0, y_0$를 가지면 모든 정수해는

$$x=x_0 - \frac{b}{d} t,\;\;y=y_0 +\frac{a}{d}t \quad \quad (t\in \mathbb{Z})$$

$ax+by+cz=d$의 해를 구하는 알고리즘 

(1) $ax+by=t,\;\;t+cz=d\;\;(t\in \mathbb{Z})$로 놓고

(2) $ax+by=1$의 특수해를 찾고

(3) $ax+by=t$의 모든 정수해를 구하고

(4) $t+cz=d$의 모든 정수해를 구한다.

(5) 위 (3)(4)에서 구한 해를 조합하여 해를 구한다.

합동식과 부정방정식

정수 $a,b$와 자연수 $n$에 대하여, $n|(a-b)$이면 정수 $a$와 $b$는 모듈(mod) n에 관해 합동이라고 하고 합동식

$$a \equiv b\quad(mod\;\; n)$$

로 적는다.

$$a=qb+c\quad (0\leq c<b)\implies a \equiv b\quad (mod\;\;b)$$

합동식은 다음과 같은 기본 성질을 가진다.

(1)  $a \equiv a\quad (mod\;\;n)$

(2)  $a \equiv b\quad (mod\;\;n)\implies b \equiv a \quad (mod\;\;n)$

(3)  $a \equiv b\quad (mod\;\;n),\;\; b \equiv c \quad (mod\;\;n)\implies a \equiv c \quad (mod\;\;n)$

(4)  $a \equiv b\quad (mod\;\;n),\;\; c \equiv d \quad (mod\;\;n)$

     (4-1) $\implies (a+c) \equiv (b+d) \quad (mod\;\;n)$

     (4-2) $\implies (a-c) \equiv (b-d) \quad (mod\;\;n)$

     (4-2) $\implies ac \equiv bd \quad (mod\;\;n)$

(5)  $ac \equiv bc\quad (mod\;\;n),\;\;(c,d)=1 \implies a \equiv b\quad(mod\;\;n)$

(6)  $t\geq 2,\;a \equiv b\quad (mod\;\;n_1),\;\;a \equiv b\quad (mod\;\;n_2),\cdots \;a \equiv b\quad (mod\;\;n_t),\;\;$

  $\implies \; \;a \equiv b \quad (mod \;\; N)\;\; N$은 $n_1 ,n_2 , \cdots n_t $의 최소공배수 (중국 나머지정리)

(7)  $a \equiv b\quad (mod\;\;n)\implies a^m \equiv b^m \quad (mod\;\;n)\;\;(m \in \mathbb{N})$

(8)  $a \equiv b\quad (mod\;\;n)\implies a \equiv b+kn \quad (mod\;\;n)$

(9)  $\displaystyle{ac \equiv bc \quad (mod\;\;n),\;\;(c,n)=d>1 \implies a \equiv b \quad \left(mod \;\; \frac{n}{d} \right)}$

1차부정방정식은 1차합동식으로 생각할 수 있다.

$$ax+by=c  \iff ax \equiv c\quad (mod\;\;b)$$

(1) $55x+6y=8$은 $55x \equiv 8 \equiv 2 (mod\;\;6)$이므로 $x=2+6n$이고 $\displaystyle{\frac{8-55(2+6n)}{6}=-17-55n}$이다.

(2) $15x \equiv 1 (mod\;44)$는 $15x-44y=1$을 푼다. $15\cdot3-11\cdot1=1$이므로 모든 정수해는 

     $x=3+44t (t \in \mathbb{Z}$ 즉, $x \equiv 3\;\;(mod\;\; 44)$이다.

연립합동식을 풀자.

$$\cases{x \equiv 2\quad (mod\;\;3) \\ x \equiv 3 \quad (mod\;\;5) \\ x \equiv 5 \quad (mod\;\; 7)}$$

$x\equiv 5(mod\;7)$이므로 $x=7k+5$ 두 번째 합동식에서 $7k+5 \equiv 3\;(mod \;5) \implies 2k \equiv 3\; (mod \;5) \implies k \equiv 4 \; (mod \;5)$이다. $k=5m+4 (m$은 정수)이다. 

$$x=7k+5=7(5m+4)+5=35m+33 \equiv 2\;\;(mod\;3)$$

$2m \equiv 2 \;\;(mod\;3), m \equiv 1\;\;(mod\;3)$이다. $m=3t+1 (t$는 정수)이므로

$$x=35m+33=35(3t+1)+33=105t+68$$

그러므로 해는$$x \equiv 68(mod\;105)$$

다른 꼴의 부정방정식

1. $AB=k$꼴

유클리드 알고리즘으로 풀리는 꼴이 아닌 부정방정식은 다른 풀이를 찾아 해결해야 한다. 곱으로 표현하여 약수와 배수 관계를 쓰거나 부등식을 쓰는 방법이 대표적이다.

$xy+6x-y=18$의 양의 정수해를 구해보자.

$x(y+6)-(y+6)+6=18 \implies (x-1)(y+6)=12$

$y+6 | 12$이므로 $y+2=1,2,3,4,6,12$이다.

$y>0$이라야 하므로 $y=6$이다. $x=2$를 얻는다.

또 다른 예를 들어보자.

$a^5 =b^4 ,\;c^3 =d^2,\;c-a=19$일 때, $d-b$의 값을 구하여라.

$5$와 $4$의 최소공배수는 $20$이고 $3$과 $2$의 최소공배수는 $6$이므로

자연수 $m,n$에 대하여 $a^5 =b^4 =m^{20} ,\;\;c^3 =d^2 =n^6$이라고 하면

$a=m^4,\;b=m^5,\;c=n^2,\;d=n^3$이다.

따라서 $c-a=n^2 -m^4 =(n+m^2)(n-m^2)=19$로 부터 $n+m^2 =19, \;n-m^2 =1$에서 $n=10,m=3$이다.

따라서 $d-b=10^3 -3^5 =757$이다.

2. 완전제곱식이나 판별식을 쓰는 꼴

부정방정식 $\displaystyle{\frac{x+y}{x^2 -xy+y^2}=\frac{3}{7}}$의 정수해를 구해보자.

$3x^2 +(-3y-7)x+3y^2 -7y=0$으로 바꿀 수 있다.

실수 $x$에 대한 이차방정식으로 볼 때 실수 근을 가져야 하므로 판별식 $D \geq 0$이다.

$$D=(-3y-7)^2 -12(3y^2 -7y)=-27y^2 +126y+49 \geq 0$$

이를 만족하는 $y$의 범위는

$$\frac{21-14\sqrt{3}}{9} \leq y \leq \frac{21+14 \sqrt{3}}{9}$$

$$\therefore \;\;y=1,1,2,3,4,5$$

주어진 식에 대입하여 정수 $x$를 구하면 $(x,y)=(4,5),(5,4)$

3. 정수의 표현을 이용하는 꼴

부정방정식 $y^3 =x^2 +x$를 만족하는 정수해를 구해보자.

$y^3 =x(x+1)$에서 우변이 $0$면 $y=0$이다. 따라서, $(x,y)=(0,0),(-1,0)$은 해가 된다.

우변이 $0$이 아니라면 $x|y^3 ,x+1 |y^3$이다.

하지만 $(x,x+1)=1$이므로 두 수 $x,x+1$이 동시에 $y$의 약수가 될 수 없다.

따라서 다른 해는 없다.

4. 부등식을 이용하는 꼴

부정방정식 $\displaystyle{\frac{1}{x} +\frac{1}{x+1}+\frac{1}{x+2}=\frac{13}{12}}$을 만족하는 정수해를 구해보자.

분모에서 $x<x+1<x+2$이므로 $\displaystyle{\frac{1}{x} >\frac{1}{x+1}>\frac{1}{x+2}}$이다.

식을 $\displaystyle{\frac{13}{12}= \frac{1}{x} +\frac{1}{x+1}+\frac{1}{x+2} <\frac{3}{x}}$와

$\displaystyle{\frac{13}{12}= \frac{1}{x} +\frac{1}{x+1}+\frac{1}{x+2} >\frac{3}{x+2}}$로 생각하면

$\displaystyle{\frac{10}{13}<x<\frac{36}{13}}$을 얻는다.

$x=1,2$인데 $x=2$만 주어진 식을 만족한다.

아래 부정방정식을 풀어 보아라.

1) $\displaystyle{\frac{1}{x}-\frac{1}{y}=\frac{1}{4}}$ : 양의 정수해

2) $\displaystyle{4x^2 y =y^4 +2x^4 +1}$ : 정수해

3) $x=yz (y,z$은 소수)일 때, $\displaystyle{\frac{1}{x}+\frac{1}{z} =\frac{3}{z}}$을 만족하는 정수해

4) $x+y+z=xyz$ : 양의 정수해

펠 방정식을 이용하는 것은 다음을 기약한다.