一道数论难题的解答

题目 求所有满足∑_(𝑖=1)^(𝑛)𝑖^(𝑛)≡1(mod𝑛)的正整数𝑛．

引理 对于质数𝑝，有

公式：\sum\limits_{i=1}^{p-1}i^n\equiv \left\{ \begin{array} &p-1,&p-1\mid n\\ 0,&p-1\nmid n \end{array}\right.\ ({\rm{mod}}\ p)

引理的证明 若𝑝−1∣𝑛，则由Fermat小定理：𝑖^(𝑘)≡1(mod𝑝)．故

若𝑝−1∤𝑛，由𝑝是质数知𝑝存在原根𝑔，其满足𝑔^(𝑘)≢1(mod𝑝)．而gcd(𝑔,𝑝)=1，故𝑔,2𝑔,⋯,(𝑝−1)𝑔为模𝑝的一个简系．因此

公式：\sum\limits_{i=1}^{p-1}(ig)^k\equiv\sum\limits_{i=1}^{p-1} i^k({\rm{mod}}\ p)\text{．}

即

公式：\left(g^k-1\right)\sum\limits_{i=1}^{p-1}i^k\equiv 0({\rm{mod}}\ p)\text{．}

回到原题，设𝑆(𝑛)=∑_(𝑖=1)^(𝑛)𝑖^(𝑛)，𝑛为使𝑆(𝑛)≡1(mod𝑛)成立的正整数．设𝑝为𝑛的一个质因子，且𝑛=𝑚𝑝．
则

公式：S(n)=S(mp)=\sum\limits_{i=1}^{mp}i^{mp}\equiv m\sum\limits_{i=0}^{p-1}i^{mp}({\rm{mod}}\ p)\text{．}

所以我们有：若𝑝∣𝑛，则𝑝−1∣𝑛．记为条件一．

若存在质数𝑝，使得𝑝^(2)∣𝑛，设𝑛=𝑚𝑝^(2)．由前面知

公式：S(n)=S(mp^2)\equiv mp\sum\limits_{i=1}^{p-1}i^n\equiv 0({\rm{mod}}\ p)\text{．}

故𝑛中无平方因子．记为条件二．

下面求同时满足条件一和二的所有正整数𝑛，记其集合为𝑋．将𝑋中任意整数的任一质因子称作𝑋-质数．

显然2∈𝑋，且2为𝑋-质数．
容易验证6∈𝑋，故3为𝑋-质数；42∈𝑋，故7为𝑋-质数．

可猜测，若𝑝_(1),𝑝_(2),⋯,𝑝_(𝑘)为𝑋-质数，且∏_(𝑖=1)^(𝑘)𝑝_(𝑖)+1为质数，则∏_(𝑖=1)^(𝑘)𝑝_(𝑖)+1为𝑋-质数．并由此得到4个𝑋-质数：2,3,7,43．这由2,6,42,1806∈𝑋容易证明．

下证只有这4个𝑋-质数，否则存在一个最小的质数𝑦（不同于2,3,7,43）．设𝑦∣𝑥，𝑥∈𝑋．则𝑦−1∣𝑥，且𝑦−1为若干个不同的𝑋-质数之积．
𝑦−1的质因子必小于𝑦，故必为2,3,7,43之一，逐一枚举可得矛盾．故𝑋-质数只有2,3,7,43．

由此可得𝑋={1,2,6,42,1806}．