Algorithm, 未分类费马小定理

费马小定理

定理内容

若p是质数,且gcd(a, p) = 1,那么

a^{p-1}\\equiv 1(mod p)

证明

我们考虑从1至p的所有整数{1,2,……,p-1,p}

将其中每一项乘上一个与p互质的数x,得到{x,2x,……,(p-1)x,px}

由于p和x互质,那么这些数同余于{1,2,……,p-1,p}

A = 1\\times 2\\times \\cdots\\times(p-1)\\times p,B = x\\times 2x\\times \\cdots\\times(p-1)x\\times px

那么易知B\\equiv A(mod p)

又因为A = (p-1)! ,B = x^{p-1}\\times (p-1)!

两边同时约去(p-1)!得到x^{p-1}\\equiv 1(mod p)

Categories: Algorithm, 未分类 Tags: ,

Comments

  1. 2017年9月13日 下午11:46

    完全剩余系的写法应该是 $$\forall x, x\ mod\ p \belong \{ 0, ..., p - 1 \}$$
    1. huangkui

      2017年9月21日 下午8:06

      我这里怎么显示不出来

Post a comment