[문제 풀이] IMO 2024 문제 2.

다음 조건을 만족하는 양의 정수 $g$와 $N$이 존재하는 양의 정수 순서쌍 $(a,b)$를 모두 구하시오.

(조건) 모든 정수 $n\ge N$에 대해 $\gcd(a^n+b,b^n+a)=g$이다.

(단, $\gcd(x,y)$는 두 정수 $x,y$의 최대공약수이다.)

---

$(a,b)$가 조건을 만족할 때, 수열 $x_n=\gcd(a^n+b,b^n+a)$를 생각해 보죠. $a$와 $b$에 동시에 서로소인 $ab+1$에 대해 $\ph(ab+1)|n$이라면 $a^n\equiv b^n\equiv1\pmod{ab+1}$이 성립해요. ($\ph(m)$은 양의 정수 $m$에 대해 그보다 작은 서로소 개수를 의미해요.) 이 내용이 유명한 오일러의 정리 Euler's theorem죠. 자세한 증명은 나중에 기회가 있으면 다루기로 할게요.

동시에 $n>N$이 성립한다고 가정할 수 있죠. $x_{n-1}$에 대해 살펴보면,\[a\p{a^{n-1}+b}=a^n+ab\equiv1-1=0\pmod{ab+1}\]이고 비슷하게 $b\p{b^{n-1}+a}\equiv0\pmod{ab+1}$이기에 $x_{n-1}\equiv0\pmod{ab+1}$이 성립해요.

$n>N$으로부터 $g=x_{n-1}=x_n=x_{n+1}=\cdots$가 성립하고, $x_n$에 대해 살펴보면, $0\equiv a^n+b\equiv1+b\pmod{ab+1}$과 $0\equiv b^n+a\equiv1+a\pmod{ab+1}$로부터 $a\equiv b\equiv-1\pmod{ab+1}$이라는 걸 알 수 있죠.

마지막으로 $x_{n+1}$에 대해 살펴보면,\[0\equiv a^{n+1}+b\equiv b^{n+1}+a\equiv a+b\pmod{ab+1}\]이기에 $a\equiv b\equiv-1\pmod{ab+1}$로부터 $0\equiv2\pmod{ab+1}$, 즉, $ab+1=2$라는 걸 알 수 있어요. $a$와 $b$는 양의 정수이기에 $a=b=1$이죠.