淺談歐拉定理

本篇隨筆簡單講解一下信息學奧林匹克競賽數論部分歐拉定理這一知識點。介紹的內容大致分為這么幾個部分：“同余的基本概念、費馬小定理、歐拉定理及其推論、乘法逆元”。

同余的基本概念

同余的概念啊非常簡單啦：如果兩個整數(a,b)除以一個數(m)的余數相等的話，那么就叫做(a,b)在模(m)的意義上同余。

記作：

[aequiv b\,\,\,(mod\,\,m)
]

那么根據同余的這個定義，我們很容易能推導出一個性質：如果兩個數(a,b)在模(m)的意義下同余，那么(a-b)就是(m)的倍數，這是顯然的。

以及，如果(a\%m=1)，那么就可以被改寫成這樣的式子：

[aequiv 1\,\,\,(mod\,\,m)
]

這個轉化的正確性也是顯然的。

費馬小定理

費馬小定理也非常簡單啦！用語言描述就是，如果一個數(p)是質數，那么對于一個不為(p)的倍數的整數(a)，有(a^{p-1}equiv 1\,\,\,(mod\,\,p))。那么把這個結論兩邊同時乘上一個(a)，即可得出：對于任意的整數(a)，(a)的(p)次冪與(a)在模(p)的意義上同余。

即：

[a^pequiv a\,\,\,(mod\,\,p)
]

證明過程由于筆者水平有限，請參閱百度百科：

引理1．
　　若a,b,c為任意3個整數,m為正整數，且(m,c)=1，則當a·c≡b·c(mod m)時，有a≡b(mod m)。
　　證明：a·c≡b·c(mod m)可得ac–bc≡0(mod m)可得(a-b)·c≡0(mod m)。因為(m,c)=1即m,c互質，c可以約去，a– b≡0(mod m)可得a≡b(mod m)。 [2]

引理2．
　　設m是一個整數且m>1，b是一個整數且(m,b)=1。如果a[1],a[2],a[3],a[4],…a[m]是模m的一個完全剩余系，則b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]也構成模m的一個完全剩余系。
　　證明:若存在2個整數b·a[i]和b·a[j]同余即b·a[i]≡b·a[j](mod m)..(i>=1 && j>=1)，根據引理1則有a[i]≡a[j](mod m)。根據完全剩余系的定義可知這是不可能的，因此不存在2個整數b·a[i]和b·a[j]同余。

所以b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]構成模m的一個完全剩余系。

構造素數

的完全

因為

，由引理2可得

也是p的一個完全剩余系。由完全剩余系的性質，

即

易知

，兩邊可約去

這樣就證明了費馬小定理。

（結論必須要記住）：

[a^pequiv a\,\,\,(mod\,\,p)
]

歐拉定理

在學習歐拉定理之前，需要先學習一下歐拉函數。推薦本蒟蒻的這篇博客：

歐拉函數詳解

那么有了這個知識做鋪墊，我們就可以得出歐拉定理的式子：

[a^{phi(p)}equiv1\,\,\,(mod\,\,p)
]

也就是說，如果(a,p)為整數且(a,p)互質，那么(a)的(p)的歐拉函數次冪與(1)在模(p)意義下同余。

（以下證明摘自百度百科。）

證明

將1~n中與n互質的數按順序排布：x1,x2……xφ(n) （顯然，共有φ(n)個數）

我們考慮這么一些數：

m1=ax1;m2=ax2;m3=ax3……mφ(n)=axφ(n)

1）這些數中的任意兩個都不模n同余，因為如果有mS≡mR (mod n) （這里假定mS更大一些），就有：

mS-mR=a(xS-xR)=qn，即n能整除a(xS-xR)。但是a與n互質，a與n的最大公因子是1，而xS-xR<n，因而左式不可能被n整除。也就是說這些數中的任意兩個都不模n同余，φ(n)個數有φ(n)種余數。

