[數論] 歐拉定理 (Euler's theorem)、Wilson's theorem

參考資料
http://www.math.cornell.edu/~putnam/modular.pdf
http://www.millersville.edu/~bikenaga/number-theory/euler/euler.html (推薦)

Euler's theorem

定義 $a^{\varphi (n)}\equiv 1\; ($mod$\; n)$, 其中 $\varphi (n)$ 是 Euler's phi function, $(a,n)=1$.

證明：內容擷自下面兩段 YouTube 影片, 雖然影片是證明費馬小定理, 但仍不失一般性(費馬小定理是歐拉定理的特例.). 簡單來說, a mod n, 2a mod n, ..., (n-1)a mod n 的餘數的集合是 {1, 2, ..., n-1}. 例如a=3, n=5, (a, n)=1, 則 3 mod 5, 6 mod 5, ..., 12 mod 5 的餘數依序是 3, 1, 4, 2, 寫成集合是 {1, 2, 3, 4}.

我們得到式子 $a\cdot 2a\cdot ...\cdot (n-1)a\equiv 1\cdot 2\cdot ...\cdot (n-1)\equiv (n-1)! $ mod $n$

上式可改寫成 $(n-1)!\cdot a^{n-1}\equiv (n-1)!$ mod $n$.
將上式左右兩邊消去 $(n-1)!$, 即得 $a^{n-1}\equiv 1$ mod $n$. 證明完畢

Euler's theorem 可以簡化我們在計算某個數的高次方的餘數. 假設今天我們想知道 $7^{222}$ 除以 $10$ 的餘數, 亦即 $7^{222}$ 的個位數字.

方法1. 算出 $7^{222}$, 看個位數字. 這個方法很直觀, 若次方數字很小, 這個方法也許比較快, 但對於高次方, 例如這裡的 $222$, 顯然毫無效率可言.

方法2. 試圖看 $7$ 的次方數中, 個位數字有無規律. 依序列出後會發現 $7$ 的次方的個位數字會以 $1,9,3,7$ 的順序出現, 每四個數循環一次. 所以我們把 $222$ 除以循環週期 $4$, 得到餘數 $2$, 最後得到 $7^{222}$ 個位數字是 $9$. 這個方法很好用, 但遇到週期很長的題目, 甚至是看出不週期的時候, 這個方法就派不上用場.

如果知道 Euler's theorem, 我們就可以用第三種方法來解決這類問題.

方法3. 因為 $(7,10)=1$, 所以我們可以用 Euler's theorem. 因為 $\varphi (10)=4$, 所以我們知道 $7^{4}\equiv 1\; ($mod$\; 10)$. 接著再用方法2中, 看 $222$ 除以 $4$ 的餘數. 最後得到答案是 $9$

萬一....要是 $a$ 和 $n$ 不互質呢? 例如我把 $7^{222}$ 改成 $8^{222}$, 那不就不能直接套用 Euler's theorem 嗎? 此時我們要對 $n$ 做適當地分解.

因為 $10=2\times 5$, 所以我們分開求 $8^{222}$ 除以 $2$ 及 $8^{222}$ 除以 $5$ 的餘數. $8^{222}\equiv 0\; ($mod$\; 2)$; 另一方面, 因為 $(8,5)=1$, $\phi (5)=4$, 由 Euler's theorem 得知 $8^{\varphi (5)}\equiv 8^{4}\equiv 1\; ($mod$\; 5)$, 而 $222$ 除以 $4$ 的餘數是 $2$, 所以 $8^{222}\equiv 8^{55\times 4+2}\equiv 1\times 8^{2}\equiv 4\; ($mod$\; 5)$. 最後得到答案是 $4$(why?).

Beacuse $8^{222}=2a=5b+4$, we know that $b$ must be even. Let $b=2c$, then $5b+4=5(2c)+4=10c+4$. Therefore, $8^{222}\equiv 4\: ($mod$\: 10)$.

練習題
試求 $16^{198}$ 的末兩位數字. (答案：$96$)


有一個跟 Euler's theorem 的類似的定理, 叫做 Wilson's theorem. 下面的證明擷自影片內容.

Wilson's theorem: $p$ is prime iff $(p-1)!\equiv -1$ mod $p$.

<pf> If $p$ is prime, and $k\in \left \{ 1,2,...,p-1 \right \}$, then there exists two integers $a$ and $b$ such that $ak+bp=1$(according to the Euclidean algorithm). We have $ak+bp\equiv ak\equiv 1$ (mod $p$). It says that the modular multiplicative inverse of $k$ modulo $p$ exists.

The point is to to pair each number with its modular inverse. There are two exceptions: $k=1$ and $k=p-1$. The modular inverses of 1 and p-1 modulo p are equal to themselves (check: $1\times 1\equiv 1$ mod $p$, $(p-1)(p-1)\equiv 1$ mod $p$).

$(p-1)!\equiv 1\cdot (2\cdot 2^{-1})\cdot (3\cdot 3^{-1})...\cdot (p-1)\equiv p-1\equiv -1$ mod $p$. Q.E.D.

Note: $2^{-1}$ 是指 $2$ 的模反元素, 它會是 $\left \{ 2,3,...,p-2 \right \}$ 的某個元素. 同理, $3^{-1}$ 也會是 $\left \{ 2,3,...,p-2 \right \}$ 的某個元素, 且 $2^{-1}$ 和 $3^{-1}$ 不會相同, 不會有重複的問題. 下面是證明.

For two integers $a,b\in \left \{ 2,3,...,p-2 \right \}$. Assume $a$ and $b$ have the same modular multiplicative inverse modulo $p$, called $k$. $ak\equiv bk\equiv 1$ mod $p$.
$\Leftrightarrow ak-bk\equiv 0$ mod $p$
$\Leftrightarrow (a-b)k\equiv 0$ mod $p$

Since $k\in \left \{ 2,3,...,p-1 \right \}$, $(k,p)=1$, $(a-b)$ must be a multiple of $p$. We know that $a,b\in \left \{ 2,3,...,p-2 \right \}$, $0\leq (a-b)< p$. Therefore, $a=b$. Q.E.D.