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, 但這要在 m 和 a 皆是具體的數時才能操作. 我們將利用 Euler's Theorem 對一般的 m, a 都能將 b 確實找到.

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

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

証 明. 複習一下, {r₁,..., r_$\phi$(m)} 是一個 reduced residue system modulo m 表示 gcd(m, r_i) = 1 且對任意 i$\ne$j, 皆有 r_i $\not\equiv$r_j(mod m). 現要證明 {ar₁,..., ar_$\phi$(m)} 也是 reduced residue system modulo m, 我們需要證明 gcd(m, ar_i) = 1 且對任意 i$\ne$j 皆有 ar_i $\not\equiv$ar_j(mod m).

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

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

前面提過, 給定 m $\in$ $\mathbb {N}$, 利用除以 m 同餘的分類, 我們可以將與 m 互質的數分成 $\phi$(m) 類. 而將每一類中挑出一代表元素所成之集合就是一個 reduced residue system modulo m. 今假若 S = {a₁,..., a_$\phi$(m)} 和 T = {b₁,..., b_$\phi$(m)} 皆為 reduced residue system modulo m, 任取 a_i $\in$ S, 由於它代表與 m 互質的某一同餘類, 而 T 中也有一元素是在和 a_i 同類的元素中挑出. 換言之, 存在 b_j $\in$ T 滿足 a_i $\equiv$ b_j(mod m). 又由於這些 b_j 兩兩皆不同類, 所以 S 和 T 中元素在 modulo m 之下有一對一的對應關係. 也就是說經過適當的排序, 我們有 a_i $\equiv$ b_i(mod m). 因此得 a₁ ^... a_$\phi$(m) $\equiv$ b₁ ^... b_$\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^$\phi$(m) $$\equiv$$ 1(mod m).

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

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

r₁ ^... r_$\phi$(m) $$\equiv$$ (ar₁) ^... (ar_$\phi$(m)) $$\equiv$$ a^$\phi$(m)(r₁ ^... r_$\phi$(m))(mod m).

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

給定 m $\in$ $\mathbb {N}$ 及 a $\in$ $\mathbb {Z}$ 滿足 gcd(m, a) = 1, 若令 b = a^{$\phi$(m) - 1}, 則利用 Euler's Theorem 得知 ab $\equiv$ a^$\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^{$\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, 則

a^{p - 1} $$\equiv$$ 1(mod p).

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

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

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

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

a^p $$\equiv$$ a(mod p).

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