本文来讲数论中欧拉函数的理论及相关定理的证明，编程实现求一个正整数的欧拉函数值，并给出欧拉定理的证明。
欧拉函数的定义非常简单，如下描述
对于正整数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取模后相等，即有
联系客服
