当前位置: 首页 > >

欧拉定理及其证明

发布时间:

我真的很逊,所以有错也说不定。
这篇很简,所以看不懂也说不定。


总觉得小满哥讲过这个证明,虽然身为老年健忘选手我大概是不记得什么了。。


欧拉定理:(a^{varphi(n)} equiv 1 (mod n)) ,其中 ((a,n) = 1)
费马小定理:(a^{p-1} equiv 1 (mod p)) ,其中 ((a,p) = 1) ,容易发现是欧拉定理的一种特殊情况。


欧拉定理证明:(同余式默认模 (n))
设 (X_1,X_2,...,X_{varphi(n)}) 是 (1) 到 (n) 里与 (n) 互质的数,容易发现它们模 (n) 两两不同,且余数都与 (n) 互质(废话,因为模了之后还是原数嘛)


然后我们发现 (aX_1,aX_2,...,aX_{varphi(n)}) 好像也有如上两个性质。。


模 (n) 两两不同:反证,若 (aX_i equiv aX_j (mod n)) ,则 (aX_i-aX_j equiv 0) ,则 (a(X_i-X_j) equiv 0) ,由于 (a) 与 (n) 互质 ,(X_i-X_j) 不可能是 (n) 的倍数,所以模 (n) 一定不为 (0)


余数都与 (n) 互质:(a) 与 (n) 互质,(X_i) 与 (n) 互质,所以 (aX_i) 也 与 (n) 互质 (这很感性理解orz)


有了这两个性质,我们就可以发现 (aX_1,aX_2,...,aX_{varphi(n)}) 模 (n) 后一定是 (varphi(n)) 个不同的与 (n) 互质的数,那不就肯定是 (X_1,X_2,...,X_{varphi(n)}) 这个集合。


所以得到 [X_1 cdot X_2 ...X_{varphi(n)} equiv aX_1 cdot aX_2 ...aX_{varphi(n)} (mod n)]


[Rightarrow 1 equiv a^{varphi(n)} (mod n)]


(QED.)



转载于:https://www.cnblogs.com/ymzqwq/p/11198749.html



友情链接: