인상 깊었던 MO 문제 #5: USA Winter TST 2019 2번

문제

자연수 $n$에 대하여, $\mathbb{Z}/n\mathbb{Z}$는 정수의 집합을 modulo $n$으로 본 것이다. 

다음을 만족하는 함수 $g: \mathbb{Z}/n\mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z}$가 존재하는 자연수 $n$을 모두 구하시오. $$g(x), \quad g(x) + x, \quad g(x) + 2x, \quad \dots, \quad g(x) + 100x$$ 가 모두 $\mathbb{Z}/n\mathbb{Z}$위의 일대일대응 함수이다. 

스포 방지선

_________________________________________________________________________________________________________

___________________________________________________________________________________________________________

답은 $101!$과 서로소인 모든 자연수들이다. $\text{gcd}(n,101!)=1$이라면 $g(x)=x$가 조건을 만족한다.

이제 $\text{gcd}(n,101!)\neq1$이라고 생각하자. $n$의 최소 소인수를 $p$라 하면, $p \le 101$이다.

각 $0 \le k \le p-1$에 대해서, $k \le p-1 \le 100$임을 상기하면 $$\sum_{x} g(x)^k \equiv \sum_{x} (g(x)+x)^k \equiv \sum_{x} (g(x)+2x)^k \equiv \cdots \equiv \sum_{x}(g(x)+kx)^k \equiv \sum_{i=0}^{n-1} i^k \pmod{n}$$ 이다. 각 식에서 더하고 있는 term들에 대한 $k$차 차분을 취하면,  $$\sum_{x} k!x^k \equiv 0 \pmod{n}$$ 을 얻는다. 한편, $p$는 $n$의 최소 소인수이므로 $\text{gcd}(k!,n)=1$이다. 그러니 $$\sum_{x} x^k \equiv 0 \pmod{n}$$ 을 얻는다. 그러므로 $$0 \equiv \sum_{x=1}^n (x-1)\cdots (x-(p-1)) \equiv (p-1)! \sum_{x=1}^n \binom{x-1}{p-1} \equiv (p-1)! \binom{n}{p} \pmod{n}$$ 를 얻을 수 있고, 이는 $n| \binom{n}{p}$를 얻는다. 이는 $p \nmid n$을 강제하고, 모순이다.