費馬小定理

命題：

若p是質數且p不能整除a，則a^p-1=1(mod p)。

證明：

列出a的首(p-1)個質數：

a,2a,3a, ... ,(p-1)a

若有二數ra和sa(r, s＜1)使得ra = sa (mod p)，則r = s (mod p)。因此，我們不可能找到這樣的r和s。由此可得a的首(p-1)個倍數是非零且每個也不同，進而得到這(p-1)個數除以p後的餘數分別是1,2,...(p-1)。把這(n-1)個數乘起來，得到：

a ^. 2a ^. 3a ^. ... ^. (p-1) a  =  1 ^. 2 ^. 3 ^. ... ^. (p-1)  (mod p)

簡化後得到

a^p-1(p-1)!  =  (p-1)! (mod p)

把兩邊都除以(p-1)!，證畢。

註：1.由此我們亦可以得到：

       若p為一質數，而a為任何一整數，則有：

a^p=a (mod p)

       證明：

       若a是p的倍數，則可設a = kp，(kp)^p = 0 (mod p)，kp = 0 (mod p)，命題成立。

       否則可將費馬小定理兩邊乘上a，命題亦成立。