欧拉定理的Python简单验证

王德贵

在数论中，欧拉定理（Euler Theorem），也称费马-欧拉定理或欧拉函数定理，是一个关于同余性质的定理，它也是数论四大定理（威尔逊定理、费马小定理、孙子定理、欧拉定理）之一。

数学史上公认的4名最伟大的数学家分别是：阿基米德、牛顿、欧拉和高斯。阿基米德有“撬起地球”的豪言壯语，牛顿因为苹果闻名世界，高斯少年时就显露出计算天赋，唯独欧拉没有戏剧性的故事却让人印象深刻。

然而，几乎每一个数学领域都可以看到欧拉的名字——初等几何的欧拉线、多面体的欧拉定理、立体解析几何的欧拉变换公式、数论的欧拉函数、变分法的欧拉方程、复变函数的欧拉公式……欧拉还是数学史上最多产的数学家，他一生写下886本书籍论文，平均每年写出800多页，彼得堡科学院为了整理他的著作，足足忙碌了47年。他的著作《无穷小分析引论》《微分学》《积分学》是18世纪欧洲标准的微积分教科书。欧拉还创造了一批数学符号，如f（x）、Σ、i、e等等，使得数学更容易表述、推广，欧拉是18世纪数学界最杰出的人物之一。并且欧拉把整个数学推至物理的领域，此外还涉及建筑学、弹道学、航海学等领域。

对正整数x，欧拉函数是小于x的正整数中与x互质的数的数目。求法通式为（图1）：

x （1 - 1/p1）* … * （1 - 1/pn）。其中p1， p2……pn为x的所有质因数，x是不为0的整数。φ（1）=1[唯一和1互质的数（小于等于1）就是1本身]。

注意：每种质因数只算一个。 比如12=2*2*3那么φ（12）=12（1-1/2）（1-1/3）=4。

还可以根据定义求解，即统计小于x的所有值中与x互素的个数。当x为素数时，φ（x） = x -1。

其中为欧拉函数，gcd（a，m）求两数最大公约数，如果为1则互素。

特别是当m为素数时，该结论即为费马小定理，因为也称欧拉定理是费马小定理的推广。

基本思路就是根先输入n和a，并判断是否互素，然后用定义法和通式法求出欧拉函数值，计算幂，求模后判断，如果为1，则欧拉定理成立。

程序设计涉及到的是等级考试四级或二级内容。

1.输入n和a，并判断是否互素（图3）

2.求欧拉函数值（图4）

3.计算幂，并求模（图5）

4.判断模的值，如果为1，则输出欧拉定理成立（图6）

5.完整程序

为了能循环验证，将所有程序加在循环里面（图7）;

如果输入12和8，则提示非互素，程序返回;输入12和5，输出欧拉定理成立;当输入11和5时，皆为互素，其实就是费马小定理的验证，这里不做赘述，有兴趣的朋友可以参考笔者之前发的文章（图8）。

其实上述这个程序所涉及的知识点是等级考试二级内容。

6.利用自定义函数

这是等级考试四级内容。

从上述程序里，大家看到，判断互素用了两次，所以使用自定义函数应该是更好一些，思路比较清晰（图9）。

这里定义了两个求最大公约数的函数，以此来判断是否互素，一个是递归函数，一个是递推函数，放在一起，便于比较理解。fai（）函数是求欧拉函数值，ouler（）调用fai（）函数求得f值，然后计算a的f次幂，并对n求模。

主程序中判断ouler（）函数返回值，如果为1，则说明欧拉定理成立。

前面我们利用欧拉定理的定义来验证其正确性，而在欧拉函数求法时，前面用的是定义形式，这里还可以用通用式来求欧拉函数值（图10）。

这是自定义函数求欧拉函数值，测试结果与之前相同。大家也可以研究其他编程方法，这里不再讨论。

本文如有不当之处，请各位同仁、朋友斧正。