2006 China TST (정수)

 

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

[2006 China TST]

 

풀이)

$n>1$이라고 하자. 

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

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

즉, $\text{mod}p$에 대해 $a$의 역원 $b$가 존재한다. 

따라서 다음 식을 얻는다. 

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

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

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

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

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

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

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

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

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