프로젝트 오일러 142번

Find the smallest \(x+y+z\) with integers \(x>y>z>0\) such that \(x+y\), \(x-y\), \(x+z\), \(x-z\), \(y+z\), \(y-z\) are all perfect squares.

---

\(x>y>z>0\) 을 만족하는 자연수 \(x, \; y\; z\) 에 대해서 \(x+y\), \(x-y\), \(x+z\), \(x-z\), \(y+z\), \(y-z\) 가 모두 완전제곱수가 되는 \(x+y+z\) 의 최솟값을 구하시오. 

늘 그렇듯이 처음엔 무식하게 하나하나 완전제곱수인 것을 모두 확인하는 방법을 사용했지만, 아니나 다를까 시간이 너무 오래 걸린다. 그래서 다음의 방법을 생각 !!

\[x+y=a^2 \label{a}\tag{1}\]

\[x+z=b^2 \label{b}\tag{2}\]

\[y+z=c^2 \label{c}\tag{3}\]

이라고 하자. \(x>y>z\) 이므로 \(a^2 > b^2 > c^2\) 이 된다. (2)-(3) 을 하면 \(x-y\) 를 얻을 수 있고, (1)-(3) 을 하면 \(x-z\)를, (1)-(2)를 하면 \(y-z\) 를 얻을 수 있다.

\[x-y=b^2-c^2 \label{d}\tag{4}\]

\[x-z=a^2-c^2 \label{e}\tag{5}\]

\[y-z=a^2-b^2 \label{f}\tag{6}\]

이제 \(x-y ,\; x-z,\; y-z\) 가 모두 완전제곱수이면 1단계는 통과다. 즉, \(b^2-c^2\), \(a^2-c^2\), \(a^2-b^2\) 이 완전제곱수인지 확인한다.

이제 (1) ~ (6) 식을 적절히 연립하여 \(x, \; y, \;z\) 를 구해낸다.

\[x=\dfrac{a^2+b^2-c^2}{2}\]

\[y=\dfrac{a^2+c^2-b^2}{2}\]

\[z=\dfrac{b^2+c^2-a^2}{2}\]

2단계에서는 \(x, \;y, \;z\) 가 모두 자연수인지 확인하면 된다. 그러기 위해서는 \(a^2+b^2-c^2\), \(a^2+c^2-b^2\), \(b^2+c^2-a^2\) 이 모두 \(2\)의 배수인지 확인하고, \(z>0\) 인지만 확인하면 된다.

이렇게 하면 쉽게 답을 구해낼 수 있다.