2）這些數除n的余數都與n互質，因為如果余數與n有公因子r，那么axi=pn+qr=r(……)，axi與n不互質，而這是不可能的。(因為axi=pn+qr=r(……)，說明axi含有因子r，又因為前面假設n含有因子r，所以axi和n含有公因子r，因此axi與n不互質)那么這些數除n的余數，都在x1,x2,x3……xφ(n)中，因為這是1~n中與n互質的所有數，而余數又小于n.

由1）和2）可知，數m1,m2,m3……mφ(n)（如果將其次序重新排列）必須相應地同余于x1,x2,x3……xφ(n).

故得出：m1m2m3……mφ(n)≡x1x2x3……xφ(n) (mod n)

或者說a^[1](x1x2x3……xφ(n))≡x1x2*x3……xφ(n)(mod n)

或者為了方便：K{a^[2]-1}≡0 ( mod n ) 這里K=x1x2x3……xφ(n)。

可知K{a^[3]-1}被n整除。但K中的因子x1,x2……都與n互質，所以K與n互質。那么a^[4]-1必須能被n整除，即a^[5]-1≡0 （mod n），即a^[6]≡1 （mod n），得證。

歐拉定理的推論

歐拉定理能干什么呢？

比如，簡化冪的模運算。

例題：計算(7^{222})的個位數。（也就是計算(7^{222}mod\,\,10)）。

那么，根據歐拉定理，(a^{phi(p)}equiv1\,\,\,(mod\,\,p))，我們可以有以下的推導：

首先，因為(7,10)互質，且(phi (10)=4)，所以有：(7^4equiv 1\,\,\,(mod\,\,10))。

那么，根據取余的性質，因為(7^4mod\,\,10=1)，所以(7^4)的(n)次冪模10還等于1.

那么就可以有：

(7^{222}=7^{4 imes55+2})，把1全部約去，得到：

(7^2equiv7^{222}\,\,\,(mod\,\,10))

這樣就簡單多了。

所以我們得出了這樣的一個結論：

[a^n\,\,mod\,\,p=a^{n\%phi(p)}\,\,mod\,\,p
]

也就是說：

[a^nequiv a^{n\%phi(p)}\,\,\,(mod\,\,p)
]

這個結論也叫做：歐拉定理的推論，極其重要。

對于線性計算的式子（這里指四則基本運算中除了除法之外的三種運算），如果要求我們對于(a+b,a-b,a imes b)的結果取模，那么我們完全可以在進行運算之前先對(a,b)取模，對結果不會造成任何影響。

但是如果要求我們對(a^b)這樣的式子取模呢？

這就用到了歐拉定理的推論：我們可以把底數對(p)取模（這個操作的正確性就是由前面說的四則混合運算的正確性推導出來的，別忘了乘方運算的實質是一堆連乘）。指數對(phi(p))取模，再進行運算即可（快速冪走起）。

求乘法逆元

乘法逆元的概念

其實是一個介紹定義的過程：

如果(axequiv1\,\,\,(mod\,\,p))，并且(a,p)互質，則稱(a)關于模(p)的乘法逆元為(x)。

還是比較容易記住的。

乘法逆元的求解

舉個例子：

如果需要我們求解(4)關于模(7)的乘法逆元。那么也就是說，對于這個需要去求解的乘法逆元(x)，我們只需要找到一個(k)，使得下式成立：

[4x=7k+1
]

（這個式子是由于乘法逆元的定義：(4xequiv 1\,\,\,(mod\,\,7))以及同余的定義得到的）。

關于乘法逆元的求解，我們首先要對其進行分類。

首先，我們需要明白的是，對于(a)關于模(p)的乘法逆元的求解，只有在(a,p)互質的時候才有解，否則就是無解。這不僅是定義規定的，更是滿足大前提的首要條件（大家只需要牢牢記住就好）。

那么，現在，(a,p)已經互質了。那么又有兩種情況：模數(p)是否為素數。

假如(p)為素數。那么我們可以使用費馬小定理來求解乘法逆元。

