初等數論Part 1：歐拉定理

04-30

這是一個關於初等數論的入門級別文章
適合中學數學水平的讀者
主要內容：唯一分解定理，互質，最大公因數，最小公倍數，同餘關係，同餘類，完全剩餘系，縮剩餘系，歐拉函數，歐拉定理，費馬小定理，中國剩餘定理，逆元。

求正整數 $3^{83}$ 的最後兩位數

看到類似這樣求一個數的某次方的最後幾位數的問題，

沒有接觸過初等數論的同學可能第一反應是小學的做法：找規律。

$egin{align} &3^0 = quadspace space color{red}1\ &3^1 = space quad space color{red}3\ &3^2 =space quad space color{red}9\ &3^3 =space space space space 2 color{red} 7\ &3^4 =space space space space 8 color{red} 1 \ &3^5 =space space 24 color{red} 3 \ &3^6 =space space 72 color{red} 9 \ &3^7 =218color{red}7 \ &3^8 = 656color{red} 1 \ end{align}$

可以看出來 $3^n$ 的個位是 $1,3,9,7$ 循環，循環周期是 $4$

而十位是 $0,0,0,2, 8, 4, 2, 8, 6, 8, 4, 4, 4, 2, 6, 0, 2, 6, 8, 6$ 循環，循環周期是 $20$

所以 $3^{83}$ 最後兩位是 $27$

接觸過一點初等數論的同學表示這種方法too young，因為這個問題可以用歐拉定理(Eulers theorm)秒殺。

如果正整數 $n$ 和整數 $a$ 互質，那麼就有
$a^{varphi(n)}equiv 1 pmod{n}$
其中歐拉函數 $varphi(n)$ 是「小於 $n$ 的正整數中和 $n$ 互質的數」的個數

因為

$varphi(100)=100left( 1-frac{1}{2} ight)left( 1-frac{1}{5} ight)=40$

我們又知道 $gcd(3, 100)=1$ ，所以

$3^{83}=3^{3} imes 3^{80} =3^{3} imes left(3^{varphi(100)} ight)^2 equiv 3^3 imes 1 = 27pmod{100}$

利用好歐拉定理我們還可以解決很多類似的問題（部分選自Brilliant）

求 $2014^{2014^{2014}}$ 的最後兩位數
求 $1^{2016}+2^{2016}+cdots + 2016^{2016}$ 除以 $2016$ 的餘數
求 $8^{7^{6^{5^{4^{3^{2^{1}}}}}}}$ 的最後三位數
有多少個正整數 $1le n le 2015$ 使得 $n^{n^{n}}$ 和 $n^n$ 的個位數相同？
$249$ 的奇數次方末尾總會出現其本身 $color{red}{249}^3 =15438color{red}{249}$ ， $color{red}{249}^5=957186876color{red}{249}$ 等等。 $1000$ 以內有多少個正整數有這樣的性質？

我們首先從初等數論最基本的幾個概念說起

1.唯一質數分解定理（Unique factorisation theorm）

任何一個正整數 $n>1$ 都可以唯一地分解為一組質數的乘積

$n=2^{e_1} imes3^{e_2} imes 5^{e_3} imes cdots=prod_{k=1}^infty p_k^{e_k}$

其中 $e_1, e_2,ldots in mathbb{N}$ ，我們稱這個分解為 $n$ 的標準分解

2.互質（Coprime）、最大公因數（GCD）和最小公倍數（LCM）

對於整數 $a, b$ 我們記 $gcd(a, b)$ 和 $operatorname{lcm}(a, b)$ 為 $a, b$ 的最大公因數和最小公倍數，有時候我們會直接把他們簡寫為 $(a, b)$ 和 $[a, b]$ 。如果 $gcd(a, b)=1$ ，我們稱 $a, b$ 互質，也就是說他們沒有任何共同的質因數。

它有幾個基本的性質，對於正整數 $a, b, n$

$gcd(a, b)=gcd(apm b, b)$
$gcd(na, nb)=ngcd(a, b)$
$gcd(a, b)=frac{acdot b}{operatorname{lcm}(a, b)}$
貝祖定理：總能找到整數 $x, y$ 使得 $gcd(a, b)=ax+by$

2.同餘關係（Congruence relations）

整數 $a$ 和 $b$ 除以 $n$ 的餘數相同，則稱 $a,b$ 模 $n$ 同餘，計作

