[數論] 歐拉定理 (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.

[數論] 歐拉函數(Euler's Phi Function)

參考資料
EulerTheorem-Silverman http://palmer.wellesley.edu/~ivolic/pdf/Classes/USEM/EulerTheorem-Silverman.pdf

定義2 一個數論函數 $f(n)$, 若 $(m,n)=1$, 具有性質 $f(mn)=f(m)f(n)$, 則稱 $f(n)$ 為「積性函數(multiplicative function)」. 若不論有無 $(m,n)=1$, 上式都成立, 則稱 $f(n)$ 為「完全積性函數(complete multiplicative function)」.

例2 試證: $h_{\lambda }(n)=n^{\lambda }$($\lambda$為常數)是完全積性函數.
<pf> 設 $n=n_{1}n_{2}$, 無論 $n_{1}$ 與 $n_{2}$ 是否互質, 都有 $h_{\lambda }(n)=h_{\lambda }(n_{1}n_{2})=(n_{1}n_{2})^{\lambda }=(n_{1})^{\lambda }(n_{2})^{\lambda }=h_{\lambda }(n_{1})h_{\lambda }(n_{2})$. 由定義得知, $h(n)$ 是完全積性函數.

性質2 若積性函數 $f(n)$ 不恆等於 $0$, 則必有 $f(1)=1$.
<pf> 設 $f(n)\neq 0$. 因為 $f(n)$ 為積性函數, 所以有 $f(n)=f(n\cdot 1)=f(n)f(1)$, 從而 $f(1)=1$.

定義3 小於或等於正整數 $n$ 且與 $n$ 互質的正整數個數稱為 $n$ 的歐拉函數(Euler's function), 記為 $\varphi (n)$.

1. $\phi (1)=1$
2. 若 $n=p$ 是質數, 因為凡是小於 $p$ 的正整數均與 $p$ 互質, 故 $\varphi (p)=p-1$.
3. 若 $n=p^{k}$,$k\in \mathbb{N}$, 亦即 $n$ 是某個質數的次方. 凡是 $p$ 的倍數都不列入. 這些 $p$ 的倍數中, 最大的是 $p^{k}=p^{k-1}p$, 故總共有 $k-1$ 個 $p$ 的倍數.(例如要知道 $\varphi(27)$, 因為 $27=3^{3}$, 故有 $3$, $2\cdot 3$, $3\cdot 3...,$ $3^{2}\cdot 3$, 總共 $3^{2}$個 $3$ 的倍數.). 因此 $\phi (p^{k})=p^{k}-p^{k-1}=p^{k}(1-\frac{1}{p})$.
4. 對於一般正整數 $N$, 對 $n$ 做質因數分解, 得到 $N=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{n}^{k_{n}}$. 則 $\phi (N)=\phi (p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{n}^{k_{n}})=\phi (p_{1}^{k_{1}})\phi (p_{2}^{k_{2}})...\phi (p_{n}^{k_{n}})$ (這裡用到了 Euler's function 是積性函數的性質, 證明在文末).

公式：$\phi (N)=N\cdot \left ( 1-\frac{1}{p_{1}} \right )\left ( 1-\frac{1}{p_{2}} \right )...\left ( 1-\frac{1}{p_{n}} \right )$

證明：Euler's function 是積性函數
<pf> If p and q are prime, then $\varphi (pq)=(pq-1)-(q-1)-(p-1)=pq-(p+q)+1=(p-1)(q-1)=\varphi (p)\phi (q)$.
$(q-1)$ 是 $p$ 的倍數的個數, $(p-1)$ 是 $q$ 的倍數的個數.

底下介紹一些歐拉函數的推廣.

Euler's theorem(當要對一個高次方的數取餘數)  http://en.wikipedia.org/wiki/Euler's_theorem
RSA加密演算法 http://en.wikipedia.org/wiki/Euler's_totient_function