定理：
若GCD(a,m)=1，則滿足$a^{\phi (m)}\equiv 1(modm)$

證明:

擴展歐拉定理：
$a^b\equiv ?\begin{array}{l}{a}^{b\%?(p)}gcd(a,p)=1\\ a^{b}gcd(a,p)=1,b<?(p)\\ a^{b\%?(p)+?(p)}gcd(a,p)=1,b\ge ?(p)\end{array}(modp)$

證明：
當m = 1時顯然成立，以下討論m ≠ 1的情況。

對于gcd(a,m) = 1 的情況，因為a?(m) ≡ 1，所以每?(m)個a就相當于乘1。于是只需要算c Mod ?(m)次。

對于c < ?(m)的情況，直接爆算

下面證明第三種情況。

先證明a是一個質數的情況：

引理1：
? p 為質數，r ∈ Z+，都有?(pr) = (p?1) × pr?1。

證明：
由于p是一個質數，所以 1 ～ (pr?1) 中有且僅有i × p, i ∈ (0,pr?1) 與pr不互質。

于是?(pr) = pr ? pr?1 = pr?1 × (p ? 1) 。

證畢。
引理2：
? k ∈ Z，? a,b,x,y ∈ Z+ , s.t. xa × yb = k，都有 a,b ≤ ?(k) 。

證明：
先考慮k為一個質數p的r次冪的情況。根據引理1有：

?(k) = ?(pr) = (p?1) × pr?1。

下面說明(p?1) × pr?1 ≥ r。

當p=2時：

經驗證 r=1,2,3 時成立。當 r>3 時按照r的大小做數學歸納，可證正確性。

當 p > 2 時，不等號左側增大，右側不變，不等式仍然成立。

考慮k是多個質數冪時的情況，按照質數個數做數學歸納，正確性成立。

任意組合質數，引理得證。

證畢
引理3：? r ≤ c , s.t. a?(m)+r ≡ ar (Mod m)。
證明：
令m = t × ar，其中gcd(t,a)=1，t的存在性顯然。

因為gcd(t,a) = 1，且?函數是一個積性函數，所以?(t) | ?(m)。

根據歐拉定理，a?(t) ≡ 1 (Mod t)，于是有

a?(m) ≡ 1 (Mod t)

同余式同乘ar，于是有

a?(m)+r ≡ ar (Mod m)

已經證明可以構造出這樣的r。根據引理2，r ≤ ?(m)。又c ≥ ?(m)，于是可證構造出的r ≤ c。定理得證。

證畢
于是

ac ≡ ac?r+r ≡ ac?r+?(m)+r ≡ ac+?(m) (Mod m)

對上式做數學歸納，可得ac ≡ ac+k?(m) , k ∈ Z，需保證指數為正。

于是最小的合法的指數即為c Mod ?(m) + ?(m)。

于是有
ac ≡ ac Mod ?(m) + ?(m)

當a是一個質數的冪次時，設a=pk，則

ac ≡ pck ≡ pck+?(m) ≡ pck+k?(m) ≡ (pk)c+?(m) ≡ (pk)c Mod ?(m) + ?(m) (Mod m)

當a時多個質數次冪的乘積時，依據唯一分解定理做數學歸納，即證正確性。證畢。

總結

以上是生活随笔為你收集整理的数学--数论--数论定理--欧拉定理的全部內容，希望文章能夠幫你解決所遇到的問題。

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