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

디오판투스 방정식은 정수 부정방정식을 말한다.

이 글에서는 2원 1차(linear) 디오판투스 방정식을 다룰 것이다.

즉, a x + by = c  꼴 이다.    ( 당연히, 우리의 관심은 a,b,c 가 0 이 아닐때이다. )

디오판투스의 Arithmetica 는 원래 13권인데, 그중 6권만 전해지고 있는데, 저 방정식의 해법은 없댄다. 대신, 유클리드의 Elements 에 나온다나..

디오판투스 방정식의 해에 존재에 대한 정리.

---

a x +  b y = c    has a solution if and only if   (a,b) | c

---

=>  증명)   ax + by = c has a solution, say x0 , y0 , then  ax0 + by0 = c 

                     NOTE.   (a,b) | a , and   (a,b) | b     , therefore ,   (a,b) | c

<=  증명)   (a,b) | c  이면,   c = (a,b) k   ,   NOTE,  (a,b) = ax + by for some x,y

                therefore, c = (ax + by) k = a (xk ) + b (yk)    ,   so, it has a solution (xk, yk )

---

부정방식은 복수개의 해를 갖을 수 있는데, 주어진 해로 부터, 다른 해를 구하는 방법을 생각해보자.

---

주어진 해에 대해,      b / (a,b)  ,  -a / (a,b)   를   각각 더해도 해가 된다.

---

증명.    a ( b / (a,b) ) + b ( -a / (a,b) ) = 0   이므로 주어진 x,y 해에 대해, 더해도, 주어진 방정식에 해를 끼치지 않는다.

---

예.  7x  +  4y  =  100

      (7,4) = 1  , 1 | 100 ,   따라서 해는 존재함.

      

              x = 4 ,  y = 18    은  해 이므로,       여기에    4, -7 을 임의로 더해도 해가 된다.

따라서,    x= 8  ,  y = 11  도 해이고,

              x=12 ,  y = 4   도 해이고,

              x=16  ,  y = -3  도 해이고, 등등...