费马小定理

1. 定义

假如 a{\displaystyle a} 是一个整数,p{\displaystyle p}是一个质数,那么 apa{\displaystyle a^{p}-a}pp 的倍数,可以表示为

apa(modp)\begin{array}{c} a^p \equiv a \,\, (mod \,\, p) \end{array}

如果 aa 不是 pp 的倍数,这个定理也可以写成

ap11(modp)\begin{array}{c} a^{p-1} \equiv 1 \,\, (mod \,\, p) \end{array}

2. 证明

  • 对于 a=0a = 0 的情况,定义中的第一个等式显然成立。
  • 对于 a0a \ne 0 的情况,则 (a,p)=1(a,p) = 1。此时模 pp 的所有非零的余数,在同于意义下对乘法构成一个群,此群的阶是 p1p-1。根据群论中的拉格朗日定理,对于该群中的 x\forall x,都有 xx 的阶必整除群的阶,故命题得证。

3. 推广

  • 费马小定理是欧拉定理的一个特殊情况。
  • 卡迈克尔函数比欧拉函数更小,费马小定理也是它的特殊情况。它的特殊情况。

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!