既然前面已经有谈及费马小定理和欧拉函数的文章,这里顺理成章地便可以推导费马-欧拉定理。
同样地,由于不懂数论/群论,维基百科对这个定理的证明我是看不懂的。其实我多多少少是想效法欧拉当年的做法,用简单的初等数学语言来描述重要的数学定理。
从两数互质说起——关于欧拉函数
欧拉函数的初等数学证明在前面的文章已经有了,这里就不赘述了。先摆出欧拉函数的结论:小于正整数\(n = \prod_{i=1}^r p_i^{k_i}\)且与它互质的正整数、有\(\phi(n) = n \prod_{i=1}^r (1-\frac{1}{p_i})\)这么多个。
设集合\(R = \{x_1, x_2, …, x_{\phi(n)}|x_i \perp n, 0 \lt x_i \lt n\}\)为与n互质且小于n的所有正整数,由于取模预算的性质,当\(x_i \lt n\),肯定有\(x_i \mod n = x_i\)。
那么,当一个正整数y如果大于n、且与n互质,那么它对n取模的值将会是什么?
我们设\(y = tn + m, t \geq 1, 0 \lt m \lt n, y \perp n\)。由于\(tn\)肯定不能与n互质,所以如果要y能够与n互质,必然有m和n互质,即\(m \perp n\)。我们再观察m的性质:\(m \perp n, 0 \lt m \lt n\),m的定义与\(x_i\)相同,那么便可以直接判断得出:\(y \mod n = m \in R\)。
这其实便证明了,只要一个正整数u与n互质,不论它多大,肯定都有\((u \mod n) \in R, u \perp n\)。
另一方面,如果有两个正整数u、v分别与n互质,那么肯定也有\((uv \mod n) \in R, u \perp n, v \perp n\)。
为什么呢?设p代表素因数、\(u = \prod_{f=1} p_f^{k_f}, v = \prod_{g=1} p_g^{k_g}, n = \prod_{i=1} p_i^{k_i}\),再设\(F = \{…,p_f\}\)为u的素因数的集合、\(G = \{…,p_g\}\)为v的素因数的集合、\(I = \{…,p_i\}\)为n的素因数的集合。由于\(u \perp n, v \perp n \Leftrightarrow F ∩ I = \varnothing, G ∩ I = \varnothing\),即F与I没有交集、G与I也没有交集。基于集合的基本操作,F和G的并集肯定也与I没有交集,即\((F∪G) ∩ I = \varnothing \Leftrightarrow uv \perp n\),所以\((uv \mod n) \in R\)。
取模运算的乘法结合率
对于任意正整数\(z_1, z_2\),它们的乘积对n取模等价与它们分别对n取模后相乘、再对n取模:\(z_1 z_2 \mod n = \{(z_1 \mod n)(z_2 \mod n)\} \mod n\)。
我们可以设\(z_1 = t_1 n + m_1, z_1 \mod n = m_1, z_2 = t_2 n + m_2, z_2 \mod n = m_2\),于是有:
\(\begin{aligned}
z_1 z_2 \mod n &= \{(t_1 n + m_1)(t_2 n + m_2)\} \mod n \\
&= (t_1 t_2 n^2 + m_1 t_2 n + m_1 m_2) \mod n \\
&= m_1 m_2 \mod n \\
&= \{(z_1 \mod n)(z_2 \mod n)\} \mod n \\
\end{aligned}\)
对于多个整数相乘的情况结合率也是可以适用的。
费马-欧拉定理
基于上述结论,当任意与n互质的正整数a与集合R中的元素相乘,肯定会得到一个新集合\(AR = \{ax_1, ax_2, …, ax_{\phi(n)}|a \perp n, x_i \perp n, ax_i \perp n, 0 \lt x_i \lt n\}\),集合中的每一个元素肯定都与n互质。而且也不难想象,集合R和集合AR的每个元素直接相乘得出来的数,肯定也会与n互质,即:
- \(\prod_{i=1}^{\phi(n)} x_i \perp n, (\prod_{i=1}^{\phi(n)} x_i \mod n) \in R\);
- \(\prod_{i=1}^{\phi(n)} ax_i \perp n, (\prod_{i=1}^{\phi(n)} ax_i \mod n) \in R\)。
观察集合AR中的每个元素,由于\(ax_i \perp n, ax_i \mod n = x_j \in R, 1\leq j\leq \phi(n)\),所以各不相同的\(x_i\)乘以a后对n取模后的值肯定也各不相同,且由于集合AR对n取模后的大小仍然为\(\phi(n)\),于是肯定有:
\(\begin{aligned}
AR \mod n &= \{(ax_1 \mod n), (ax_2 \mod n), …, (ax_{\phi(n)} \mod n)\} \\
&= \{…,x_j|1\leq j\leq \phi(n), x_j \in R\}
\end{aligned}\)
集合AR对n取模后,实际上就是集合R的重新排列(顺序有可能不一样)。但由于这里讨论的集合都是无序集合,所以便有\(AR \mod n = R\),于是有:
\(\begin{aligned}
&\{AR \mod n\} \mod n = R \mod n \\
&\Rightarrow \{(ax_1 \mod n)(ax_2 \mod n)…(ax_{\phi(n)} \mod n)\} \mod n = \{x_1 x_2 …x_{\phi(n)}\} \mod n \\
&\Rightarrow (ax_1 ax_2 …ax_{\phi(n)}) \mod n = (x_1 x_2 …x_{\phi(n)}) \mod n \\
&\Rightarrow \prod_{i=1}^{\phi(n)} ax_i \mod n = \prod_{i=1}^{\phi(n)} x_i \mod n \\
&\Rightarrow (a^{\phi(n)} \cdot \prod_{i=1}^{\phi(n)} x_i) \mod n = \prod_{i=1}^{\phi(n)} x_i \mod n \\
&\Rightarrow \{(a^{\phi(n)} \mod n)(\prod_{i=1}^{\phi(n)} x_i \mod n)\} \mod n = \{(1 \mod n)(\prod_{i=1}^{\phi(n)} x_i \mod n)\} \mod n \\
&\Rightarrow (a^{\phi(n)} \mod n) = (1 \mod n) \\
&\Rightarrow a^{\phi(n)} \mod n = 1
\end{aligned}\)
我们再转换一下记号方法,便可以得到费马-欧拉定理:当正整数a与n互质,有\(a^{\phi(n)} \equiv 1 \pmod{n}, a \perp n, a \in \mathbb{Z}^+, n \in \mathbb{Z}^+\)。
不难看出,费马-欧拉定理就是费马小定理的一般化推广。当p是素数,\(\phi(p) = p-1\),任何正整数a都会与p互质,所以有\(a^{p-1} \equiv 1 \pmod{p}\)。
应用
在讨论费马小定理的文章里已经提到,费马小定理可以用于快速运算指数函数对一个素数取模,即一个针对素数的mod_pow
操作。由于费马-欧拉定理是费马小定理的推广,所以也可以用于实现快速mod_pow
操作,而这次底数变成了任何正整数——可应用的范围相当于无限阔了。
试想有一个数\(a^k\),幂数k十分大。如果我们只需要\(a^k\)的个位数,如何快速得到呢?假设\(n = 10\),且n与a互质。那么,便有\(a^{\phi(n)} \equiv 1 \pmod{n}\)。再设\(k = \phi(n) \cdot t + s\),那么便会有\(a^k = a^{\phi(n) \cdot t + s} = (a^{\phi(n)})^t \cdot a^s \equiv 1^t a^s \equiv a^s \pmod{n}\)。可以想象得到,s远小于k,计算过程便会少很多。
为何执着于用初等数学对定理进行解释
其实,上面的推导过程,如果用数论、整数模n乘法群等概念进行,是等价的——构造集合R和AR就是那些高等概念的底层过程。高深的理论、辞藻往往会让人忘记背后的细节。在这些过程中抓住核心过程、去芜存精,从来都是思维锻炼的最佳方法——看似遥远却是最便捷的方法。不受华丽词汇影响的思维内核,负担最小。
其实这个学习过程对于我自身来说也是喜出望外的——因为我从来都不觉得自己有能力去理解费马小定理、欧拉函数、费马-欧拉定理这些重要的东西。但事实上我走过来了。我相信其他只要对数学还是抱有基本兴趣的人、即便像我一样只有初等数学水平,也是可以继续不断一路往前的。共勉之。
打赏作者
[…] 说来惭愧,这个我现在还真没大搞懂。如果有兴趣的话可以暂且先参考一下这篇博客:如何证明费马-欧拉定理。你可能发现了,这位博主用的是初等数学对欧拉定理进行的证明。对,找这种证明就是因为我已经暂时放弃了为了证明这些定理再去学习那些高等概念了——让人脑壳疼。以后找个时间我会回过头来顺着这位博主的的过程再走一遍,然后参照他的方法拼上这篇文章的这最后一块缺角。 […]
您好,
非常感谢你写的文章啊,秒杀网上其他的贴来贴去的证明 🙂
有个问题能请教下么?
当n是质数的时候,大于n的y,显然可以写成y=tn+m,t≥1,0<m<n,y⊥n, 并且m显然m∈R(因为R包含所有小于n的数)
如果n不是质数乘积的时候,比如n=p*q, p,q 是质数,此时n的集合R好像是小于p.q.的质数及其乘积
好像m∈R,好像不是很直观啊
首先,很高兴你喜欢这篇文章!
查资料查到我这里来,阁下肯定历尽艰辛了!(毕竟作为一个懒惰的站长,我很有自知之明😂)
对于你的困惑,我认为是不必要的。
你可能忽略了上文已经清晰给出【
m
的定义是和x_i ∈ R
一样的】这个中间结论。y
的结构是十分巧妙地利用了互质的定义,才导致m
和x_i ∈ R
等价。假若
n < y = t*n + m
中m
没有0 < m < n
这个限制:当
m = n
时,y
将会变成y = (t+1)*n
,那么y
肯定不能与n
互质了;而当
m > n
,便有y = (t+1)*n + (m-n) = t'*n + m', 0 < m' < n
,这个结构实际上就是y = t*n + m
。由于
t*n
是n
的倍数,肯定不能与n
互质,所以互质的“任务”便落在m
身上。于是便有【m
是小于n
且与n
互质的正整数】这个结论,这同样是集合R
中元素的定义——【x_i
是小于n
且与n
互质的正整数】。所以毫无疑问,m
就是某个x_i
,即m ∈ R
。另外,任意正整数
n
肯定、必然是若干素数的乘积,即n = p_1^{k_1} * p_2^{k_2} * ... * p_r^{k_r}
,其中p_i
是某个素数、k_i
是对应素数的幂。这个证明很简单。若
n
是任意素数,肯定满足上述形式,只要r=1, k_1 = 1
;若n
是任意合数,由于合数的定义本身就是若干素数的乘积,直接满足上述形式。站长大人太自谦了啊,我在Google搜索的第一页就找到您这个有意思的网站了呢
而且一打开就是工整的公式,很是吸引人啊
多谢回复,今天想了想确实是昨天想错了,集合 R中已经包含了所有的任何形式的n的因子,不管n是素数还是合数
祝你们的网站越来越红火。
另外:
您这验证码过期的时间太短了呀,看看贴,编辑下回复,打开网页是生成的验证码已经过期了呢 :)
这个博客其实是上两年辞职回家后,闲来无事搞起来的。
回想往年工作时,很多时候不求甚解,落下很多遗憾。作为一名软件工作者,其实我也受够了网络上的那些【粘贴-复制】的内容,所以在编写这个博客文章时,便以极高的要求来约束自己——写不好的就不发布、要写就写到最好(自己认为)。
然而,其实这是一种【无明】。最显著的表现就是,在上一年又重新走上岗位后,这个博客便被无限期暂停更新了~囧——即便后台有着几篇草稿,还是迟迟无法完成……
所以我又开始觉得,那些在百忙中还不忘【粘贴-复制】进行知识积累的作者,其实也是十分可敬的。
另外,多谢你提出验证码过期时间太短的问题。难怪这里没什么人来留言……
现在我正在使用的验证码插件貌似没有超时选项可以配置,可能是这插件有点旧了,回头有空我找一款对用户更友好的吧!无论如何都感谢你提出这个建议!
[…] 说来惭愧,这个我现在还真没大搞懂。如果有兴趣的话可以暂且先参考一下这篇博客:如何证明费马-欧拉定理。你可能发现了,这位博主用的是初等数学对欧拉定理进行的证明。对,找这种证明就是因为我已经暂时放弃了为了证明这些定理再去学习那些高等概念了——让人脑壳疼。以后找个时间我会回过头来顺着这位博主的的过程再走一遍,然后参照他的方法拼上这篇文章的这最后一块缺角。 […]
[…] 说来惭愧,这个我现在还真没大搞懂。如果有兴趣的话可以暂且先参考一下这篇博客:如何证明费马-欧拉定理。你可能发现了,这位博主用的是初等数学对欧拉定理进行的证明。对,找这种证明就是因为我已经暂时放弃了为了证明这些定理再去学习那些高等概念了——让人脑壳疼。以后找个时间我会回过头来顺着这位博主的的过程再走一遍,然后参照他的方法拼上这篇文章的这最后一块缺角。 […]
[…] 至于欧拉定理和欧拉函数的证明……说来惭愧我还没大搞懂。如果有兴趣的话可以参考一下这位博主的博客:欧拉函数,欧拉-费马定理。 […]