정수론 · 디오판토스 방정식

간단한 방정식에 숨은 세계

Simple equations, infinite depth.

정수해만 묻는 방정식을 디오판토스 방정식이라 합니다. 적는 데 한 줄이면 충분한데, 그 안엔 올림피아드의 전설부터 무한히 솟는 해, 나무처럼 가지치는 해, 그리고 358년을 버틴 난제까지 — 깊은 세계가 통째로 들어 있죠. 가장 단순한 식들이 숨긴 가장 깊은 이야기.

1전설이 된 문제 — IMO 1988 6번

1988년 호주에서 열린 국제수학올림피아드(IMO)의 6번 문제는, IMO 역사에서 아직도 전설로 남아 있습니다. 정답률만 따지면 더 어려운 문제도 있지만, 이 문제는 아래 일화 덕에 ‘서사’를 갖춰 그 타이틀을 쉽게 내줄 것 같지 않아요.

IMO 1988 · Problem 6

양의 정수 $a,b$에 대해 $ab+1 \mid a^2+b^2$이라면, $\dfrac{a^2+b^2}{ab+1}$은 완전제곱수임을 보여라.

아서 엥겔은 저서 Problem-Solving Strategies에서 이 문제의 일화를 전합니다. 출제위원회의 수학자 여섯 명이 풀지 못했고, 호주의 정수론학자 네 명에게 6시간을 주었지만 아무도 못 풀었습니다. 그런데도 이들은 문제를 후보에 올리며 ‘아주 어렵다’는 뜻으로 별표 둘(**)을 달았고, 단장 회의를 거쳐 결국 출제됩니다. 그리고 — 고등학생 11명이 이 문제를 풀어냈습니다.

이 문제가 전설인 또 하나의 이유는, 지금도 회자되는 간결한 풀이입니다.

PROOF — 해를 ‘점프’시켜 모순으로

$k=\dfrac{a^2+b^2}{ab+1}$이 정수라 하자. $k$가 완전제곱이 아니라고 가정하고 모순을 이끈다. 식을 정리하면 $a^2 - k\,ab + b^2 - k = 0$. 이 식을 만족하는 양의 정수해 $(a,b)$ 중 $a+b$가 가장 작은 것을 고르고, $a\ge b$라 두자.

$b$를 고정하고 $x^2 - (kb)\,x + (b^2-k)=0$의 근으로 보면, 한 근은 $a$이고 다른 근 $a'$은 근과 계수의 관계로

$$ a' = kb - a = \frac{b^2-k}{a}. $$

$a'=kb-a$는 정수다. 또 $a'\ge 0$이며(음수라면 $a'^2-ka'b+b^2-k>0$이라 모순), $a'=0$이면 $b^2-k=0$ 곧 $k=b^2$로 완전제곱 — 가정에 어긋난다. 따라서 $a'\ge 1$. 그런데 $a'=\dfrac{b^2-k}{a}\le\dfrac{a^2-k}{a}\lt a$이라, $(a',b)$는 더 작은 양의 정수해 — 최소성에 모순. 그러므로 $k$는 완전제곱수다. $\blacksquare$

이렇게 비율을 상수로 고정한 뒤 근과 계수의 관계로 다른 해를 찾아 그쪽으로 ‘점프’하는 방식은, 오늘날 올림피아드 정수론의 정석이 되어 비에타 점프(Vieta jumping)라 불립니다. 두 변수 다항식의 비율이 정수가 될 조건을 묻는 유형에서, 식을 2차 대칭식으로 만들어 점프하는 식이죠.

여담 — 이 문제로 7점 받은 학생은 훗날…

이 문제에서 만점(7점)을 받은 루마니아 학생 니쿠쇼르 단(Nicușor Dan)은 1987·1988년 IMO에서 두 번 연속 42점 만점 금메달을 받았습니다. 이후 파리 고등사범학교(ENS)에서 수학 박사를 받고 루마니아로 돌아와 수학 교수·시민운동가로 활동했고, 부쿠레슈티 시장을 거쳐 2025년 루마니아 대통령으로 선출되었죠.

