费马小定理

费马小定理设p为素数，a是任意整数，且𝑎≢0(𝑚𝑜𝑑𝑝)，则𝑎𝑝−1≡1(𝑚𝑜𝑑𝑝).证明先来说明一个引理引理设p是素数，a是任何整数，且𝑎≢0(𝑚𝑜𝑑𝑝)，则数列𝑎,2𝑎,3𝑎,…,(𝑝−1)𝑎(𝑚𝑜𝑑𝑝)于数列1,2,3,…,(𝑝−1)(𝑚𝑜𝑑𝑝)相同（忽略次序）。引理证明数列𝑎,2𝑎,3𝑎,…,(𝑝−1)𝑎，含有𝑝−1 个数字。任取两个数𝑗𝑎和𝑘𝑎，假设它们同余：𝑗𝑎≡𝑘𝑎(𝑚𝑜𝑑𝑝)则𝑝|(𝑗−𝑘)𝑎，又因为𝑎≢0(𝑚𝑜𝑑𝑝)，所以𝑝|(𝑗−𝑘)。而1≤𝑗,𝑘≤𝑝−1，则 0≤|𝑗−𝑘|≤𝑞−2，仅有𝑗=𝑘时，𝑝|0。所以，𝑎,2𝑎,3𝑎,…,(𝑝−1)𝑎模p不同余。p-1个数模p不同余，这p-1个余数一定就是1,2,…,𝑝−1。得证。证明费马小定理引理中的两个数列连乘得：𝑎⋅(2𝑎)…⋅(𝑝−1)𝑎≡1⋅2…⋅(𝑝−1)(𝑚𝑜𝑑𝑝)即𝑎𝑝−1(𝑝−1)!≡(𝑝−1)!(𝑚𝑜𝑑𝑝)又有(𝑝−1)!与𝑝互素，两边消掉得𝑎𝑝−1≡1(𝑚𝑜𝑑𝑝)得证。利用费马小定理简单判断一个数是不是质数a可以随便取，比如取2，只要计算出2𝑚−1mod𝑚≠1，那就说明m不是质数。 比如当𝑚=106+7时，2𝑚−1mod𝑚=399097，所以1𝑒6+7不是质数。注意，若 2𝑚−1mod𝑚=1，m不一定是质数