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