欧拉函数公式及其证明

简介：
《欧拉函数公式及其证明》一文详细介绍了数论中的欧拉函数定义、性质，并给出了该函数公式的严格数学证明，适合数学爱好者和研究者阅读。 欧拉函数是数论中的一个重要概念，它表示对于一个正整数n，小于n且与n互质的正整数（包括1）的数量，记作φ(n)。完全余数集合定义为：由所有小于n并与n互质的数组成的一个集合Zn，并称这个集合作为n的完全余数集合。显然|Zn|= φ(n)。 对于素数p, 欧拉函数的结果是φ(p)= p -1。如果两个不同的素数p和q相乘得到一个整数n=p*q，那么欧拉函数的结果满足φ(n)=(p-1)*(q-1)，这是因为集合Zn={1, 2, 3,... , n-1}去掉所有能被pq中任一元素整除的数字后剩下的就是完全余数集。因此 φ(n) = (n - 1) - (q - 1) - (p - 1)= (p-1)*(q-1)，即φ(p)*φ(q)。 欧拉定理指出，对于互质的正整数a和n，有 a^φ(n) ≡ 1 mod n。证明如下：设Zn={x1, x2,... , x_φ(n)} 和 S = {ax1mod n, ax2mod n, ..., ax_φ(n)mod n} ，则集合S等于Zn。 (1) 因为a与n互质，xi (i ≤ i ≤ φ(n)) 也与n互质，所以 a * xi 与 n 互质，因此 a*xi mod n 属于 Zn。 (2) 若i ≠ j，则 xi ≠ xj，并且由于a和n是互素的可得 axi mod n ≠ axj mod n。