先要吐槽一下我所在学校用的课本高等教育出版社的《离散数学(第二版)》,我在看讲到包含容斥定理这个问题时讲到了求欧拉函数的值,这里书上跳过介绍直接给出了算术基本定理「任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积」这个结论.尽管是初等数论的内容,但我相信还是有很多同学不知道.可能是我不听课的缘故(我也不知道老师讲没讲),但就单单对这本书来说,我认为这一块是缺少证明过程的,如果学生用这本书来自学的话,那么会因为这一个定理不知道会增加很大难度.
那么下面我来系统的写一下证明欧拉函数的过程🙃.
欧拉函数是用来计算给定一个正整数n,求小于等于n的正整数中,有多少个与n构成互质关系的方法(互质:如果两个数的公约数只有1,那么称这两个数互质),用以φ(n)表示.
例如φ(6) = 2,φ(8) = 4;
下面给出证明过程:
1.当n==1 φ(n) = 1; 因为1与任何数(包括自身)都构成互质关系.
2.当n是质数,则φ(n) = n - 1;因为质数与小于它的每一个数，都构成互质关系.
3.当n是质数p的某一次方,即n = p^k (k>=1 && k为整数) 那么
φ(n) = p^k - p^k-1因为当一个数不包含质数p才可能与n互质.而包含质数p的数一共有 p^k-1 个 分别是 1 x p,2 x p,3 x p…..p^(k-1) * p. 去掉他们就得到与n互质的数.
同时这个式子也就可以写成这样的形式
φ(p^k) = p^k - p^k-1 = p^k (1-1/p);可以看出上面这个式子当 k==1 时也就是当n为质数时的情况.
4.如果n可以分解为两个互质的整数之积(我上面提到的算术基本定理在这里可以进行拓展) 即
n = p1 x p2那么
φ(n) = φ(p1p2) = φ(p1)φ(p2)也就是积的欧拉函数等于各个因数的欧拉函数之积.
解释: 如果a与p1互质(a < p1)，b与p2互质(b < p2)，c与p1p2互质(c < p1p2)，则c与数对 (a,b) 是一一对应关系。由于a的值有φ(p1)种可能，b的值有φ(p2)种可能，则数对 (a,b) 有φ(p1)φ(p2)种可能，而c的值有φ(p1p2)种可能，所以φ(p1p2)就等于φ(p1)φ(p2).
5.这里用到了算术基本定理,也就是对第4条的拓展, 「任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积」.
由4得
φ(n) = φ(p1^k1)φ(p2^k2)...φ(pr^kr)由3得
φ(n) = p1^k1 p2^k2 ...pr^kr (1-1/p1)(1-1/p2)...(1-1/pr)也就是
φ(n) = n(1-1/p1)(1-1/p2)...(1-1/pr)证毕.