2비에타 점프로 모든 해를 길어올리다

비에타 점프는 모순을 만드는 데만 쓰는 게 아닙니다. 거꾸로 점프해 해를 키우면, 조건을 만족하는 모든 해를 길어올릴 수 있어요. 깔끔한 예 하나 —

예제

$a^2+b^2+1 = 3ab$를 만족하는 모든 양의 정수 $(a,b)$를 구하라.

$b$를 고정하면 $x^2 - 3b\,x + (b^2+1)=0$, 두 근의 합은 $3b$. 한 해 $(a,b)$에서 다른 근 $3b-a$로 점프하면 또 다른 해가 나오죠. 가장 작은 해 $(1,1)$에서 시작해 점프를 거듭하면 — 놀랍게도 해가 전부 피보나치 수로 떨어집니다: $(1,1),(1,2),(2,5),(5,13),(13,34),\dots$ 즉 $(F_{2k-1},F_{2k+1})$.

해의 사슬 — 점프로 오르내리기

$(a,b)$에서 큰 해는 $(b,\,3b-a)$, 작은 해는 $(3a-b,\,a)$로 점프합니다. 사슬을 오르내려도 늘 $a^2+b^2+1=3ab$가 성립하죠 — 피보나치가 줄줄이 나옵니다.

PROOF — 왜 이게 ‘모든’ 해인가

임의의 양의 정수해 $(a,b)$ (단 $a\ge b$)에서 작은 쪽으로 점프하면 $(b,\,3b-a)$가 나오는데, 새 좌표 $3b-a=\dfrac{b^2+1}{a}$는 늘 양의 정수이고, $b>1$이면 $b$보다 작습니다. 즉 큰 좌표가 매번 엄격히 줄면서도 양수를 유지하니, 이 하강은 반드시 멈추고 — 더는 줄일 수 없는 최소해 $(1,1)$에 도달합니다.

그런데 비에타 점프는 가역(양방향)입니다. $(1,1)$에서 거꾸로 위로 점프하면 그 해가 그대로 다시 나오죠. 따라서 모든 해는 $(1,1)$에서 출발한 단 하나의 사슬 위에 있습니다 — 그 사슬이 곧 위의 피보나치 수열입니다. 사슬 밖의 다른 해는 존재할 수 없습니다. $\blacksquare$

3펠 방정식 — 무한히 솟는 해

가장 유명한 디오판토스 방정식 중 하나는 펠 방정식입니다($D$는 완전제곱이 아닌 양의 정수):

$$ x^2 - D\,y^2 = 1. $$

$D$가 완전제곱이면 시시하지만, 아니면 — 해가 무한히 많습니다. 가장 작은 양의 해(기본해) $(x_1,y_1)$ 하나만 찾으면, 나머지는 전부 $(x_1+y_1\sqrt D)^n$을 전개해 얻어집니다. 신기한 건 기본해의 크기가 $D$에 따라 들쭉날쭉이라는 점 — $D=13$이면 벌써 $(649,180)$이죠. 또 $x/y$는 $\sqrt D$의 최적 유리수 근사(연분수의 수렴값)가 됩니다.

예 — $x^2-3y^2=1$

기본해는 $(2,1)$: $2^2-3\cdot1^2=1$. 비결은 $(2+\sqrt3)(2-\sqrt3)=4-3=1$이라는 것 — 이 곱(노름)이 $1$이니, $n$제곱해도 $(2+\sqrt3)^n(2-\sqrt3)^n=1$, 곧 $x_n^2-3y_n^2=1$이 저절로 성립합니다. 전개하면 $(2+\sqrt3)^2=7+4\sqrt3\to(7,4)$, $(2+\sqrt3)^3=26+15\sqrt3\to(26,15)$, … 무한히 솟죠.

펠 방정식 풀기 — $D$를 골라 보세요

D = 13

