next up previous
下一頁: Wilson's Theorem 上一頁: Congruences 前一頁: 同餘的運算

Euler's Theorem

一般在解方程式時, 我們經常需要乘法反元素來幫忙. 所以當 m $ \in$ $ \mathbb {N}$, a $ \in$ $ \mathbb {Z}$ gcd(a, m) = 1 時, 若能確實知道哪些 b $ \in$ $ \mathbb {Z}$ 會滿足 ab $ \equiv$ 1(mod m) 將是很有用的. 由 Proposition 3.2.5 的證明中我們知可以利用輾轉相除法解 mx + ay = 1 的整數解來得到 b, 但這要在 ma 皆是具體的數時才能操作. 我們將利用 Euler's Theorem 對一般的 m, a 都能將 b 確實找到.

給定 m $ \in$ $ \mathbb {N}$, 若 a, b $ \in$ $ \mathbb {Z}$ 滿足 ab $ \equiv$ 1(mod m), 則由 Proposition 3.2.5ab 皆與 m 互質. 換言之, 我們只要考慮和 m 互質的數即可, 所以我們自然考慮 reduced residue system modulo m.

Lemma 3.3.1   給定 m $ \in$ $ \mathbb {N}$, 考慮 a $ \in$ $ \mathbb {Z}$ 滿足 gcd(m, a) = 1. 若 {r1,..., r$\scriptstyle \phi$(m)} 是一個 reduced residue system modulo m, 則 {ar1,..., ar$\scriptstyle \phi$(m)} 也是一個 reduced residue system modulo m.

証 明. 複習一下, {r1,..., r$\scriptstyle \phi$(m)} 是一個 reduced residue system modulo m 表示 gcd(m, ri) = 1 且對任意 i$ \ne$j, 皆有 ri $ \not\equiv$rj(mod m). 現要證明 {ar1,..., ar$\scriptstyle \phi$(m)} 也是 reduced residue system modulo m, 我們需要證明 gcd(m, ari) = 1 且對任意 i$ \ne$j 皆有 ari $ \not\equiv$arj(mod m).

現假設 gcd(m, ari)$ \ne$1, 即存在一質數 p 滿足 p| mp| ari. 因 p 是質數, 故由 Lemma 1.4.2p| ap| ri. 換言之, pm, a 的公因數或是 m, ri 的公因數. 此和 gcd(m, a) = 1 且 gcd(m, ri) = 1 相矛盾, 故得證 gcd(m, ari) = 1.

另一方面, 若 i$ \ne$j ari $ \equiv$ arj(mod m), 則由 gcd(m, a) = 1, 利用 Corollary 3.2.4 ri $ \equiv$ rj(mod m). 此和 ri $ \not\equiv$rj(mod m) 矛盾, 故得證 ari $ \not\equiv$arj(mod m). $ \qedsymbol$

前面提過, 給定 m $ \in$ $ \mathbb {N}$, 利用除以 m 同餘的分類, 我們可以將與 m 互質的數分成 $ \phi$(m) 類. 而將每一類中挑出一代表元素所成之集合就是一個 reduced residue system modulo m. 今假若 S = {a1,..., a$\scriptstyle \phi$(m)} 和 T = {b1,..., b$\scriptstyle \phi$(m)} 皆為 reduced residue system modulo m, 任取 ai $ \in$ S, 由於它代表與 m 互質的某一同餘類, 而 T 中也有一元素是在和 ai 同類的元素中挑出. 換言之, 存在 bj $ \in$ T 滿足 ai $ \equiv$ bj(mod m). 又由於這些 bj 兩兩皆不同類, 所以 ST 中元素在 modulo m 之下有一對一的對應關係. 也就是說經過適當的排序, 我們有 ai $ \equiv$ bi(mod m). 因此得 a1 ... a$\scriptstyle \phi$(m) $ \equiv$ b1 ... b$\scriptstyle \phi$(m)(mod m). 利用這個結果我們可以得證 Euler's Theorem.

