최근 수정 시각 : 2020-03-15 08:27:02

디오판토스 방정식

1. 개요2. 역사3. 풀이
3.1. 부등식법3.2. 인수분해 및 식의 변형3.3. 잉여계를 이용하는 방법3.4. 무한강하법3.5. 타원곡선
4. 관련 문서

1. 개요

정수론에서 매우 중요한 문제 중 하나로써, 다항방정식정수해 또는 유리수해를 찾는 것이다. 정리하자면 정수 혹은 유리수 계수를 갖는 다항식 F1,F2,,FkF_1, F_2, \cdots, F_k에 대해
F1(x1,,xm)==Fk(x1,,xm)=0,xiZ or Q F_1(x_1, \cdots, x_m) = \cdots = F_k(x_1, \cdots, x_m) = 0, \quad x_i \in \mathbb{Z} \text{ or } \mathbb{Q}
의 해를 찾는 것으로 생각할 수 있다.

교과과정에는 부정방정식 테마 안에 디오판토스 방정식이 소개되긴 하는데, 정확히 말하면 다른 개념이다. 대부분의 디오판토스 방정식은 부정방정식이긴 하다. 부정방정식이 아닌 경우 일반적인 방정식으로 생각해도 무리가 없기 때문. 물론 일반적인 부정방정식은 정수 혹은 유리수 다항식에 관련될 필요도 없고, 정수/유리수해에 국한되어야 하는 것도 아니다. 자세한 것은 부정방정식 참고. 정수해를 찾는 부정방정식에는 2x+3y=5z2^x + 3^y = 5^z 같은 디오판토스 방정식이 아닌 것들도 포함된다. 저런 형태의 것들을 '지수 디오판토스 방정식'이라고 부르기도 하지만, 엄밀하게는 디오판토스 방정식은 아니다.

방정식처럼 딱히 분류가 되어있진 않고, 수학자들이 중요하게 연구하는 몇몇 디오판토스 방정식에는 제각각인 이름이 붙어 있다.
  • 일차 부정방정식: ax+by=cax + by = c의 정수해. 풀이는 베주 항등식을 참조
  • 피타고라스 세 쌍 문제: x2+y2=z2x^2 + y^2 = z^2의 정수해/유리수해. 피타고라스 정리에서 나온 방정식이다. 정확히는 세 변의 길이가 모두 정수인 직각삼각형을 찾는 문제.
  • 펠 방정식: x2Dy2=kx^2 - D y^2 = k의 정수해
  • 페르마의 마지막 정리: xn+yn=znx^n + y^n = z^n (n3n \ge 3) 의 정수해/유리수해. 문서 참조
  • 타원곡선: y2=x3+Ax+By^2 = x^3 + Ax + B 의 정수해/유리수해.
  • 합동수 문제: 변의 길이가 유리수인 삼각형의 넓이가 주어진 유리수 kk가 될 수 있는지의 문제. 타원곡선의 유리수해 문제로 귀결된다.

디오판토스 방정식은 같은 수준의 방정식에 비해 어렵다는 것이 중론이다. 당장에 저 페르마의 마지막 정리만 봐도 그렇고, 한때 인터넷에서 나돌았던 분수방정식 문제

xy+z+yz+x+zx+y=4  (x,y,zN)\dfrac{x}{y+z} + \dfrac{y}{z+x} + \dfrac{z}{x+y} = 4 \ \ (x, y, z \in \mathbb{N})

의 해가 양의 정수라는 조건을 건 디오판토스 방정식 문제가 원문에서는 MIT졸업생의 5%만 풀 수 있다는 문제였으나, 이 문제를 푼 수학자 Alon Amit는[1] MIT 졸업생의 95%은커녕, 99.999995%는 못 풀 거고, 그 중에서는 정수론이 전공이 아닌 대학교 수학 교수도 포함될 거라며 장담을 했을 정도이다. [2] 이 Alon Amit의 의견을 더 들어보면...
  • (디오판토스)일차방정식: 쉬움
  • 이차방정식: 완전히 이해된 수준으로 기초수학 수준에서 해결 가능
  • 삼차방정식: 심오한 이론의 거대한 바다와 수백만 가지의 미해결 문제[3]
  • 사차 이상의 방정식: 정말...정말로 어렵다.