$a equiv b pmod{n}$

如果對於整數 $a_1, a_2, b_1, b_2$ 有

$a_1 equiv b_1 pmod{n}\a_2 equiv b_2 pmod{n}$

那麼可以把他們相加或相減

$a_1 pm a_2 equiv b_1 pm b_2pmod{n}$

也可以把他們相乘

$a_1a_2 equiv b_1b_2pmod{n}$

通過這兩條性質，我們容易知道，如果 $aequiv b pmod{n}$ 那麼

$mathrm P(a)equiv mathrm P(b) pmod{n}\$

對於任意整係數多項式 $mathrm P(x)$ 都成立，這個結論很重要哦，經常會用

這裡需要注意的一點是，如果整數 $a, b, c$ 滿足

$acequiv bc pmod{n}$

那麼只有當 $n, c$ 互質時才可以把兩邊的 $c$ 直接約掉，得到 $aequiv b pmod{n}$ ，更一般的

$aequiv b pmod{frac{n}{gcd(n, c)}}$

3.同餘類(Residue class)、完全剩餘系(Complete residue system)、縮剩餘系(Reduced residue system)

通過一個整數模 $n$ 的餘數，我們可以把所有整數分成 $n$ 類，記

$overline{r}_n={min mathbb{Z} mid mn+r}$

為模 $n$ 余 $r$ 的同餘類（也叫剩餘類）舉個例子

$overline{4}_{10}={dots,-16,-6,4, 14, 24, dots}$

是模 $10$ 余 $4$ 的同餘類

從 $overline{0}_n, overline{1}_n, overline{2}_n, dots,overline{(n-1)}_n$ 中各挑出一個數就組成了一個模 $n$ 的完全剩餘系（完系） $R_n$

$R_n = {r_0, r_1, dots, r_{n-1}}$

其中 $r_0 in overline0_n, r_1 in overline1_n, r_2 in overline2_n, dots, r_{n-1} in overline{(n-1)}_n$

換言之， $n$ 個模 $n$ 互相不同餘的整數組成一個模 $n$ 的完全剩餘系。

我們稱 $R_n = {0, 1, dots, n-1}$ 為模 $n$ 的最小非負完全剩餘系（最小非負完系）。

取一個模 $n$ 的完全剩餘系 $R_n$ ，取出裡面所有和 $n$ 互質的數，這些數組成一個模 $n$ 的縮剩餘系（縮系），記為 $Phi_n$

$Phi_n = {c_1, c_2, dots, c_{varphi(n)} }$

其中 $varphi(n)$ 是序言里提到的歐拉函數，代表「小於 $n$ 的正整數中和 $n$ 互質的數」的個數。

注意，因為 $gcd(c_i, n)=gcd(c_i+n, n)=1$ ，每一個模 $n$ 的縮剩餘系有相同數量的元素（縮剩餘系中的每一個數所屬的同餘類是確定的，所以總有確定的 $varphi(n)$ 個同餘類）

如果縮剩餘系 $Phi_n = {c_1, c_2, dots, c_{varphi(n)} }$ 滿足 $1le c_1, c_2, dots, c_{varphi(n)}le n -1$ ，那麼稱其為模 $n$ 的最小正縮剩餘系（最小正縮系）。

4.歐拉函數(Eulers totient function)

對於正整數 $n$ ， $varphi(n)$ 代表「小於 $n$ 的正整數中和 $n$ 互質的數」的個數，這個函數被稱為歐拉函數；歐拉還告訴我們

$frac{varphi(n)}{n}=prod_{p|n}left( 1-frac{1}{p} ight)$

其中 $p$ 取到 $n$ 的所有質因數

所以我們可以很方便的計算一個正整數歐拉函數的值，比如

$varphi(1926)=varphi(2 imes 3^2 imes 107)=1926left( 1-frac{1}{2} ight)left( 1-frac{1}{3} ight)left( 1-frac{1}{107} ight)=636$

歐拉函數還有一些非常有用的性質（跳過不影響下一部分的閱讀）

