费马小定理是数学竞赛生的必学内容，在数论题目中应用十分广泛。 a^(p-1) ≡1（mod p）,若（a,p)=1且p为素数。我们的证法是构造素数p的完系P={1,2,3,4…（p-1)}和A={a,2a,3a,4a，…（p-1)a}，令W=1*2*3*4…*(p-1），Y=a*2a*3a*4a*…（p-1)a，则a*2a*3a*…（p-1)a≡1*2*3*…（p-1)(mod p），即W*a^(p-1）≡W(mod p）。易知（W,p)=1，故a^(p-1）≡1(mod p）。
但当我翻开《组合几何》第一页时，几行字让我眼前一亮：
“找到一个‘几何’模型，它的计数结果是有（a^p-a)/p种，其中a,p分别是一个正整数和一个素数，这样就顺便把费马小定理给证明了。”
哦，香雪！数论定理居然还能用组合计数的方法来证！虽说数学竞赛是先学数论再学组合，但一般情况，组合计数对于数论定理来说绝对是小儿科。于是我想了一想，果真想出了一种证明方法：
有a种颜色的扇形石砖，形状完全相同，每种颜色的石砖都足够多。现在要围一个有p块石砖的圆形花坛，问花坛能围几种？其中p为素数。
首先，每块石砖能在a种颜色中选择，应是a^p种，但是，花坛是圆的，把一种花坛旋转一下跟原来没有什么区别，但我们却计算了p次，当然，所有石砖都是同样颜色的情况没有多算，因此，真正的围法数目是：（a^p-a)/p+a。
其中，p为素数，是不可或缺的条件。否则围法数目仍会出现多算的情况。
等等！我们证明的并不是费马小定理，而是p|a^p-a。不过这个问题很好解决，加上（a,p)=1的条件，就可以直接推出费马小定理。
The end.
但当我翻开《组合几何》第一页时，几行字让我眼前一亮：
“找到一个‘几何’模型，它的计数结果是有（a^p-a)/p种，其中a,p分别是一个正整数和一个素数，这样就顺便把费马小定理给证明了。”
哦，香雪！数论定理居然还能用组合计数的方法来证！虽说数学竞赛是先学数论再学组合，但一般情况，组合计数对于数论定理来说绝对是小儿科。于是我想了一想，果真想出了一种证明方法：
有a种颜色的扇形石砖，形状完全相同，每种颜色的石砖都足够多。现在要围一个有p块石砖的圆形花坛，问花坛能围几种？其中p为素数。
首先，每块石砖能在a种颜色中选择，应是a^p种，但是，花坛是圆的，把一种花坛旋转一下跟原来没有什么区别，但我们却计算了p次，当然，所有石砖都是同样颜色的情况没有多算，因此，真正的围法数目是：（a^p-a)/p+a。
其中，p为素数，是不可或缺的条件。否则围法数目仍会出现多算的情况。
等等！我们证明的并不是费马小定理，而是p|a^p-a。不过这个问题很好解决，加上（a,p)=1的条件，就可以直接推出费马小定理。
The end.
