模運算/費馬小定理

費馬小定理

如果 $p$ 是一個素數，而 $a$ 是一個整數，則

$a^{p}\equiv a{\pmod {p}}$

示例：3 的冪 讓我們來看看一個數在模運算下的冪。我們將檢視 $\displaystyle 3,3^{2},3^{3},3^{4}...$ 我們將在一個素數 $\displaystyle p$ 模下進行計算。首先，我們將選擇 $\displaystyle p=7$。我們可以計算每個數，然後進行模運算，例如 $\displaystyle 3^{4}=3\times 3\times 3\times 3=81\equiv 4\,\mathrm {mod} \,7$ $\displaystyle 3^{5}=3\times 3\times 3\times 3\times 3=243\equiv 5\,\mathrm {mod} \,7$ 但是，直接從 $\displaystyle 3^{n}$ 計算 $\displaystyle 3^{n+1}$ 會更快，如下所示 $\displaystyle 3^{1}=3\quad \quad \quad \equiv 3\,\mathrm {mod} \,7$ $\displaystyle 3^{2}=3\times 3=9\equiv 2\,\mathrm {mod} \,7$ $\displaystyle 3^{3}=2\times 3=6\equiv 6\,\mathrm {mod} \,7$ $\displaystyle 3^{4}=6\times 3=18\equiv 4\,\mathrm {mod} \,7$ $\displaystyle 3^{5}=4\times 3=12\equiv 5\,\mathrm {mod} \,7$ $\displaystyle 3^{6}=5\times 3=15\equiv 1\,\mathrm {mod} \,7$ $\displaystyle 3^{7}=1\times 3=3\equiv 3\,\mathrm {mod} \,7$ $\displaystyle 3^{8}=3\times 3=9\equiv 2\,\mathrm {mod} \,7$ 很明顯，這個模式是重複的。這是因為 $\displaystyle 3^{6}\equiv 1\,{\bmod {\,}}7$. 即使不做計算，也很清楚這個模式必須在某個地方重複。對於 $\displaystyle 3^{n}\,{\bmod {\,}}7$，最多有 7 種不同的可能數字，所以如果我們計算 $\displaystyle n=1,2,3,4,5,6,7,8$，一定會在裡面找到重複的答案。 注意： 這是抽屜原理的應用——鴿子比抽屜多，因此一個抽屜必須包含兩隻鴿子。如果你感興趣，請點選鴿子圖示，閱讀有關抽屜原理的更多資訊 鴿子： 3 的冪 $\displaystyle {\bmod {\,}}7$. 抽屜： 七個可能的餘數 $\displaystyle {\bmod {\,}}7$. 一旦某個數字重複，從那個數字首次出現的地方開始，後面的序列就必須與之前的序列相同。我們甚至可以看到，我們會在重複第一次發生的地方得到一個 1 然後是一個 3。為什麼呢？ 假設我們有一個重複的數字，換句話說 $\displaystyle 3^{a}\equiv 3^{a+b}$，其中 a 和 b 是正數。那麼 $\displaystyle 3^{a}\equiv 3^{a}3^{b}$，我們可以將兩邊都除以 $\displaystyle 3^{a}$，得到 $\displaystyle 1\equiv 3^{b}$，即更早出現的重複。只需要稍微注意一下。在模算術中，並不總是允許除以公因數。我們在這裡允許進行除法，因為我們之前使用歐幾里德演算法確定了對素數進行模運算。我們知道 $\displaystyle 3^{n}\,\mathrm {mod} \,7$ 不為零，因為否則 3 將是 7 的一個因數，而 7 是素數。

關於模運算需要注意的是，我們不能隨意地對所有數字進行取模運算。例如，在 $\displaystyle {\bmod {\,}}7$ 的情況下，$\displaystyle 3^{8}$ 中的 $\displaystyle 8$ 的指數不能直接替換為 $\displaystyle 1$，因為 $3^{8}\neq 3^{1}\,{\bmod {7}}$。需要特別注意的是指數。在諸如 $\displaystyle 1000x\,{\bmod {7}}$ 和 $\displaystyle (1000+x)\,{\bmod {7}}$ 的表示式中，將 1000 替換為 $\displaystyle 6x\,{\bmod {7}}$ 和 $\displaystyle (6+x)\,{\bmod {7}}$，甚至 $\displaystyle -x\,{\bmod {7}}$ 和 $\displaystyle (x-1)\,{\bmod {7}}$ 是可以的。

練習：3 的冪 現在輪到你了。執行與示例中相同的操作，但這次針對 $\displaystyle p=11$。

這裡 3 沒有什麼特殊之處。我們可以對其他數字進行相同的練習 $\displaystyle a$，其中 $\displaystyle a=1,2,4,5\,or\,6$。我們可能會更快地達到 $\displaystyle a^{n}\equiv 1$，對於 $\displaystyle a=1$，我們一定會這樣，但我們仍然會得到 $\displaystyle a^{(p-1)}\equiv 1\,{\pmod {p}}$。

我們將透過多種方式證明這一點。之所以要費力地證明它，是因為它有助於我們看到證明結果的不同方法。在本例中，它主要是一種展示可以使用不同符號的方式。證明的第三種變體還將介紹乘性函式的概念，這在後面會很重要。