n^k-n的最大公因子

wayne

对于所有的整数$n，n^k-n$的最大公因子记为$f(k)$, 求$f(k)$

KeyTo9_Fans

手算前10项，然后拿去OEIS查，结果如下：

http://oeis.org/A141056

mathe

对于f(k)的任意一个素因子p,我们可以取n为p的原根g, 由此得出 $g^{k-1}=1(mod p)$,所以得出$\varphi(p)=p-1|k-1$
反之，对于任意素数如果满足$p-1|k-1$,那么对于任意n显然$n^k\equiv n(mod p)$
另外，对于$p^2$,由于取n=p时, $n^k-n$不是$p^2$的倍数，所以显然$p^2$不是f(k)的因子。
由此得出结论\[f(k)=\prod_{p-1|k-1,p为素数} p\]。