费马小定理证明

　　火车上看的一篇文章。写得真是简单易懂。今天发了下学期的书，《离散数学》非常非常“厚塞雷”的教材，全都是英文呐！打开第一眼看到的居然是费马小定理。随便翻了翻，觉得里面可以学到好多有用的知识，挺期待的（但是还是挺可怕的(,,•? . •?,,) ）。

（选自《数论妙趣——数学女王的盛情款待》第六章　开门咒）

　　费马小定理有多种证法，以同余证法最为简短而精致。

　　任意取一个质数，比如13。考虑从1到12的一系列整数1,2,3,4,5,6,7,8,9,10,11,12，给这些数都乘上一个与13互质的数，比如3，得到3,6,9,12,15,18,21,24,27,30,33,36。对于模13来说，这些数同余于3,6,9,12,2,5,8,11,1,4,7,10。这些余数实际上就是原来的1,2,3,4,5,6,7,8,9,10,11,12，只是顺序不同而已。

　　把1,2,3,„,12统统乘起来，乘积就是12的阶乘12！。把3,6,9,„,36也统统乘起来，并且提出公因子3，乘积就是3¹²×12！。对于模13来说，这两个乘积都同余于1,2,3,„,12系列，尽管顺序不是一一对应，即3¹²×12！≡12！mod 13。两边同时除以12！得3¹²≡1 mod 13。如果用p代替13，用x代替3，就得到费马小定理

x^p－1≡1 mod p。

我自己解释一遍(..•?_?•..)就是：

　　1*2*..*12 ≡ 3*6*9*12*2*5*8*11*1*4*7*10 mod 13 （因为顺序不同而已）

　　而3*6*9*12*15*18*21*24*27*30*33*36 ≡ 3*6*9*12*2*5*8*11*1*4*7*10 mod 13 （因为3和13互质，所以1，2，.. 12 乘上3后还是和13互质，12个数还是和1到12同余 ，只是顺序不同了 ）。

　　所以3¹²×12！≡12！mod 13。

费马小定律可以快速求得x关于p的逆。前提是x与p互质。

费马小定理证明

原文：http://www.cnblogs.com/flipped/p/5218037.html