一道数论难题

huhuyang2010

Find the sum of all integers m with 1≤m≤300 such that for any integer n with n≥2, if 2013m divides n^n - 1, then 2013m also divides n - 1.

来自苹果APP客户端

huhuyang2010

先考察普通的M, 即对任意满足M | n^n - 1的n, 也满足M | n - 1, 这样的M有什么特点.
显然(n,M)=1. 对M的任意质因子幂p^k，p^k | n^n -1，(p,n)=1。φ(p^k)=p^(k-1)*(p-1)，设n模p^k的阶为e，则有e | p^(k-1)*(p-1), e | n => e | GCD(p^(k-1)*(p-1),n)。如果(p-1,n) = 1, 则e=1, p^k | n - 1，进而M | n - 1. 所以关键是(p-1,n)=1是否成立!
猜想对M的任意质数p, p-1的所有质因子也是M的因子. 由上面分析, 这是充分条件. 接下来证明也是必要条件.
反证法，假设M有一个质因子p，使得p-1的某个质因子q不是M的因子，设置p-1 = q^a*Q. q不整除M.
设g是p^k的原根，g^(p^(k-1)*(p-1)) ≡ 1 (mod p^k).
构造n, 满足:
1） n ≡ 0 (mod q^a)
2)   n ≡ g^(p^(k-1)*Q) ≠ 1 (mod p^k), 原根性质
3)   n ≡ 1 (mod pi^ki), pi是M除p以外的其他质因子
由中国剩余定理可知这样的n一定存在！
n^n ≡ (g^(p^(k-1)*Q))^n ≡  (g^(p^(k-1)*Q*g^a))^(n/q^a)  ≡ 1 (mod p^k)
n^n  ≡ 1 (mod  pi^ki)
所以 n^n  ≡ 1 (mod M), 但 n -1 ≠ 0 (mod p^k) 与 M | n-1矛盾.

2013 = 3*11*61, 所以有2 | m, 5 | m, m是10的倍数(10,20,...,300). 经验证m=290不满足, 其他均满足上面的条件, sum=4360.

这题有XMO水准(X=C, CG, I, USA, EG, O...).