디오판토스 방정식

정수해만 찾는 방정식을 디오판토스 방정식이라 한다. 일차 방정식은 완전히 풀리지만, 차수가 올라가면 매우 어려워진다. 페르마의 마지막 정리 $x^n+y^n=z^n$ ($n\ge3$)은 350년 만인 1994년에 와일스가 증명했다.

핵심 개념

  • 일차 부정방정식 $ax+by=c$: $\gcd(a,b)\mid c$일 때만 정수해가 있다. 한 해 $(x_0,y_0)$이 있으면 일반해는 $x=x_0+\frac bdt$, $y=y_0-\frac adt$ ($d=\gcd(a,b)$)
  • 피타고라스 세 수: $a^2+b^2=c^2$의 자연수 해. 서로소인 기본 해는 $m>n$, $\gcd(m,n)=1$, $m-n$ 홀수인 $m,n$에 대해 $(m^2-n^2,\ 2mn,\ m^2+n^2)$로 모두 얻어진다.
  • 펠 방정식 $x^2-dy^2=1$: $d$가 제곱수가 아니면 해가 무한히 많다.
a²+b²=c²의 자연수 해를 점으로 찍은 그림
피타고라스 세 수 $(a,b)$. 기본 해(빨강)의 배수들이 원점을 지나는 직선 위에 있다

핵심 정리

  • $(m^2-n^2)^2+(2mn)^2=(m^2+n^2)^2$
  • $x^4+y^4=z^2$은 자연수 해가 없다 (따라서 $n=4$인 페르마의 마지막 정리가 성립한다).
증명 보기

공식 확인. $(m^2-n^2)^2+(2mn)^2=m^4-2m^2n^2+n^4+4m^2n^2=m^4+2m^2n^2+n^4=(m^2+n^2)^2$이다.

모든 기본 해가 이 꼴인 이유. $a^2+b^2=c^2$, $\gcd(a,b)=1$이면 $a,b$ 중 정확히 하나가 짝수이다(둘 다 홀수이면 $a^2+b^2\equiv2\pmod4$인데 제곱수는 $0$ 또는 $1\pmod4$). $b$가 짝수라 하면 $b^2=(c-a)(c+a)$이고, $c-a$와 $c+a$는 모두 짝수이며 $\frac{c-a}2$, $\frac{c+a}2$는 서로소이다. 서로소인 두 수의 곱이 제곱수 $\left(\frac b2\right)^2$이면 각각 제곱수이므로(소인수분해의 유일성) $\frac{c+a}2=m^2$, $\frac{c-a}2=n^2$으로 쓸 수 있고, $a=m^2-n^2$, $c=m^2+n^2$, $b=2mn$이다.

$x^4+y^4=z^2$ (무한강하법, 생각의 흐름). 해가 있다면 $z$가 가장 작은 해를 잡는다. $(x^2)^2+(y^2)^2=z^2$은 피타고라스 세 수이므로 위 공식으로 쓰고, 다시 한 번 피타고라스 세 수의 구조를 쓰면 $z$보다 작은 새로운 해가 만들어진다. 가장 작은 해보다 작은 해가 있을 수 없으므로 모순이다. 페르마 자신이 이 방법을 썼다. $\blacksquare$

예제

  • $6x+9y=20$: $\gcd(6,9)=3\nmid20$이므로 정수해가 없다.
  • $7x+3y=50$의 자연수 해: $x=2$, $y=12$가 한 해이고 일반해는 $x=2+3t$, $y=12-7t$이다. 자연수 조건에서 $t=0,1$, 해는 $(2,12)$, $(5,5)$
  • $m=2,n=1$: $(3,4,5)$, $m=3,n=2$: $(5,12,13)$, $m=4,n=1$: $(15,8,17)$

확인 문제

500원짜리와 700원짜리 물건을 섞어 정확히 6800원어치 사는 방법을 모두 구하시오.

풀이 보기

$500x+700y=6800$, 즉 $5x+7y=68$이다. $y=4$이면 $5x=40$, $x=8$이 한 해이다. 일반해는 $x=8+7t$, $y=4-5t$이다. $x,y\ge0$이려면 $t=0$ 또는 $t=-1$이므로 $(8,4)$, $(1,9)$의 두 가지이다.

정리

  • $ax+by=c$는 $\gcd(a,b)\mid c$일 때 해가 있고, 일반해는 한 해에서 주기적으로 얻는다.
  • 피타고라스 세 수는 $(m^2-n^2,2mn,m^2+n^2)$
알림: 보호된 콘텐츠입니다.