如果正整數 $n>2$ 那麼 $varphi(n)$ 是偶數
如果 $n | N$ ，那麼 $varphi(n) | varphi(N)$
對於正整數 $a, n$ 有 $n | varphi(a^n - 1)$
對於正整數 $m, n$ 有 $varphi(mn)=varphi(m)varphi(n)frac{gcd(m, n)}{varphi(gcd(m, n))}$
特別地，如果 $m, n$ 互質，那麼 $varphi(mn)=varphi(m)varphi(n)$
對於正整數 $n$ 有 $sum_{d| n}varphi(d)=n$
對於正整數 $n$ 有 $sum_{1le k le natop gcd(k, n)=1}frac{k}{n}=frac{varphi(n)}{2}$

接下來我們進入正題：歐拉定理

如果正整數 $n$ 和整數 $a$ 互質，那麼就有
$a^{varphi(n)}equiv 1 pmod{n}$
其中 $varphi(n)$ 是歐拉函數

以下是證明

考慮模 $n$ 的最小正縮系

$Phi_n ={c_1, c_2, dots, c_{varphi(n)}}$

已知 $gcd(a,n)=1$ 我們在 $Phi_n$ 的每一個元素前面都乘一個 $a$

$aPhi_n = {ac_1,a c_2, dots, ac_{varphi(n)}}$

利用反證法可以證明 $aPhi_n$ 也是一個模 $n$ 的縮系（其元素的同餘類的順序有可能會改變，但是這並沒有任何影響），假設

$ac_i equiv ac_j pmod{n}$

其中 $i e j$ ，因為 $a, n$ 互質可以將兩邊消去 $a$ ，那麼就得到

$c_i equiv c_j pmod{n}$

這是不可能的，因為 $Phi_n$ 中的元素互相模 $n$ 不同餘，矛盾啦！

接下來的思路就比較清晰了，因為 $Phi_n$ 和 $aPhi_n$ 都是模 $n$ 的縮系

$prod_{i=1}^{varphi(n)} c_iequiv prod_{i=1}^{varphi(n)} ac_i = a^{varphi(n)}prod_{i=1}^{varphi(n)} c_i pmod{n}$

顯然 $gcdleft(n, prod_{i=1}^{varphi(n)} c_i ight)=1$ 所以可以兩邊消去它

$a^{varphi(n)}equiv 1 pmod{n}$

然後我們就證畢啦，是不是意外的簡單？

另外，如果我們讓 $n=p$ 是一個質數，我們就可以從歐拉定理推出費馬小定理（Fermats little theorm）

如果 $p$ 是質數，那麼 $p | n^p -n$ 對於任意整數 $n$ 都成立

當然，費馬小定理也可以用歸納法證明，假設 $p | n^p -n$ ，那麼

$(n+1)^p-(n+1)=sum_{r=1}^{p-1}inom{p}{r}n^r + n^p - n$

當 $1le r le p -1$ 時，二項式係數 $inom{p}{r}=frac{p!}{(p-r)!r!}$ 的分子中有 $p$ ，分母中每一個乘子都不能整除 $p$ （因為 $p$ 是質數），所以 $p$ 能夠整除 $inom{p}{r}$ ，進而得到 $p | (n+1)^p - (n+1)$ 。當 $n=0$ 時顯然成立，所以定理成立。

接下來我們看看如何證明

$frac{varphi(n)}{n}=prod_{p|n}left( 1-frac{1}{p} ight)$

首先考慮 $varphi(p^e)$ ，其中 $p$ 是質數， $e$ 是非負整數

如果要使 $gcd(p^e, k) e 1$ ，只能讓 $k$ 等於 $p$ 的倍數

在 $1le k le p^e$ 範圍內， $p$ 的倍數有 $p, 2p, 3p, dots p^{e-1}p=p^e$ 總共 $p^{e-1}$ 個，所以

$varphi(p^e)=p^e - p^{e-1}=p^e left( 1-frac{1}{p} ight)$

然後我們證明對於 $gcd(m, n)=1$ 有 $varphi(mn)=varphi(m)varphi(n)$ ，我們首先構造兩個集合，第一個集合是模 $mn$ 的最小正縮系 $Phi_{mn}$ ，第二個集合定義為

$S={(m, n)mid min Phi_m, nin Phi_n }$

其中 $Phi_m, Phi_n$ 分別是模 $m,n$ 的最小正縮系，顯然 $|Phi_{mn}|=varphi(mn)$ 和 $|S|=varphi(m)varphi(n)$

如果我們證明存在一個雙射 $f:Phi_{mn} ightarrow S$ ，就證明了 $varphi(mn)=varphi(n)varphi(n)$

我們讓