根據費馬小定理，有：(a^{p-1}equiv1\,\,\,(mod\,\,p))，那么結合乘法逆元的定義，如果(a,p)互質，那么原式可以拆成(a imes a^{p-2}equiv1\,\,\,(mod\,\,p))。也就是說，這個時候的乘法逆元就是(a^{p-2})。

假如(p)不是素數，就需要我們使用擴展歐幾里得算法求解，對于擴展GCD還有不明白的小伙伴，請移步本蒟蒻的這篇博客：

淺談擴展GCD

對于擴展歐幾里得算法，我們知道它可以被用于求解同余方程。

那么就和乘法逆元的求解很匹配了，因為乘法逆元的求解本質上就是在求解這么一個同余方程：

[axequiv 1\,\,\,(mod\,\,p)
]

但是，擴展GCD解決的是形如(ax+by=gcd(a,b))的東西，和這個同余式子有什么關系呢？

如果像我一開始一樣不太會變通的話，請看下面的證明過程。

最裸最裸，我們會求解形如：(ax+by=gcd(a,b))，這樣的方程。

那么，我們只需要把這個(axequiv1\,\,\,(mod\,\,p))轉換成這樣的形式進行求解即可。

假設我們可以把這個同余方程轉換成(ax+by=gcd(a,b))的形式，那么當(a,b)互質時，(gcd(a,b)=1)，咦？我們發現這個東西和乘法逆元的定義：(a,p)互質好像啊！那就讓(b=p)吧！

那么，有(ax+by=1)。

兩側同時對(b)取模（因為這個時候(b=p)了），有(ax\%b+by\%b=1\%b=1)。

因為(by\%b=0)，所以原式就變成了：

(axequiv1\,\,\,(mod\,\,p))，得證。

也就是說，如果要求一個數(a)關于(p)的乘法逆元，直接向擴展GCD算法的模板里傳((a,p,x,y))，最后的(x)就是我們要求的乘法逆元。

這樣的話有一道經典裸題例題：NOIP2012同余方程

然后我們就可以求出一個數的乘法逆元。

線性求逆元

其實我認為，前面的“求一個數的逆元”的部分最終還是為這個“線性求逆元”做鋪墊（理論知識大于天嘛！）。我們在學數論的時候可能都會發現，我們在探究的過程中都是一個“由局部到整體”的概念：由判斷一個數是否為質數到判斷一群數是否為質數，由求一個數的約數集合到篩選一群數的約數集......同樣，在學會了求一個數的逆元之后，我們要學習線性篩逆元。

求一個數的逆元的復雜度是(O(log N))的。如果我們要求很多數的逆元的時候，如無意外它的復雜度會是(O(Nlog N))的，這顯然不符合我們的需求。所以，我們要開發一個(O(n))的線性求逆元的算法。

線性篩逆元其實是一個遞推的過程，我們在這里著重講其遞推式的建立與證明。

首先我們有：

[1^{-1}equiv 1\,\,\,(mod\,\,p)
]

我們把(p)拆開，拆成這樣的形式：(p=k imes m+n)，這是可以成立的，因為任意一個正整數都可以被拆成這樣的形式。

所以我們有：

[k imes m+nequiv 0\,\,\,(mod\,\,p)
]

（這個同余式其實表示的意義就是整除）

那么，兩邊同時除以(m,n)（即同時乘(m^{-1},n^{-1})），則有

[frac{k}{n}+frac{1}{m}equiv0\,\,\,(mod\,\,p)
]

移項有：

[frac{1}{m}equiv-frac{k}{n}\,\,\,(mod\,\,p)
]

因為(k)就是(lfloorfrac{p}{m}floor)，(n)就是(p\,\,\,mod\,\,\,m)，所以原式就變成了：

[m^{-1}equiv-lfloorfrac{p}{m}floor imes(p\,\,\,mod\,\,\,m)^{-1}\,\,\,(mod\,\,p)
]

