数论算法编程之欧拉函数与欧拉定理的理论证明

本文来讲数论中欧拉函数的理论及相关定理的证明，编程实现求一个正整数的欧拉函数值，并给出欧拉定理的证明。

一. 欧拉函数认识

欧拉函数的定义非常简单，如下描述

对于正整数n，欧拉函数值是小于等于n的正整数中与n互质的数的数量，记为Φ(n)

例如对于正整数8来说，小于等于它且与它互质的数有1,3,5,7这四个数，所以Φ(8)=4。下面来看几个关于欧拉函数的定理。

定理一：若正整数n为素数，有Φ(n)=n-1。

证明：根据定义可以知道，如果n是一个素数，那么小于n的所有正整数都与它互质，那么欧拉函数值为n-1，即Φ(n)=n-1。

定理二：若正整数n是质数p的k次幂，则有

证明：当正整数n可以表示为质数p的k次幂，那么除了p的倍数外，其它的数都与n互质，n以内满足p的倍数的数一共有n/p个，所以有

定理三：对于两个互质的正整数m和n，有Φ(mn)=Φ(m)Φ(n)。

证明：即证明欧拉函数是积性函数，先来看nm以内的数构造的m*n的矩阵，如下

先来按行看，对第一行来说m的欧拉函数值为Φ(m)，其实每行的数可以表示为km+r，若r与m互质，那么很显然km+r也一定与m互质，所以每行有Φ(m)个数与m互质。

再来按列看，可以证明任意一列都是n的完全剩余系，即按列取两个整数，不存在它们对n取模后相等，下面用反证法证明一下

假设按列取的两个整数对n取模后相等，即有