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

2021年8月17日07:20:30 发表评论 77 views

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

今天我们就用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,这个比较好理解。

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

 

运行结果:

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

 

2、费马小定理形式二

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

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

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

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

五、测试与改进

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

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

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

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

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

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

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

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: