부정방정식 풀이

주어진 세 정수 $a,b,c$에 대하여 방정식 $ax+by=c$를 만족하는 해를 찾는 방법을 적는다. 해가 무수히 많은 방정식을 부정방정식으로 부른다. 영어로는 디오판토스 이름을 따서 Diophantine equation이라고 한다.

정리 $ax+by=c$가 해를 가질 필요충분조건은 $d|c\;\;d=gcd(a,b)$이다. $x_0 ,y_0$가 특별 해라면 일반 해는 아래와 같다.

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

증명 $x_0 ,y_0$와 $x^{\prime},y'$이 알려진 해라고 하자.

$$ax_0 +by_0 =c=ax'+by'$$

$$a(x'-x_0)=b(y_0-y')$$

$$r(x'-x_0)=s(y_0-y')\;\;(a=dr,b=ds)$$

$$r|(y_0-y')\;\;(\because gcd(r,s)=1)$$

$$x'-x_0=st \;\;(y_0-y'=rt)$$

$$x'=x_0 +st=x_0+\bigg(\frac{b}{d}\bigg)t$$

$$y'=y_0 -st=y_0-\bigg(\frac{a}{d}\bigg)t$$

역으로 $x',y'$이 해임을 보이자.

$$ax'+by'=a\bigg[ x_0+\bigg(\frac{b}{d}\bigg)t \bigg]+b \bigg[ y_0-\bigg(\frac{a}{d}\bigg)t \bigg]$$

$$=(ax_0+by_0)+\bigg(\frac{ab}{d}-\frac{ab}{d}\bigg)t=c+0\cdot t=c$$

연습문제 $172x+20y=1000$의 해를 구해보자.

$$172=8\cdot 20+12\\20=1\cdot 12+8\\12=1\cdot8+4\\8=2\cdot 4\\\therefore gcd(172,20)=4$$

$$4=12-8=12-(20-12)=2\cdot 12-20=2(172-8\cdot 20)-20=2\cdot 172+(-17)20$$

$$1000=250\cdot 4=250[2\cdot 172+(-17)20]=500\cdot 172+(-4250)20$$

$$\therefore x_0=500,\;\;y_0=-4250$$

$$\cases{x=500+\frac{20}{4}t=500+5t\\ y=-4250-\frac{172}{4}t=-4250-43t}$$