즉 삼차 이상으로 넘어가면 일반인 수준으론 답이 없다는 뜻이다. 그리고 이 디오판토스 방정식은 삼차다. 더 나아가서, (원문의 수식을 가져오자면) 기쁘게도, 그리고 끔찍하게도, 타원곡선의 형태다. 그래서 미해결 문제까진 아니지만, 해만 터무니없이 큰 게 아니라 풀이법도 까다롭다.

다항방정식의 경우 복소수 위에서는 항상 해가 있다는 것이 대수학의 기본정리로 증명되었고, 지수방정식도 해의 유무는 미분으로 판정할 수 있지만, 디오판토스 방정식의 해가 존재하는지 아닌지 알 수 있는 일반적인 알고리즘은 없다는 것이 증명되었다. (힐베르트의 10번째 문제의 마티아셰비치의 풀이) 일반적인 경우는 고사하고 저 단순해 보이는 타원곡선도 해의 개수를 구하는 문제는 몇백여년 동안 미해결이라, 지금도 밀레니엄 문제 중 하나인 버츠와 스위너톤-다이어 추측이란 이름으로 수학자들을 괴롭히고 있다. 어떻게 보면 편미분방정식하고 느낌이 비슷하다. 중요하다고 생각해서 연구는 많이 했지만 해가 있는지 없는지도 모르고, 수치계산은 하지만 그게 해인지는 장담할 수 없고...

대신에 많은 이/공학 분야의 핵심 도구인 편미분방정식과 다르게 현실세계에서 쓰임새는 좀 잉여스럽다. 모든 물리량을 실수로 생각하는 현실에서 정수방정식이 자연스럽게 나오는 것도 아니고, 방정식의 해가 정수로 맞아떨어지는 것도 심미성 이상의 딱히 큰 의미를 갖진 않는다. 덕분에 디오판토스 방정식은 그 정수론 중에서도 가장 순수한 분야로 취급받아 왔다. 다만 근/현대에 들어서 컴퓨터이산수학의 발전으로 이 디오판토스 방정식마저 응용되는 분야가 등장하기 시작했다. 당장에 타원곡선암호에 응용되고, 소인수분해 문제 등을 계기로 디오판토스 방정식의 빠른 풀이가 중요시되는 알고리즘 정수론(algorithmic number theory)이 급부상하며, 최적화 문제에서 정확한 정수해가 필요한 정수계획법(integer programming) 문제가 산업현장에서 나오는 걸 보면 정수론이 순수하다는 것도 옛말일지도 모른다. 솔직히 대부분의 디오판토스 방정식 연구는 이런거랑 상관없다

물론 많은 수학자들, 특히 대수적 정수론 덕후들에게는 그런 거 없고, 인류가 몇 천년 동안 연구했던 근본적인 문제와 그 아름다움에 대한 탐구만이 있을 뿐이다.

2. 역사

기원전 1800년경의 것으로 추정되는 고대 바빌로니아의 Plimpton 322 석판(콜롬비아 대학의 Plimpton 소장품)에는 다양한 피타고라스의 세 쌍(즉 a2+b2=c2a^2 + b^2 = c^2의 정수해)들이 60진법 쐐기문자로 적혀 있다. 저 석판의 의미가 무엇인지는 논쟁의 여지가 있지만, 단순히 (3,4,5)나 (5,12,13) 이런 작은 숫자가 아니라 49612+64802=816124961^2 + 6480^2 = 8161^2 같은 큰 숫자들이 랜덤하게 적혀 있는 걸 봐서는 이들이 자연수 길이로 직각삼각형을 만드는 체계적인 방법을 알았을 것으로 추정된다. 2의 제곱근의 근사값이 적혀있는 다른 석판에서 드러나듯 바빌로니아인들은 제곱근과 피타고라스 정리에 대해 확실히 알고 있었다. 고대 이집트의 수학에 대해선 바빌로니아보다는 남아 있는 자료가 없지만, 이들이 밥먹듯이 하는게 단위분수 분해였니 만큼[4] 정수문제도 많이 연구했을 것이다. 사실 고전 그리스 까지만 해도 자연수말고 다른 수는 (거의) 없었기 때문에 "방정식=정수방정식"이긴 했다.

