문제: a, b가 자연수일때 ab + 1이 a^2 + b^2를 나누어떨어지게 하면 그 몫은 제곱수임을 증명하시오


풀이: ab + 1|a^2 + b^2인 (a, b)중 a+b가 최소인 (a, b)를 (A, B)라 하자.(WLOG A ≥ B) 

(A^2 + B^2)/(AB + 1) = k(k는 자연수) 

A^2 - kBA + (B^2 - k) = 0
여기서 A는 이차방정식 x^2 - kBx + B^2 - k = 0의 한 해인데, 다른 해를 C라 하면 근과 계수와의 관계에 의해

C = kB - A (따라서 C는 정수)

C = (B^2 - k)/A

만약 C > 0이라면 C^2 - kBC + B^2 - k = 0이므로 BC + 1|B^2 + C^2, 최소해보다는 커야 하므로
A + B ≤ B+C, A ≤ C
C = (B^2 - k)/A < (AB)/A = B ≤ A이므로 모순.

(근과 계수의 관계를 이용해 새로운 식을 만들어 모순을 이끌어낸다 하여 vieta jumping이라는 이름이 붙었습니다)


만약 C < 0이라면 C는 정수이므로 C ≤ -1

0 = C^2 - kBC + B^2 - k ≥ C^2 + kB + B^2 - k ≥ C^2 + 1 (B ≥ 1)

>0 이므로 모순.


따라서 C = 0이고, (B^2 - k)/A = 0이므로 k = B^2인 제곱수이다.

Q.E.D



문제 자체가 너무 유명해서 아시는분이 모르시는분보다 많겠지만 심심해서 적었습니다