$f(a)=(a mod m, a mod n)$

首先我們用反證法證明 $f$ 是單射，假設 $a, b in Phi_{mn}$ 滿足 $a e b$ 且 $f(a)=f(b)$ 那麼

$egin{align}a&equiv b pmod{m}\a&equiv b pmod{n}end{align}$

顯然因為 $gcd(m,n)=1$ 我們能得出 $aequiv b pmod{mn}$ ，這與我們的假設矛盾（因為 $Phi_{mn}$ 是模 $mn$ 的縮系， $a, b$ 是 $Phi_{mn}$ 的兩個不同的元素，所以他們模 $mn$ 不同餘）。接下來，中國剩餘定理告訴我們

如果整數 $r_1, r_2$ 和正整數 $gcd(n_1,n_2)=1$ ，同餘方程組
$egin{align}x&equiv r_1 pmod{n_1}\ x &equiv r_2 pmod{n_2}end{align}$
在 $0 le x < n_1n_2$ 範圍內有且只有一個解

通過中國剩餘定理我們能夠證明 $f$ 是滿射，所以 $f$ 是雙射。

所以對於 $gcd(m,n)=1$ 就有 $varphi(mn)=varphi(n)varphi(n)$ ，假設 $n$ 的標準分解為

$n=2^{e_1} imes3^{e_2} imes 5^{e_3} imes cdots=prod_{k=1}^infty p_k^{e_k}$

其中 $e_1, e_2,ldots in mathbb{N}$ ，那麼

$egin{align}varphi(n)&=varphileft(prod_{k=1}^infty p_k^{e_k} ight)\&=prod_{k=1}^infty varphileft(p_k^{e_k} ight)\&=prod_{k=1}^infty p^{e_k} left( 1-frac{1}{p_k} ight)\&=left(prod_{k=1}^infty p^{e_k} ight)prod_{k=1}^inftyleft( 1-frac{1}{p_k} ight)\&=n imesprod_{k=1}^inftyleft( 1-frac{1}{p_k} ight)end{align}$

證畢

序言中題目的解答

求 $2014^{2014^{2014}}$ 的最後兩位數
正確答案是 $36$

因為 $100$ 和 $2014$ 不互質，我們把它拆成 $100=4 imes 25$

注意到 $varphi(25)=25left( 1-frac{1}{5} ight)=20$

$2014^{2014^{2014}} equiv 2014^{2014^{2014} mod 20} pmod{25}$

再拆一次 $20=4 imes 5$

$2014^{2014}equiv 2014^2 imes left( 2014^{varphi(5)} ight)^{503}equiv 2014^2equiv4^2=16 pmod{5}$

這裡取 $16$ 因為要保證它能被 $4$ 整除，接著

$2014^{2014^{2014}}equiv2014^{16}equiv 14^{16}equiv36 pmod{100}$

因為 $36$ 能被 $4$ 整除，所以最後兩位是 $36$

求 $1^{2016}+2^{2016}+cdots + 2016^{2016}$ 除以 $2016$ 的餘數
正確答案是 $48$

因為 $2016=2^5 imes 3^2 imes 7$ ，我們只需分別找出這個數模 $32, 9, 7$ 的餘數

因為 $varphi(32) | 2016$

$egin{align}1^{2016}+2^{2016}+cdots+2016^{2016}&equiv 63 imes left(1^{2016}+2^{2016}+3^{2016}+cdots+32^{2016} ight) pmod{32}\ &=63 imes (1^{2016}+3^{2016}+5^{2016}+cdots+31^{2016})\&equiv 63 imes 16\&equiv 16end{align}$

因為 $varphi(7) | 2016$

$egin{align}1^{2016}+2^{2016}+cdots+2016^{2016}&equiv 288 imes left(1^{2016}+2^{2016}+cdots+7^{2016} ight) pmod{7}\ &=288 imes (1^{2016}+2^{2016}+cdots+6^{2016})\&equiv 288 imes 6\&equiv 6end{align}$

因為 $varphi(9) | 2016$

$egin{align}1^{2016}+2^{2016}+cdots+2016^{2016}&equiv 224 imes left(1^{2016}+2^{2016}+cdots+9^{2016} ight) pmod{9}\ &=224 imes (1^{2016}+2^{2016}+4^{2016}+5^{2016}+7^{2016}+8^{2016})\&equiv 224 imes 6\&equiv 3end{align}$