关于费马小定理的一个奇妙的组合证明

费马小定理：

已知：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整除。            

证毕