歐拉定理 & 費馬小定理

費馬小定理

定義

若 \(p\) 為素數，\(\gcd(a, p) = 1\)，則 \(a^{p - 1} \equiv 1 \pmod{p}\)。

另一個形式：對於任意整數 \(a\)，有 \(a^p \equiv a \pmod{p}\)。

證明

設一個質數為 \(p\)，我們取一個不為 \(p\) 倍數的數 \(a\)。

構造一個序列：\(A=\{1,2,3\dots,p-1\}\)，這個序列有着這樣一個性質：

\[ \prod_{i=1}^{p-1}\space A_i\equiv\prod_{i=1}^{p-1} (A_i\times a) \pmod p \]

證明：

\[ \because (A_i,p)=1,(A_i\times a,p)=1 \]

又因為每一個 \(A_i\times a \pmod p\) 都是獨一無二的，且 \(A_i\times a \pmod p < p\)

得證（每一個 \(A_i\times a\) 都對應了一個 \(A_i\)）

設 \(f=(p-1)!\), 則 \(f\equiv a\times A_1\times a\times A_2\times a \times A_3 \dots \times A_{p-1} \pmod p\)

\[ \begin{aligned} a^{p-1}\times f &\equiv f \pmod p \\ a^{p-1} &\equiv 1 \pmod p \end{aligned} \]

證畢。

也可用歸納法證明：

顯然 \(1^p\equiv 1\pmod p\)，假設 \(a^p\equiv a\pmod p\) 成立，那麼通過二項式定理有

