不同余数的个数

longzaifei

求$ 1^{2013},2^{2013},......,2013^{2013} $除以 $2013 $ ,得到的不同余数的个数。

tommywong

问题是怎么知道61少了16...吗

（更正：61少了40）

tommywong

bbs.emath.ac.cn/forum.php?mod=viewthread&tid=5822#lastpost

$3\times 11\times 21=693$

tommywong

那边推出公式了

$\displaystyle \frac{\varphi(p^k)}{(\varphi(p^k),m)}+\frac{\varphi(p^{k-m})}{(\varphi(p^{k-m}),m)}+\frac{\varphi(p^{k-2m})}{(\varphi(p^{k-2m}),m)}+...+1$

$\displaystyle \frac{\varphi(3)}{(\varphi(3),1)}+1=3$

$\displaystyle \frac{\varphi(11)}{(\varphi(11),3)}+1=11$

$\displaystyle \frac{\varphi(61)}{(\varphi(61),33)}+1=21$

tommywong

在东论有证明了。
bbs.cnool.net/cthread-105405736.html