2018-04-11 Vaniot
费马小定理(Fermat's little theorem) 费马小定理:假假如a是整数,p是质数,且a,p互质(即两者只有一个公约数1),那么a的(p-1)次方除以p的余数恒等于1。即$a^{p}\equiv a{\pmod {p}}$ more 证明: 法一: gcd(a,p)=1,将$1\cdot a,2\cdot a,....(p-1)\cdot a$共(p-1)个数,将他们分别除以p,余数分别为$r_{1},r_{2}......r_{p-1}$,则集合{$r_{1},r_{2}......r_{p-1}$}为{1,2,3...(p-1)}的重排列,即1,2,3,....,(p-1)在余数中恰好各出现一次,(对于 继续阅读 »