고대 그리스의 수학은 기하학이 주였지만 수론에 대해서도 당연히 많은 발전이 이루어졌다. 유클리드의 원론은 소인수분해(즉 산술의 기본정리 증명)와 유클리드 호제법, 약수/배수의 성질 등을 기초정수론 수준으로 다루고 있고, 그리고 우리가 알고 있는 피타고라수 세 쌍의 일반적인 풀이 (a,b,c)=k(m2n2,2mn,m2+n2)(a,b,c)=k(m^2-n^2, 2mn, m^2 +n^2) (원론 원전에는 서로소인 풀이, 즉 k=1k=1의 풀이만이 나와있다)가 제시된다. 정수방정식에 대해 더욱 집중적으로 연구한 것은 이 항목의 이름을 만들어준 디오판토스로, 그의 '산학'(Arithmetica, Ἀριθμητικῶν) 책에선 최초로 미지수를 문자로 사용하고 이차 정수방정식에 대한 일반적인 고찰을 하였다. 디오판토스 방정식을 사실상 처음 체계적으로 연구한 셈이다. 중세를 거쳐 산학을 포함한 그리스 서적들이 번역되어 아라비아, 인도로 흘러가며 디오판토스 방정식의 연구도 실전(失傳)과 수복을 반복하며 띄엄띄엄 이어졌다.

고대 중국 수학에서는 서구권과는 다르게 정수에 딱히 큰 의미를 갖지 않았다. 원론과 비슷하게 동양산학의 기원으로 꼽히는 3세기 경의 구장산술(九章算术)은 체계화된 연립일차방정식과 이차방정식의 해법을 담고 있지만 정수해만을 취급하진 않는다. 방정식의 이름 '방정(方程)'이 이 구장산술 8장의 이름에서 따온 것으로, 계수들을 정방형으로(지금으로 치면 행렬처럼) 써놓고 풀었다고 해서 붙여졌다고 한다. 다만 이 구장산술에서도 다량의 정수 부정방정식 문제가 등장하는데, 모두 실제로 정수해가 필요할 물류와 상거래에 관한 문제들이다. 요즘 말하는 정수계획법 느낌의 실용적인 문제를 중요시한 것으로 보인다. 그래 물론 체계적으로 방정식을 분류하고 그러진 않았고, 이후에도 중화권의 수학은 일반적 분수/소수, 실수로의 근사를 생각하는 수치해법 쪽으로 주로 발전하여 정수방정식과는 영영 멀어진다.

디오판토스 방정식이 다시 유럽 수학의 주무대에 등장한 것은 디오판토스의 '산학' 책이 프랑스의 어느 법률가한테 들어가고 나서일 것이다. 페르마가 '산학'에서 발굴하고 일반화한 여러 문제들은 당대 수학자들의 어그로관심을 끌어, 비교적 잊혀진 디오판토스 방정식을 거의 부활시켰다고 볼수 있을 수준이었다. 정리된 형태는 아니었지만 페르마의 기여 자체도 엄청난 수준이었다. 오일러라그랑주 대에 이르러선 페르마의 대부분의 문제들을 포함하여, 펠 방정식의 연분수 일반해, 네 제곱수의 합 등 (지금으로 치면 초등정수론 수준의) 많은 디오판토스 방정식의 해법을 수복[5] 및 정립할 수 있었다. 물론 '그 문제'는 여전히 남아있었지만.

그 뒤로는 쿰머의 아이디얼, 디리클레/데데킨트의 대수적 정수 개념 등 대수적 정수론의 역사를 따라간다. 20세기~21세기의 현재 디오판토스 방정식 연구는 대수학, 해석학, 기하학을 망라하는 현대의 모든 수학이 집대성되어 있다고 볼 정도로 거대해졌고, 많은 수학자들이 관심을 갖는 수학계의 중심 분야 중 하나로 간주되고 있다.

3. 풀이

중등과정 및 경시대회에서 몇 가지의 유형이 등장하고는 한다. 체계적으로 공부하려면 대학수학인 정수론이 필요하기 때문에 몇몇 경시대회 학생들은 정수론을 상당히 심화해서 공부하기도 한다.

3.1. 부등식법

부등식을 이용하여 변수의 범위를 좁히는 방법. 부등식을 세울때 미지수의 개수를 줄이고
필요없는 항은 과감히 지워버림으로써 양변중 더 큰쪽을 작게하거나, 더 작은쪽을 크게 만든다.
특별히 a,b,c 가 대칭적인 경우 a<b<c(등호생략) 등의 순서배열이 가능하고 보통의경우 가장작은 a 의 범위를 좁히게 된다.

3.2. 인수분해 및 식의 변형

