Vieta Jumping

Vieta Jumping은 꽤 난도가 높아 보이는 수올 문제들에서 종종 보이는 테크닉이다. 아니 사실 나한테만 어렵지 현역 수올러들은 되게 잘 쓰는 것 같다. 주로 이변수 대칭 이차식의 정수해를 bound 시킬 때 쓰인다. 이렇게 말해봐야 이해하는 데 도움이 되지 않으니, 아래의 예시를 따라오면서 감을 잡는 것을 권장한다.

---

Problem 1. (IMO '88 #6)

음 아닌 정수 \(a,b\)가 \(ab+1 | a^2+b^2\)를 만족할 때, \(k = \frac{a^2+b^2}{ab+1} \)은 완전제곱수임을 보여라.

우선 \(b = 0\)인 경우는 \(k = a^2\)이 되어 완전제곱수가 됨을 알 수 있다.

fixed \(k\)에 대해 \(S := \{ (a,b) | a \ge b, \ \frac{a^2+b^2}{ab+1} = k \} \)라 하자.

이 때 \(S = \emptyset\)인 경우는 전혀 중요하지 않고, 

\(S \neq \emptyset\)이라면 정렬성의 원리에 의해 \(A+B\)가 최소가 되는 \((A,B) \in S\)를 잡을 수 있다.

이 때 주어진 식인 \( A^2 + B^2 = k(AB+1) \)을 이차방정식처럼 해석하자. 즉, \(A\)를 이차방정식 \(x^2 - kBx + B^2 - k = 0\)의 한 해로 보는 것이다.

그렇다면 주어진 방정식의 또다른 해 \(t\)가 존재할 것인데, Vieta's theorem (근과 계수와의 관계)^[각주:1] 에 의해 다음 두 식이 성립한다.

$$ t = kB-A \cdots (1)$$

$$ t = \frac{B^2-k}{A} \cdots (2) $$

(1)에 의해 \(t\)는 정수인데, 

만약 \(t = 0\)일 경우 방정식에 \(t = 0\)을 대입하면 \(k = B^2\)이 되어 \(k\)가 완전제곱수가 된다.

\(t < 0\)일 경우에는 

\(t^2 - kBt + B^2 - k \ge t^2 + k + B^2 - k \ge t^2 + B^2 > 0\)이므로 모순.

그리고 \(t > 0\)인 경우에는 \(  t = \frac{B^2 - k}{A} \le \frac{A^2 - k}{A} < A \)인데, \((t,B) \text{ or } (B,t) \in S\)인데 \(t + B < A + B\)이므로 \(A+B\)가 최소라는 가정에 모순이 된다. 따라서 \(k\)는 완전제곱수일 수밖에 없다. \(\blacksquare\)

---

Problem #2. (IMO)

자연수 \(x,y\)가 \(\frac{x^2+y^2+1}{xy} = k \in \mathbb{Z}\)를 만족할 때, \(k = 3\)임을 보여라.

*2021.01.03 UPD. 틀린 부분이 발견되어 증명을 전체적으로 교체하였다.

우선 \(x = y\)인 경우 \( k = 2 + \frac{1}{x^2}\)이므로 가능한 \(k\)는 3 뿐임을 머리에 넣어두자.

마찬가지로 고정된 \(k\)에 대해 \(S := \{ (x,y) | x, y > 0, \ \frac{x^2+y^2+1}{xy} = k \} \) 라고 정의하자. \(S\)가 공집합이 아닌 경우, \(X+Y\)가 최소가 되는 \((X,Y) \in S\)를, 이중에서도 \(X \ge Y\)를 만족하는 것을 잡자.

그리고 \(X,Z\)를 방정식 \(x^2 - kY x + Y^2 + 1 = 0\)의 해라고 두면 마찬가지로 \(Z = kY - X, \ \ ZX = Y^2 + 1\)을 얻을 수 있다.

두 조건에 의해 자명히 \(Z\)는 양의 정수가 되어야 한다.

이 때 \(Z \ge X\)인 경우 \(X^2 \le ZX = Y^2 + 1\)이 되므로 \(X = Y\)여야만 함을 알 수 있고, 이 경우 가능한 \(k\)의 값은 \(k = 3\)뿐이다.

따라서 \(0 < Z < X\)인 경우를 보면 되는데, 이는 \(X+Y\)의 최소성에 모순. 

따라서 \(k\)로 가능한 값은 3뿐이다. \(\blacksquare\)

---

Problem #3. (IMO '07)

자연수 \(a,b\)가 \(\frac{(4a^2-1)^2}{4ab-1} = k \in \mathbb{Z}\)를 만족할 때, \(a = b\)임을 보여라.

음... 그냥 바로 비에타로 때려박으라고 준 문제는 아닌 것 같다. 일단 4차식이기 때문에 그대로 분모를 양변에 곱해봤자 아무것도 안 나온다. 이 때는 아래와 같이 차수를 내려주면 된다. 나는 문제 밑의 풀이를 보임당하는 바람에 생각할 틈조차 없었는데, 어차피 이걸 읽을 사람들은 나보다 똑똑할테니 생각할 수 있겠지...

$$ \color{red}{4ab-1} \ | \ \color{red}{(16a^4-8a^2+1)} \cdot b^2 - \color{red}{(4ab-1)} \cdot (4a^3b +2ab - a^2) = a^2 - 2ab + b^2 = (a-b)^2 $$

뒤는 너무나 쉬운 Vieta Jumping 문제이니 연습문제로 남긴다. 

---

사실 이렇게 무한 강하법으로 해의 bound를 잡는 것 이외에도 해를 생성해서 정수해의 무한성을 보이는 때에도 썼던 것 같기는 한데, 수올을 접은 지가 벌써 2년이라 기억도 나지 않는다. 기억나면 추가하는 걸로.

1. 이렇게 근과 계수와의 관계를 이용하는 것 때문에 이 테크닉의 이름을 Vieta Jumping이라고 한다. [본문으로]