Theorem 3.3.2 (Euler's Theorem)   給定 m $ \in$ $ \mathbb {N}$, 若 a $ \in$ $ \mathbb {Z}$ 滿足 gcd(m, a) = 1, 則

a$\scriptstyle \phi$(m) $\displaystyle \equiv$ 1(mod m).

証 明. 取 S = {r1,....r$\scriptstyle \phi$(m)} 為一個 reduced residue system modulo m. 首先我們證明 gcd(m, r1 ... r$\scriptstyle \phi$(m)) = 1. 若 gcd(m, r1 ... r$\scriptstyle \phi$(m))$ \ne$1, 即存在一質數 p 使得 p| m p| r1 ... r$\scriptstyle \phi$(m). 利用 Corollary 1.4.3 知存在 ri $ \in$ S 使得 p| ri, 也就是說 gcd(m, ri)$ \ne$1. 此和 S 是 reduced residue system modulo mri $ \in$ S 相矛盾, 故得證 gcd(m, r1 ... r$\scriptstyle \phi$(m)) = 1.

現由於 gcd(m, a) = 1, 故利用 Lemma 3.3.1 {ar1,..., ar$\scriptstyle \phi$(m)} 也是一個 reduced residue system modulo m, 因此得

r1 ... r$\scriptstyle \phi$(m) $\displaystyle \equiv$ (ar1) ... (ar$\scriptstyle \phi$(m)) $\displaystyle \equiv$ a$\scriptstyle \phi$(m)(r1 ... r$\scriptstyle \phi$(m))(mod m).

再因為 gcd(m, r1 ... r$\scriptstyle \phi$(m)) = 1, 故利用 Corollary 3.2.4 得證 a$\scriptstyle \phi$(m) $ \equiv$ 1(mod m). $ \qedsymbol$

給定 m $ \in$ $ \mathbb {N}$ a $ \in$ $ \mathbb {Z}$ 滿足 gcd(m, a) = 1, 若令 b = a$\scriptstyle \phi$(m) - 1, 則利用 Euler's Theorem 得知 ab $ \equiv$ a$\scriptstyle \phi$(m) $ \equiv$ 1(mod m). 因此我們找到了 a 在 modulo m 之下的乘法反元素.

Corollary 3.3.3   給定 m $ \in$ $ \mathbb {N}$, 若 a $ \in$ $ \mathbb {Z}$ 滿足 gcd(m, a) = 1, 則令 b = a$\scriptstyle \phi$(m) - 1, 會滿足 ab $ \equiv$ ba $ \equiv$ 1(mod m).

特別地, 當 m 是一個質數 p 時, Euler's Theorem 就是所謂的 Fermat's Little Theorem. 我們特別將它寫下來.

Theorem 3.3.4 (Fermat's Little Theorem)   給定一質數 p, 若 a $ \in$ $ \mathbb {Z}$ 滿足 p$ \nmid$a, 則

ap - 1 $\displaystyle \equiv$ 1(mod p).

特別地, 若令 b = ap - 2, 則 ab $ \equiv$ ba $ \equiv$ 1(mod p).

証 明. 因 p 是一質數, 由 p$ \nmid$a 之假設知 gcd(p, a) = 1. 又此時 $ \phi$(p) = p - 1, 故直接套用 Theorem 3.3.2 得證 ap - 1 $ \equiv$ 1(mod p). $ \qedsymbol$

p| a 時 Ferma's Little Theorem 並不對, 因為此時 a $ \equiv$ 0(mod p), 故 ap - 1 $ \equiv$ 0(mod p). 不過我們可以推導出下一個對任意整數 a 皆成立的式子.

Corollary 3.3.5   給定一質數 p, 則對任意整數 a 皆滿足

ap $\displaystyle \equiv$ a(mod p).

証 明. 因為 p 是質數所以對任意 a $ \in$ $ \mathbb {Z}$, 我們可以分成 p| ap$ \nmid$a 之情況處理. 當 p| a 時, 由於 a $ \equiv$ 0(mod p), 故得 ap $ \equiv$ 0 $ \equiv$ a(mod p). 當 p$ \nmid$a 時, 由 Theorem 3.3.4 ap - 1 $ \equiv$ 1(mod p), 故兩邊乘上 a 可得 ap $ \equiv$ a(mod p). $ \qedsymbol$


next up previous
下一頁: Wilson's Theorem 上一頁: Congruences 前一頁: 同餘的運算
Li 2007-06-28