2006 China TST (정수)

 

문제 1.  \( n | (a+1)^n-a^n \)을 만족하는 양의 정수 순서쌍 \((a, n)\)을 모두 찾아라.

[2006 China TST]

 

풀이)

\(n>1\)이라고 하자. 

\(p\)를 \(n\)을 나누는 최소 소인수라 하자. 만약 \(p|a+1\) 또는 \(p|a\)라면 모두를 나누게 되어 모순이다. 

따라서 \(\textup{gcd}(p,a)=\textup{gcd}(p,a+1)=1\)이다. 

즉, \( \textup{mod}\; p\)에 대해 \(a\)의 역원 \(b\)가 존재한다. 

따라서 다음 식을 얻는다. 

$$ (a+1)^n\equiv a^n (\textup{mod} \;p) \to (b+1)^n\equiv (ab+b)^n\equiv (ab)^n\equiv 1(\textup{mod} \;p)  $$

이제 \(n | (b+1)^n-1\)을 만족하는 \((b,n)\)을 찾아보자.

\(r=\textup{ord}_p(b+1)\)이라 하자. 위수의 성질에 의해, \(r|n\)이고, 페르마 소정리에 의해, \(r|p-1\)이다.

따라서 \(r|\textup{gcd}(n,p-1)\)이다. (by 베주 항등식)

이 때, \(p\)가 \(n\)의 최소소인수로 잡았으므로, \(\textup{gcd}(n,p-1)=1\)이다.

(참고: \(\textup{gcd}(n, p-1)=k>1\)라면, \(k<p\)이고 \(k|n\)이므로 \(k\)의 소인수가 \(p\)보다 작아지므로 최소성에 모순!)

즉 \(r=1\)이 되어 \(b\equiv 0 (\textup{mod} \;p) \) 이 되어 역원의 존재성에 모순이다.

따라서 \(n\)을 나누는 소수는 존재하지 않으므로, 이러한 \(n=1\)뿐이다. 

또한 \(n=1\)일 때 모든 양의 정수 \(a\)에 대해 식이 잘 성립하므로, 모든 해는 \((k,1)\)꼴이다. (단, \(k\)는 양의 정수)