예를 들면, 다음과 같은 문제를 보자.
"x+y=xyx+y=xy를 만족하는 정수해의 순서쌍 (x,y)(x, y)를 모두 구하여라."
풀이 : 주어진 방정식의 좌변을 전부 이항하면 xyxy=0xy-x-y=0이고, 양변에 1을 더하면 xyxy+1=1xy-x-y+1=1이다.
좌변을 인수분해하면 (x1)(y1)=1(x-1)(y-1)=1이고 x,yx, y가 모두 정수이므로 (x1,y1)=(1,1),(1,1)(x-1, y-1)=(1, 1), (-1, -1)일 수밖에 없다. 즉, (x,y)=(2,2),(0,0)(x, y)=(2, 2), (0, 0)이다.

3.3. 잉여계를 이용하는 방법

정수론에서 이용되는 modmod을 사용한다. 예로는 완전제곱수는 mod4mod 4로는 0또는 1이 될 수밖에 없고, 세 제곱수는 mod9mod 9로 -1, 0, 1 중 하나임 등을 사용한다.
예시 : x23y2=17x^2-3y^2=17를 만족하는 정수해는 존재하지 않음을 보여라.
풀이 : 양변은 mod3mod 3으로 해석해 보면, x2x^22(mod3)2 (mod 3)이 되어야 이는 모순이다. 즉, 이와 같은 부정방정식의 정수해는 존재하지 않는다[6]

3.4. 무한강하법

방정식의 양변이 짝수밖에 나올 수 없다는 사실을 토대로 약분을 무한번 하여도 계속해서 짝수가 나와야함을 통해 답이 0뿐이라는 방법
예시 : x2+y2+z2=x2y2x^2+y^2+z^2=x^2y^2을 만족하는 정수해를 모두 구하여라
풀이 : x,y,zx, y, z가 모두 홀수이면 331(mod4)1 (mod 4)가 되어 모순이고 셋 중 하나가 홀수이면 좌변은 홀수, 우변은 짝수가되어 모순이다. 또한, x,yx, y가 홀수이고 zz가 짝수이면 221(mod4)1 (mod 4)가 되어 모순이다. 거기에 x,yx, y중 하나만 홀수이고 zz가 홀수이면 220(mod4)0 (mod 4)가 되어 또 모순이다.
이 뜻은 곧, x,y,zx, y, z가 모두 짝수이란 말이고, x=2x1,y=2y1,z=2z1x=2x_1, y=2y_1, z=2z_1로 놓으면 x12+y12+z12=22x12y12x_1^2+y_1^2+z_1^2=2^2x_1^2y_1^2이 되어 무한강하법을 사용할 수 있다. 즉, x=y=z=0x=y=z=0이다.

3.5. 타원곡선

[math(y^2 = ax^3 + bx + c)] 꼴로 정리한 뒤 푸는 방법. 3차 이상의 디오판토스 방정식에서 사용하는 방법이다.

이 외에도 부등식을 사용하는 방법 또한 있다().

4. 관련 문서


[1] 에르되시 번호가 2이다![2] 이 문제의 가장 작은 해는 자그마치 80자리나 되는 숫자. 덧붙여서 우변의 상수항 값이 클수록 해의 자릿수가 눈덩이처럼 불어난다는 사실까지 밝혀냈다. 가령 4 대신 178을 대입해봤더니 거의 4억에 육박하는 자릿수가 튀어나왔다고 한다.[3]버츠와 스위너톤-다이어 추측 같은 문제가 수백만개씩이나 있다는 뜻이다.[4] 고대 이집트인들에게 분수는 2/3을 제외고는 모두 단위분수(분자가 1인 분수)였다. 1923=118+154\frac{1}{9} \cdot \frac{2}{3} = \frac{1}{18}+\frac{1}{54} 이런 식의 계산이 일상적이었던 것.[5] 중세 인도와 아라비아에서 정수론이 어느 수준까지 발전했는지는 분명하지 않다. 6세기 경 브라마굽타가 x261y2=1x^2-61y^2=1의 (1,0)이 아닌 정수해를 찾았다고 전하기는 하지만 그것이 일반적인 방법인지는 알 수 없다. 어찌되었건 이러한 업적들이 근대 유럽의 수학자들에게는 전달되지 않은 것으로 보인다. 중국인의 나머지 정리 같은 경우도 처음에는 오일러가 발견했다고 생각했으니.[6] 사실 이부분은 정수론을 많이 접해본 이가 아니면 알기 어렵다.