\[ (a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{p-1}a+1 \]

因為 \(\binom{p}{k}=\frac{p(p-1)\cdots (p-k+1)}{k!}\) 對於 \(1\leq k\leq p-1\) 成立，在模 \(p\) 意義下 \(\binom{p}{1}\equiv \binom{p}{2}\equiv \cdots \equiv \binom{p}{p-1}\equiv 0\pmod p\)，那麼 \((a+1)^p \equiv a^p +1\pmod p\)，將 \(a^p\equiv a\pmod p\) 帶入得 \((a+1)^p\equiv a+1\pmod p\) 得證。

歐拉定理

在瞭解歐拉定理（Euler's theorem）之前，請先了解歐拉函數。定理內容如下：

定義

若 \(\gcd(a, m) = 1\)，則 \(a^{\varphi(m)} \equiv 1 \pmod{m}\)。

證明

實際上這個證明過程跟上文費馬小定理的證明過程是非常相似的：構造一個與 \(m\) 互質的數列，再進行操作。

設 \(r_1, r_2, \cdots, r_{\varphi(m)}\) 為模 \(m\) 意義下的一個簡化剩餘系，則 \(ar_1, ar_2, \cdots, ar_{\varphi(m)}\) 也為模 \(m\) 意義下的一個簡化剩餘系。所以 \(r_1r_2 \cdots r_{\varphi(m)} \equiv ar_1 \cdot ar_2 \cdots ar_{\varphi(m)} \equiv a^{\varphi(m)}r_1r_2 \cdots r_{\varphi(m)} \pmod{m}\)，可約去 \(r_1r_2 \cdots r_{\varphi(m)}\)，即得 \(a^{\varphi(m)} \equiv 1 \pmod{m}\)。

當 \(m\) 為素數時，由於 \(\varphi(m) = m - 1\)，代入歐拉定理可立即得到費馬小定理。

擴展歐拉定理

定義

\[ a^b \equiv \begin{cases} a^{b \bmod \varphi(m)}, &\gcd(a,m) = 1, \\ a^b, &\gcd(a,m)\ne 1, b < \varphi(m), \\ a^{(b \bmod \varphi(m)) + \varphi(m)}, &\gcd(a,m)\ne 1, b \ge \varphi(m). \end{cases} \pmod m \]

解釋

讀者可能對第二行產生疑問，這一行表達的意思是：如果 \(b < \varphi(m)\) 的話，就不能降冪了。

主要是因為題目中 \(m\) 不會太大，而如果 \(b < \varphi(m)\)，自然複雜度是可以接受的。而如果 \(b \ge \varphi(m)\) 的話，複雜度可能就超出預期了，這個時候我們才需要降冪來降低複雜度。

證明

直觀理解

fermat1

需要知道的是，在 \(\pmod m\) 的條件下，\(a^b \bmod m\) 的取值範圍一定在 \([0, m)\)，而 \(a^i \bmod m = (a^{i-1} \bmod m) \times a \bmod m\)，那麼對於任意一個數 \(a\)，那麼很容易就能知道它的後繼，在有限的空間內這一定會形成一個循環。

在擴展歐拉定理中，循環分為純循環和混循環。其中純循環中不存在節點有兩個前驅，而混循環則反之。而 \(a^i \mod n\) 形成的序列可以是一個混循環，那麼只需要知道循環節的長度，和前面那一小段未進入循環節的長度，就可以根據這個性質來進行降冪了。

值得注意的是，無論是費馬小定理，還是（擴展）歐拉定理，一個很重要的應用就是降冪，從而將不可能的表達式化為可能。

形式證明

證明轉載自 synapse7，並進行了一些整理。

命題：\(a\) 的從 \(0\) 次，\(1\) 次到 \(b\) 次冪模 \(m\) 構成的序列中，存在 \(r\) 和 \(s\)，使得前 \(r\) 個數（即從 \(a^0 \bmod m\) 到 \(a^{r-1} \bmod m\)）互不相同，從第 \(r\) 個數開始，每 \(s\) 個數就循環一次。

證明：
- 由鴿巢定理易證。
  
  我們把 \(r\) 稱為 \(a\) 冪次模 \(m\) 的循環起始點，\(s\) 稱為循環長度。（注意：\(r\) 可以為 \(0\)）
  
  用公式表述為：\(\forall i \ge r, a^i \equiv a^{i+s} \pmod{m}\)
命題：\(a\) 為素數的情況，該式成立。

證明：
- 若模 \(m\) 不能被 \(a\) 整除，而因為 \(a\) 是一個素數，那麼 \(\gcd(a, m) = 1\) 成立，根據歐拉定理，容易證明該式成立。
- 若模 \(m\) 能被 \(a\) 整除，那麼存在 \(r\) 和 \(m'\) 使得 \(m = a^r m'\)，且 \(\gcd(a, m')=1\) 成立。所以根據歐拉定理有 \(a^{\varphi(m')} \equiv 1 \pmod{m'}\)。
  
  又由於 \(\gcd(a^r, m')=1\)，所以根據歐拉函數的求值規則，容易得到：\(\varphi(m) = \varphi(m') \times (a-1)a^{r-1}\)，即我們有：\(\varphi(m') \mid \varphi(m)\)。
  
  所以 \(a^{\varphi(m')} \equiv 1 \pmod {m'}, \varphi(m') \mid \varphi(m) \implies a^{\varphi(m)} \equiv 1 \pmod {m'}\)，即 \(a^{\varphi(m)}=km'+1\)，兩邊同時乘以 \(a^r\)，得 \(a^{r+\varphi(m)} = km + a^r\)（因為 \(m = a^r m'\)）
  
  所以對於 \(m\) 中素因子 \(a\) 的次數 \(r\) 滿足：\(a^r \equiv a^{r+\varphi(m)} \pmod m\)。我們可以簡單變換形式，得到推論：
  
  \[ b > r \implies a^b \equiv a^{r + ((b-r) \bmod \varphi(m))} \pmod {m} \]
  
  又由於 \(m = a^r m'\)，所以 \(\varphi(m) = \varphi(a^r) \varphi(m') \ge \varphi(a^r)=a^{r-1}(a-1) \ge r\)（tips：\(a\) 是素數，最小是 \(2\)，而 \(r \ge 1\)）。
  
  所以因為 \(\varphi(m) \ge r\)，故有：
  
  \[ a^r \equiv a^{r+\varphi(m)} \equiv a^{r \bmod \varphi(m)+\varphi(m)} \pmod m \]
  
  所以
  
  \[ \begin{aligned} a^b &\equiv a^{r+(b-r) \bmod \varphi(m)} \\ &\equiv a^{r \bmod \varphi(m) + \varphi(m) + (b-r) \bmod \varphi(m)} \\ &\equiv a^{\varphi(m) + b \bmod \varphi(m)} \end{aligned} \pmod m \]
  
  即 \(a^b\equiv a^{b \bmod \varphi(m)+\varphi(m)}\pmod m\)。
命題：\(a\) 為素數的冪的情況，該式成立。

證明：
- 不妨令 \(a = p^k\)，是否依然有 \(\forall r, a^{r} \equiv a^{r+\varphi(m)} \pmod m\)？
  
  答案是肯定的，由命題 1 可知存在 \(s\) 使得 \(a^s\equiv 1 \pmod m\)，所以 \(p^{\mathrm{lcm}(s,k)} \equiv 1 \pmod {m}\)，所以令 \(s'=\frac{s}{\gcd(s,k)}\) 時，我們能有 \(p^{s'k} \equiv 1 \pmod {m}\)。
  
  此時有關係：\(s' \mid s\) 且 \(s \mid \varphi(m)\)，且 \(r'= \lceil \frac{r}{k}\rceil \le r \le \varphi(m)\)，由 \(r',s'\) 與 \(\varphi(m)\) 的關係，依然可以得到 \(a^b\equiv a^{b \bmod \varphi(m)+\varphi(m)}\pmod m\)。
命題：\(a\) 為合數的情況，該式成立。

證明：
- 只證 \(a\) 拆成兩個素數的冪的情況，大於兩個的用數學歸納法可證。
  
  設 \(a=a_1a_2\)，其中 \(a_i=p_i^{k_i}\)，而 \(a_i\) 的循環長度為 \(s_i\)；
  
  則 \(s \mid \operatorname{lcm}(s_1,s_2)\)，由於 \(s_1 \mid \varphi(m),s_2 \mid \varphi(m)\)，那麼 \(\operatorname{lcm}(s_1,s_2) \mid \varphi(m)\)，所以 \(s \mid \varphi(m)\)，\(r=\max(\lceil \frac{r_i}{k_i} \rceil) \le \max(r_i) \le \varphi(m)\)；
  
  由 \(r,s\) 與 \(\varphi(m)\) 的關係，依然可以得到 \(a^b \equiv a^{b \bmod \varphi(m)+\varphi(m)}\pmod m\)。
  
  證畢。

習題

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：PeterlitsZo, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用