Python编程案例：简单验证费马小定理

费马小定理也一样享誉数学界，它是初等数论四大定理之一。

今天我们就用Python来简单的验证费马小定理。

一、费马小定理内容

费马小定理是数论中的一个重要定理，在1636年提出。费马小定理是初等数论四大定理（威尔逊定理，欧拉定理（数论中的欧拉定理），中国剩余定理(又称孙子定理），费马小定理）之一，在初等数论中有着非常广泛和重要的应用。实际上，它是欧拉定理的一个特殊情况。

费马小定理可以简述为：

如果p是一个质数，而整数a与p互质，则有a的（p-1）次幂除以p余1。

数学表达式为：

假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）

还有另一种描述的写法：

假如p是质数，a为整数，那么 a^p ≡a（mod p）

有关费马小定理的相关拓展知识这里不做介绍，有兴趣的朋友可以自己去搜索，学习，费马小定理已经被证明，今天我们只做简单验证。

二、创意来源

在探讨费马大定理的时候，就了解了费马小定理，在数论中，都有着重要的地位。在学习Python的时候，这些案例学生也非常感兴趣，因为他们不仅会编程验证，还学到了数学知识，了解了更多数学史。

三、设计思路

在Python编程案例中，主要是生成素数列表，验证输入的值是否为素质，然后计算过程比较简单，基本程序是二级考试内容，自定义函数是四级内容。

四、程序设计

程序设计不是很难，程序如下。

1、费马小定理形式一

首先生成p范围内的质数列表，并判断p是否为质数。如果不是质数，则重新输入，如果是质数，则提示输入a，如果a与p互质，则提示费马小定理成立，运行结果如下。

如果a是p的倍数，则余数为0，即可以整除p，这个比较好理解。

运行结果：

2、费马小定理形式二

费马小定理的另一种形式，我们也来验证一下，程序设计如下。基本思路还是先生成p范围内的所有质数列表，然后判断p是否为质数。

如果p不是质数，重新输入p值。如果p是质数，则提示输入任意整数a，然后进行验证，计算并输出结果。

五、测试与改进

定理的验证测试，就是输入数值直接验证，可以找几个特殊和一般的进行比较一下。也可以在一定范围内，验证。

比如，输入一个质数p，让a在一定范围内验证即可。程序如下。

输入p为质数，再提示输入a的最小值和最大值，然后进行逐一验证，并输出结果。

在输入范围30-40时，依次验证，a与p互质时，费马小定理均成立，而当a=34时，a是p的倍数，余数为0。

费马在提出定理时，还说明了a是一个素数的要求，但是这个要求实际上是不必要的。