根據乘法逆元的定義，對于一對互質的數(a,p)，有它的一個乘法逆元(x)滿足：(axequiv1\,\,\,(mod\,\,p))，那么(xequiv a^{-1}\,\,\,(mod\,\,p))，那么，根據上面的這個式子，我們就求出了數(m)關于模(p)意義下的逆元。

遞推式如下（用(inv[i])數組表示一個數的逆元）：

[inv[i]=-(p/i) imes inv[p\%i]
]

為了不讓乘法逆元出現一堆負數，我們需要對這個遞推式稍做處理：

[inv[i]=((p-p/i)*inv[p\%i])\%p
]

如果能看明白并且記住這個證明過程的話當然是極好的，如果看不明白，直接記結論也是完全可以的，但是，請做好考場上秒忘自己又一點不會推的準備（別怪我沒告訴你）。

乘法逆元解決除法取模問題

一般來講，毒瘤出題人不會單獨出題考乘法逆元，它的較常用的考查方式是在組合數問題中作為除法取模的計算方式。

除法取模就是：

[a/b\,\,\,mod\,\,p
]

這個式子可以變成：

[a imes b^{p-2}\,\,mod\,\,p
]

也就是分子乘以分母的逆元再取模。

---

總結：

這篇總結是我耗時將近一周盤完這篇博客之后的附加之作

（本來認為乘法逆元這一塊一天就能學完，但是我好像高估了自己的能力、低估了數學的魅力（呵呵），加之快期末了，各種文化課以及個人爛事層出不窮，導致更博和鞏固的速度都極為地緩慢）。

本來以為學完了應該就會了，但是在學最后的線性求逆元的過程中驚喜地發現前面的東西大多又不會了（結論也就差不多記住，至于推導過程就全部忘光光了），于是才真正領略了什么是數論，以及為何數論這一塊讓一些數競大佬都由衷地感覺困難。于是又剎下心來重新看了一下，順便歸納出來了一些重點，這樣的話，每次復習的時候就不用通篇瀏覽，只核對這些重要的知識點到底會不會就可以了。

那么，學完這一課，你需要會的——

1、同余的基本概念

你總不能對別人講，我學完同余了，但是連式子也看不懂...

2、費馬小定理

結論：

[a^{p-1}equiv 1\,\,\,(mod\,\,p)
]

即：

[a^pequiv a\,\,\,(mod\,\,p)
]

這個定理的適用條件一定要記住：(p)為質數，并且(a)不為(p)的倍數。

3、歐拉定理

結論：

[a^{phi(p)}equiv 1\,\,\,(mod\,\,p)
]

它的適用條件是：(a,p)互質。

推論：

[a^{n}equiv a^{n\%phi(p)}\,\,\,(mod\,\,p)
]

當然，這個定理不是供人顯擺用的，知道了，還得會用：

歐拉定理的推論可以用來解決形如這樣的式子的求解的問題：

[a^n\,\,\,mod\,\,p
]

4、乘法逆元的概念

5、求單個數的乘法逆元的兩種方式

知道求單個數的乘法逆元的兩種方式及其使用條件：

對于求(axequiv 1\,\,\,(mod\,\,p))中的(x)，（大前提當然是(a,p)互質）如果：

(p)為質數，那么可以使用費馬小定理。

(p)不為質數，那么需要使用擴展GCD將同余式轉換成形如(ax+by=gcd(a,b))的同余方程來求解。

6、線性篩逆元

結論（遞推式）：

[inv[i]=((p-p/i) imes inv[p\%i])\%p
]

7、乘法逆元求解除法取模問題

知道形如(a/b\,\,mod\,\,p)可以變成(a imes b^{p-2}\,\,mod\,\,p)。

---

φ(n) ↩?

φ(n) ↩?

φ(n) ↩?

φ(n) ↩?

φ(n) ↩?

φ(n) ↩?

總結

以上是生活随笔為你收集整理的同余知识点全析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。