關于費馬小定理的一個奇妙的組合證明

費馬小定理：

已知：p是素數，a是整數且1≤ a ≤ p

求證：a p − a 能被p整除

以下是關于費馬小定理最淺顯易懂的，也是最奇妙的一個證明，叫做Proof by counting bracelets，創始人是Golomb。

證明：假設又一種由p個珠子組成的項鍊，項鍊中珠子的種數為最多為a，那麼所有可能的不重複的排列為a p，其中珠子種數為1的情況有a種，那麼去除這些情況後一共就有a p− a種。現在把所有情況的項鍊首尾相接，那麼就有可能出現重複的情況了。因為p是素數，是以一個包含着p個珠子的環旋轉後會出現p種不同的情況，亦即，這a p− a種情況可以分為一些類，每類有p中情況，亦即，a p − a 能被p整除。            

證畢