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

费马小定理也一样享誉数学界，它是初等数论四大定理之一。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

今天我们就用Python来简单的验证费马小定理。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

一、费马小定理内容文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

费马小定理是数论中的一个重要定理，在1636年提出。费马小定理是初等数论四大定理（威尔逊定理，欧拉定理（数论中的欧拉定理），中国剩余定理(又称孙子定理），费马小定理）之一，在初等数论中有着非常广泛和重要的应用。实际上，它是欧拉定理的一个特殊情况。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

费马小定理可以简述为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

如果p是一个质数，而整数a与p互质，则有a的（p-1）次幂除以p余1。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

数学表达式为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

还有另一种描述的写法：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

假如p是质数，a为整数，那么 a^p ≡a（mod p）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

有关费马小定理的相关拓展知识这里不做介绍，有兴趣的朋友可以自己去搜索，学习，费马小定理已经被证明，今天我们只做简单验证。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

二、创意来源文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

在探讨费马大定理的时候，就了解了费马小定理，在数论中，都有着重要的地位。在学习Python的时候，这些案例学生也非常感兴趣，因为他们不仅会编程验证，还学到了数学知识，了解了更多数学史。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

三、设计思路文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

在Python编程案例中，主要是生成素数列表，验证输入的值是否为素质，然后计算过程比较简单，基本程序是二级考试内容，自定义函数是四级内容。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

四、程序设计文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

程序设计不是很难，程序如下。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

1、费马小定理形式一文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

首先生成p范围内的质数列表，并判断p是否为质数。如果不是质数，则重新输入，如果是质数，则提示输入a，如果a与p互质，则提示费马小定理成立，运行结果如下。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

如果a是p的倍数，则余数为0，即可以整除p，这个比较好理解。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

运行结果：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

2、费马小定理形式二文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

费马小定理的另一种形式，我们也来验证一下，程序设计如下。基本思路还是先生成p范围内的所有质数列表，然后判断p是否为质数。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

如果p不是质数，重新输入p值。如果p是质数，则提示输入任意整数a，然后进行验证，计算并输出结果。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

五、测试与改进文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

定理的验证测试，就是输入数值直接验证，可以找几个特殊和一般的进行比较一下。也可以在一定范围内，验证。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

比如，输入一个质数p，让a在一定范围内验证即可。程序如下。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

输入p为质数，再提示输入a的最小值和最大值，然后进行逐一验证，并输出结果。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

在输入范围30-40时，依次验证，a与p互质时，费马小定理均成立，而当a=34时，a是p的倍数，余数为0。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html

费马在提出定理时，还说明了a是一个素数的要求，但是这个要求实际上是不必要的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/22007.html