기본해에서 $(x_1+y_1\sqrt D)^n$으로 해를 키워 갑니다. $x/y$가 $\sqrt D$로 빠르게 수렴하는 것도 보이죠 — 아르키메데스의 ‘소 떼 문제’도 거대한 $D$의 펠 방정식이었습니다.

4마르코프 방정식 — 한 그루의 나무

이번엔 변수가 셋입니다.

$$ x^2 + y^2 + z^2 = 3xyz. $$

해 $(1,1,1)$에서 출발해 — 여기서도 비에타 점프! 두 변수를 고정하고 나머지를 $z\mapsto 3xy-z$로 점프하면 또 다른 해가 나옵니다. $(1,1,1)\to(1,1,2)\to(1,2,5)\to(1,5,13),(2,5,29)\to\cdots$ 이렇게 모든 해가 하나의 나무(마르코프 트리)에서 가지를 칩니다. 거기 등장하는 수 $1,2,5,13,29,34,89,\dots$가 마르코프 수죠.

마르코프 트리 — 점프가 만드는 나무

뿌리 $(1,1,2)$에서 각 삼중쌍이 $z\mapsto 3xy-z$ 점프로 두 자식을 칩니다. 주황 수가 마르코프 수. 한 줄짜리 방정식의 해가 무한한 나무로 펼쳐집니다.

마르코프 수는 무리수를 유리수로 얼마나 못 근사하는가(라그랑주·마르코프 스펙트럼)와 깊이 얽혀 있고, "가장 큰 원소가 삼중쌍을 유일하게 정하는가?"라는 유일성 추측은 100년 넘게 미해결입니다. 역시, 단순한 식 속의 깊은 세계.

5피타고라스 삼중쌍 — n=2의 무한한 해

페르마로 가기 전에 $n=2$를 봅시다. $a^2+b^2=c^2$의 양의 정수해(피타고라스 삼중쌍)는 $(3,4,5),(5,12,13),\dots$ 무한히 많은데 — 사실 전부 한 공식으로 적힙니다. 서로소인 $m>n\ge1$에 대해

$$ a=m^2-n^2,\quad b=2mn,\quad c=m^2+n^2. $$

이게 모든 (원시) 삼중쌍이라는 건 기하로 보면 환합니다. 양변을 $c^2$으로 나누면 $(a/c)^2+(b/c)^2=1$ — 곧 단위원 위의 유리점 찾기예요. 한 유리점 $(-1,0)$에서 기울기 $t=n/m$인 직선을 그으면, 원과 만나는 다른 교점도 반드시 유리점이 되고(2차식의 두 근 중 하나가 유리수면 다른 하나도), 그게 바로 $\bigl(\tfrac{m^2-n^2}{m^2+n^2},\tfrac{2mn}{m^2+n^2}\bigr)$입니다. 직선 하나가 유리점 하나 — 그래서 해가 무한히 많죠. (이 사영이 $\tan\tfrac\theta2$ 치환의 정체이기도 합니다.)

단위원 위의 유리점 = 피타고라스 삼중쌍

m = 2 n = 1

$(-1,0)$에서 기울기 $n/m$인 직선이 원과 만나는 둘째 점이 유리점 $(a/c,\,b/c)$. 정수로 환산하면 삼중쌍 $(m^2-n^2,\,2mn,\,m^2+n^2)$입니다. $m,n$을 바꿔 점을 원 위에서 옮겨 보세요.

6페르마의 마지막 정리 — 여백이 모자랐던

마지막은, 가장 단순해 보여서 가장 오래 버틴 식입니다.

$$ x^n + y^n = z^n \qquad (n\ge 3). $$

$n=2$면 피타고라스 삼중쌍이 무한히 많습니다($3,4,5$; $5,12,13$; …). 그런데 지수를 $3$으로만 올려도 — 양의 정수해가 단 하나도 없습니다. 1637년 페르마는 책 여백에 "경이로운 증명을 찾았으나 여백이 좁아 못 적는다"는 쪽지를 남겼고, 그 한 줄이 358년의 추적을 낳았죠. 오일러·제르맹·쿠머를 거쳐, 마침내 1994년 앤드루 와일스가 — 타원곡선과 모듈러성(타니야마–시무라)이라는, 여백은커녕 책 한 권으로도 모자란 현대 수학으로 — 증명합니다.

