歐拉定理

目錄

• 歐拉定理
  • 前置芝士
    • 1、唯一質數分解定理（Unique factorisation theorem）
    • 2、互質（Coprime）、最大公因數（GCD）和最小公倍數（LCM）
    • 3、同餘關系（Congruence relations）
    • 4、同餘類(Residue class)、完全剩餘系(Complete residue system)、縮剩餘系(Reduced residue system)
    • 4.歐拉函數(Euler's totient function)
  • 正文

本文章大部分摘抄自這裡

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

\[n = 2^{e_1} \times 3^{e_2} \times 5^{e_3} \times ··· = \prod_{i=1}^N p^{e_k}_k

\]

其中 \(e_1 , e_2 , ··· \in \mathbb{N}\) , 我們稱這個分解為 \(n\) 的标準分解

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

它有幾個基本的性質，對于正整數\(a, b, n\)

• \(\gcd(a, b) = \gcd(a \pm b, b)\)
• \(\gcd(na, nb) = n\gcd(a , b)\)
• \(\gcd(a, b) = \Large \frac{a·b}{\rm{lcm}(a, b)}\)
• 斐蜀定理：存在整數 $x, y $使得 \(\gcd(a, b) = ax + by\)

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

\[a \equiv b (\!\!\!\!\!\!\mod n)

如果對于整數 \(a_1, a_2, b_1, b_2\) 有

\[a_1 \equiv b_1(\!\!\!\!\!\!\mod n)

\[a_2 \equiv b_2(\!\!\!\!\!\!\mod n)

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

\[a_1 \pm a_2 \equiv b_1 \pm b_2(\!\!\!\!\!\!\mod n)

也可以把它們相乘

\[a_1 a_2 \equiv b_1 b_2(\!\!\!\!\!\!\mod n)

通過這兩條性質，我們容易知道，如果 \(a \equiv b(\!\!\!\!\mod n)\) 那麼

\[P(a) \equiv P(b)\quad(\!\!\!\!\!\!\mod n)

對于任意整系數多項式 \(P(x)\) 都成立

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

\[ac \equiv bc(\!\!\!\!\!\!\mod n)

那麼隻有當 \(n, c\) 互質時才可以把兩邊的 \(c\) 直接約掉， 得到 \(a \equiv b (\!\!\!\!\mod n)\) 更一般的

\[a \equiv b (\!\!\!\!\!\!\mod \frac{n}{\gcd (n, c)})

通過一個整數模 \(n\) 的餘數，我們可以把所有整數分為 \(n\) 類，記

\[\bar{r}_n = \{ m \in \mathbb{Z} \mid mn + r\}

為模 \(n\) 餘 \(r\) 的同餘類(也叫剩餘類)舉個例子

\[\bar{4}_10 \{ ···,-16, -6, 4, 14, 24,··· \}

是模\(10\)餘\(4\)的同餘類 (即餘數都是\(4\)，對于負數先\(+mod\)在\(\%mod\)）

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

\[R_n = \{ r_0, r_1, r_2 ···,r_{n - 1} \}

其中$r_0 \in \overline{0_n}, r_1 \in \overline{1_n}, r_2 \in \overline{2_n},···, r_{n-1} \in \overline{(n-1)_n} $

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

我們稱\(R_n = \{ 0, 1, ···, n - 1 \}\) 為模 \(n\) 的最小非負完全剩餘系（最小非負完系）

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

\[\Large\Phi_n = \{ c_1, c_2, ···, 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, ···, c_{\varphi(n)}\}\) 滿足 \(1 \leqslant c_1, c_2, ···，c_{\varphi(n)} \leqslant n - 1\), 那麼稱其為模 \(n\) 的最小正縮剩餘系（最小正縮系）。

對于正整數 \(n\) , \(\varphi(n)\) 代表 [小于 \(n\) 的正整數中和 \(n\) 互質的數] 的個數，這個函數被稱作歐拉函數；

歐拉還告訴我們：

\[\frac{\varphi(n)}{n} = \prod_{p \mid n} \large(1 - \frac{1}{p})

其中 \(p\) 取到 \(n\) 的所有質因數

是以我們可以很友善的計算一個正整數歐拉函數的值，比如

\[\varphi(1926) = \varphi(2 \times 3^2 \times 107) = 1926(1 - \frac{1}{2})(1 - \frac{1}{3})(1 - \frac{1}{107}) = 636

歐拉函數還有一些非常有用的性質:

• 如果正整數 \(n >2\) 那麼 \(\varphi(n)\)
• 如果 \(n \mid N\) ,那麼 \(\varphi(n) \mid \varphi(N)\)
• 對于正整數 \(a, n\) 有 \(n \mid \varphi(a^n - 1)\)
• 對于正整數 \(m ,n\) 有 \(\varphi(mn) = \varphi(m)\varphi(n)\Large\frac{\gcd(m,n)}{\varphi(\gcd(m,n))}\)
• 特别地，如果 \(m, n\) 互質，那麼 \(\varphi(mn) = \varphi(m)\varphi(n)\)
• 對于正整數 \(n\) 有 \(\sum_{d \mid n} \varphi(d) = n\)
• 對于正整數 \(n\) 有 \(\sum_{1 \leqslant k \leqslant n, \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, ···c_{\varphi(n)}\}

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

\[a \Phi_n = \{ ac_1, ac_2, ···, ac_{\varphi(n)} \}

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

\[ac_i \equiv ac_j \pmod n

其中 \(i \ne j\) ,因為 \(a, n\) 互質可以将兩邊消去 \(a\), 那麼就得到

\[c_i \equiv c_j \pmod n

這是不可能的，因為 \(\Phi_n\) 中的互相模 \(n\) 不同餘，出現沖突了！

接下來的思路就比較清晰了，因為 \(\Phi_n\) 和 \(a\Phi_n\) 都是模 \(n\) 的縮系

\[\prod^{\varphi(n)}_{i = 1}c_i \equiv \prod^{\varphi(n)}_{i = 1}ac_i = a^{\varphi(n)} \prod^{\varphi(n)}_{i = 1}c_i \pmod n

顯然

\[\gcd(n, \prod^{\varphi(n)}_{i = 1} c_i) = 1

是以可以兩邊消去它

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

另外，如果我們讓 \(n = q\) 是一個質數，我們就可以從歐拉定理推出費馬小定理（Feramt's little theorem）

如果 \(p\) 是質數，那麼 \(p \mid n^p - n\) 對于任意整數 \(n\) 都成立

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

\[(n ＋ 1) ^　p - (n + 1) = \sum^{p - 1}_{r = 1} \dbinom{p}{r} n^r + n ^ p - n

當 \(1 \leqslant r \leqslant p - 1\) 時，二項次系數 \(\dbinom{p}{r} = \Large\frac{p!}{(p -r)!r!}\) 的分子中有 \(p\) ，分母中每一個乘子都不能整除 \(p\) （因為 \(p\) 是質數），是以 \(p\) 能夠整除 \(\dbinom{p}{r}\), 進而得到 \(p \mid (n + 1)^p - (n + 1)\)。當 \(n = 0\) 時顯然成立，是以定理成立

接下來我們看看如何證明

\[\frac{\varphi(n)}{n} = \prod_{p\mid n}\large(1 - \frac{1}{p})

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

如果要使 \(\gcd(p^e, k) \ne 1\), 隻能讓 \(k\) 等于 \(p\) 的倍數

在 \(1 \leqslant k \leqslant p^e\) 範圍内， \(p\) 的倍數有 \(p,2p,3p,···,p^{e-1}p = p^e\) 總共 \(p^{e - 1}\) 個，是以

\[\varphi(p^e) = p^e - p^{e - 1} = p^e(1 - \frac{1}{p})

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

\[S = \{ (m,n) \mid m \in \Phi_m , n \in \Phi_n \}

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

如果我們證明存在一個雙射 \(f: \Phi_{mn} \to S\) ,就證明了 \(\varphi(mn) = \varphi(m)\varphi(n)\)

我們讓

\[f(a) = (a\!\!\!\!\!\mod m, a \!\!\!\!\!\mod n)

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

\[a \equiv b \pmod m

\[a \equiv b \pmod n

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

如果正整數 \(r_1,r_2\) 和正整數 \(\gcd(n_1,n_2) = 1\) ,同餘方程組

\[x \equiv r_1 \pmod {n_1}

\[x \equiv r_2 \pmod {n_2}

在 \(0 \leqslant x < n_1n_2 範圍内有且隻有一個解\)

通過中國剩餘定理我們能夠證明 \(f\) 是滿射， 是以 \(f\) 是雙射

是以對于 \(\gcd (m,n) = 1\) 就有 \(\varphi(mn) = \varphi(m) \varphi(n)\)，假設 \(n\) 的标準分解為

\[n = 2^{e_1} \times 3^{e_2} \times 5^{e_3} \times ··· = \prod^{\infty}_{k = 1}p_k^{e_k}

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

\[\varphi(n) = \varphi(\prod^{\infty}_{k = 1}p_k^{e_k}) = \prod^{\infty}_{k = 1}\varphi(p_k^{e_k}) = \prod^{\infty}_{k = 1}p_k^{e_k}(1 - \frac{1}{p_k})

\[= (\prod^{\infty}_{k = 1}p_k^{e_k})\prod^{\infty}_{k = 1}(1 - \frac{1}{p_k}) = n \times \prod^{\infty}_{k = 1}(1 - \frac{1}{p_k})

證畢。