浅谈欧拉定理的证明

浅谈欧拉定理的证明自己在校内互坑赛出了一道欧拉定理的板子题,但是因为数据水变成了模拟数学题,真是一个悲伤的故事。。。说一下欧拉定理的证明吧,之前一直认为费马小定理的证明很复杂,但是懂了欧拉定理之后就迎刃而解了。首先,我们需要知道欧拉定理是什么:​ 数论上的欧拉定理,指的是$$a^x\equiv1(mo

大家好,欢迎来到IT知识分享网。浅谈欧拉定理的证明

自己在校内互坑赛出了一道欧拉定理的板子题,但是因为数据水变成了模拟数学题,真是一个悲伤的故事。。。

说一下欧拉定理的证明吧,之前一直认为费马小定理的证明很复杂,但是懂了欧拉定理之后就迎刃而解了。

首先,我们需要知道欧拉定理是什么:

​ 数论上的欧拉定理,指的是

\[a^x \equiv 1 (modn) \]

这个式子实在a和n互质的前提下成立的。

为什么成立呢?下面来证一下。

首先,我们知道在1到n的数中,与n互质的一共有\(φ(n)\)个,所以我们把这\(φ(n)\)个数拿出来,放到设出的集合X中,即为\(x_1,x_2……x_{φ(n)}\)

那么接下来,我们可以再设出一个集合为M,设M中的数为:

\[m1=a*x1 \\m2=a*x2 \\…… \\mφ(n)=a*xφ(n) \]

下面我们证明两个推理:

一、M中任意两个数都不模n同余。

反证法。

证明:假设M中存在两个数设为\(m_a,m_b\)模n同余。

​ 即\(m_a \equiv m_b\)

​ 移项得到:\(m_a-m_b=n*k\)

​ 再将m用x来表示得到:\(a*x_a-a*x_b=n*k\)

​ 提取公因式得到\(a*(x_a-x_b)=n*k\)

​ 我们现在已知a与n互质,那么式子就可以转化为:\(x_a-x_b\equiv 0(modn)\),因为a中没有与n的公因子(1除外)所以a对模n同余0并没有什么贡献。

​ 又因为\(x_a,x_b\)都是小于n的并且不会相同,所以\(x_a-x_b\)一定是小于n的,那么上述的式子自然全都不成立。

​ 假设不成立。

证得:M中任意两个数都不模n同余。

二、M中的数除以n的余数全部与n互质。

证明:我们已知\(m_i=a*x_i\).

​ 又因为a与n互质,\(x_i\)与n互质,所以可得\(m_i\)与n互质。

​ 带入到欧几里得算法中推一步就好了。

​ 即:

\[gcd(a*x_i,n)=gcd(m_i,n)=gcd(n,m_imodn)=1 \]

证毕。

根据我们证得的两个性质,就可以开始推式子了。

首先,根据第二个性质可以知道,M中的数分别对应X中的每个数模n同余。

所以可以得到:

\[m_1*m_2*……*m_{φ(n)}\equiv x_1*x_2*……*x_{φ(n)}(mod n) \]

现在我们把\(m_i\)替换成x的形式,就可以得到:

\[a*x_1*a*x_2*……*a*x_{φ(n)}\equiv x_1*x_2*……*x_{φ(n)}(modn) \]

很显然,我们应该移项了,但是在移项之前,我们认为这么多的a很烦,那么就先乘起来:

\[a^{φ(n)}*(x_1*x_2……*x_{φ(n)})\equiv x_1*x_2……*x_{φ(n)}(mod n) \]

很开心,我们终于凑出了\(a^{φ(n)}\),那么就开始移项吧:

\[(a^{φ(n)}-1)*(x_1*x_2……*x_{φ(n)})\equiv 0(mod n) \]

然后,就出来啦:

\[a^{φ(n)}\equiv 1(mod n) \]

证毕。

开心。

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/33244.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信