아슬아슬한 헛스윙

$n\ge3$엔 해가 없지만 아깝게 빗나가는 수들은 있습니다. $6^3+8^3=728=9^3-1$, 그리고 라마누잔의 택시 수 $1729=1^3+12^3=9^3+10^3$처럼요. 〈심슨 가족〉엔 $3987^{12}+4365^{12}\approx4472^{12}$ 같은 ‘거의 반례’가 농담으로 등장하기도 했죠 — 계산기 자릿수로는 같아 보이지만, 결코 같지 않습니다.

7무한강하 — 비에타 점프의 조상

페르마 정리 전체는 354년이 걸렸지만, 페르마 자신은 $n=4$를 자기 손으로 증명했습니다. 그가 쓴 무기가 무한강하법 — 그리고 이게 1·2장 비에타 점프의 조상입니다. "해가 있다면 더 작은 해를 만들 수 있다 → 끝없이 작아질 순 없으니 모순"이라는, 바로 그 강하 논법이죠.

정리 (페르마)

$x^4+y^4=z^2$은 양의 정수해가 없다. (따라서 $x^4+y^4=z^4$도 — 곧 $n=4$인 FLT.)

PROOF 뼈대 — 강하

해가 있다면 $z$가 최소인 (서로소) 해 $(x,y,z)$를 잡는다. 그러면 $(x^2,y^2,z)$는 피타고라스 삼중쌍이니, 5장의 매개변수화로 $x^2=m^2-n^2,\ y^2=2mn,\ z=m^2+n^2$. 여기서 $x^2+n^2=m^2$이 또 피타고라스 삼중쌍이 되고, 다시 매개변수화하면 — 더 작은 $z'$을 갖는 새 해가 나온다. $z' \lt z$이라 최소성에 모순. 그러므로 해는 없다. $\blacksquare$

"있다면 더 작은 게 있다"는 이 강하가, 비율을 고정하고 작은 해로 점프하던 비에타 점프와 정확히 같은 심장을 가졌습니다. 올림피아드의 점프와 페르마의 강하는 한 핏줄이었던 거죠.

8타원곡선 — 점을 더하는 곡선

그렇다면 페르마 정리 전체는 어떻게 증명됐을까요? 무대는 타원곡선 — $y^2=x^3+ax+b$ 꼴의 곡선입니다. 놀라운 점은, 이 곡선 위의 점들을 더할 수 있다는 것 — 그것도 현과 접선이라는 작도로요.

두 점 $P,Q$를 잇는 직선은 곡선과 세 번째 점에서 만납니다(3차식이니까). 그 점을 $x$축에 대칭시킨 것을 $P+Q$로 정의하면 — 믿기 어렵게도 이게 결합법칙까지 갖춘 덧셈군이 됩니다. 유리점끼리 더하면 또 유리점이 나오고요.

현과 접선으로 점 더하기 — P + Q

x_P = x_Q =

곡선 $y^2=x^3-x+1$. 두 점 P, Q를 잇는 직선의 셋째 교점 R을 $x$축에 비추면 $P+Q$(초록). 두 $x$를 같게 두면 접선(두 배점)이 됩니다. 이 덧셈군이 정수론의 핵심 도구죠.

모델 정리는 유리점들이 유한개의 생성원으로 다 만들어진다고 말합니다(그 개수가 ‘랭크’). 페르마 증명도 "만약 $a^p+b^p=c^p$의 해가 있다면 너무 괴상해서 존재할 수 없는 타원곡선이 생긴다(모듈러성)"는 길을 통과했고, 합동수 문제(유리 직각삼각형의 넓이가 되는 정수?)도 결국 타원곡선의 랭크로 번역됩니다.

9귀여운 괴물 — 과일 방정식

사과/(바나나+파인애플) + 바나나/(사과+파인애플) + 파인애플/(사과+바나나) = 4, 양의 정수 해를 구하라는 퀴즈 그림

인터넷에 도는 ‘95%는 못 푼다’는 과일 퀴즈가 있습니다. 사과·바나나·파인애플을 $a,b,c$라 하면 —

$$ \frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+b}=4,\qquad a,b,c\in\mathbb{Z}^{+}. $$

얼핏 중학교 분수 문제 같죠. 함정은 양의 정수라는 조건입니다. 음수나 유리수까지 허용하면 쉽지만, 양의 정수만 찾으려 하면 — 이 식은 사실 타원곡선(8장!)이고, 양의 해는 그 곡선 위 무한 위수의 유리점에 대응합니다. 그래서 가장 작은 해조차 손으로는 절대 못 찾아요. 브렘너와 매클라우드(2014)가 밝힌 가장 작은 양의 정수해는 — 무려 80자리가 넘습니다.

🍎 a = 154476802108746166441951315019919837485664325669565431700026634898253202035277999 🍌 b = 36875131794129999827197811565225474825492979968971970996283137471637224634055579 🍍 c = 4373612677928697257861252602371390152816537558161613618621437993378423467772036

오른쪽 값을 $4$ 대신 더 키우면 해의 자릿수는 폭발적으로 늘어, 어떤 경우엔 수십·수백만 자리가 필요합니다. ‘귀여운 한 줄’ 뒤에 타원곡선의 깊은 구조가 통째로 숨어 있던 셈이죠 — 이 페이지 제목 그대로, 간단한 방정식에 숨은 세계의 완벽한 표본입니다.

10힐베르트의 열 번째 문제 — 풀 수 없는 풀이법

마지막 반전. 지금까지 방정식마다 영리한 기법(점프·강하·매개변수화·군)이 필요했죠. 그렇다면 — 아무 디오판토스 방정식이나 받아 정수해가 있는지 없는지 판정하는 만능 알고리즘이 있을까요? 1900년 힐베르트가 스물세 문제 중 열 번째로 던진 질문입니다.

답은 1970년 마티야세비치(데이비스·퍼트넘·로빈슨의 토대 위에서) — 그런 알고리즘은 없다. 디오판토스 방정식의 해 존재 여부는 결정 불가능합니다. 사실 "디오판토스 방정식으로 정의되는 집합"은 "컴퓨터가 나열할 수 있는 집합(재귀열거)"과 정확히 같아서, 튜링 기계의 정지 문제와 한 몸이죠 (계산 이론과 만나는 지점이자, 그 밑바닥엔 칸토어·괴델·튜링을 한데 꿰는 대각선 논법이 깔려 있습니다). 한 줄짜리 식들의 세계엔, 일반적인 ‘풀이법’ 자체가 존재하지 않는다는 뜻입니다.

11맺으며

$\frac{a^2+b^2}{ab+1}$, $x^2-Dy^2=1$, $x^2+y^2+z^2=3xyz$, $x^n+y^n=z^n$ — 넷 다 초등학생도 읽을 수 있는 식입니다. 그런데 그 안에는 올림피아드의 전설, 무한히 솟는 해, 끝없이 가지치는 나무, 그리고 한 시대의 수학을 통째로 동원해야 했던 증명이 들어 있었죠. 디오판토스 방정식의 매력은 바로 이것 — 입구는 한 줄, 안은 우주입니다.

참고 자료

IMO 1988 #6 · 비에타 점프 — A. Engel, Problem-Solving Strategies · Vieta jumping · Nicușor Dan
펠 방정식 — 기본해와 연분수 · Pell's equation
마르코프 방정식 — 마르코프 트리·마르코프 스펙트럼·유일성 추측 · Markov number
페르마의 마지막 정리 — A. Wiles (1994), 타니야마–시무라 모듈러성 · S. Singh, Fermat's Last Theorem