인상 깊었던 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\)을 강제하고, 모순이다.