費馬小定理證明

　　火車上看的一篇文章。寫得真是簡單易懂。

（選自《數論妙趣——數學女王的盛情款待》第六章　開門咒）

　　費馬小定理有多種證法，以同餘證法最為簡短而精緻。

　　任意取一個質數，比如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，乘積就是312×12！。對于模13來說，這兩個乘積都同餘于1,2,3,„,12系列，盡管順序不是一一對應，即312×12！≡12！mod 13。兩邊同時除以12！得312≡1 mod 13。如果用p代替13，用x代替3，就得到費馬小定理

xp－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同餘 ，隻是順序不同了 ）。

　　是以312×12！≡12！mod 13。

費馬小定律可以快速求得x關于p的逆。前提是x與p互質。

x*xp-2 ≡1 mod p

是以xp-2就是x關于p的乘法逆元。

┆涼┆暖┆降┆等┆幸┆我┆我┆裡┆将┆　┆可┆有┆謙┆戮┆那┆　┆大┆始┆　┆然┆

┆薄┆一┆臨┆你┆的┆還┆沒┆　┆來┆　┆是┆來┆遜┆沒┆些┆　┆雁┆終┆　┆而┆

┆　┆暖┆　┆如┆地┆站┆有┆　┆也┆　┆我┆　┆的┆有┆精┆　┆也┆沒┆　┆你┆

┆　┆這┆　┆試┆方┆在┆逃┆　┆會┆　┆在┆　┆清┆來┆準┆　┆沒┆有┆　┆沒┆

┆　┆生┆　┆探┆　┆最┆避┆　┆在┆　┆這┆　┆晨┆　┆的┆　┆有┆來┆　┆有┆

┆　┆之┆　┆般┆　┆不┆　┆　┆這┆　┆裡┆　┆沒┆　┆殺┆　┆來┆　┆　┆來┆