有關歐拉定理
Last updated on October 28, 2024
Contents
前言
如副標,只是記錄一下自己複習的歐拉定理證明流程 owo。
所以才沒有專屬放上精美的封面
正文
創建兩個集合,$S$ 包含所有小於且與 $n$ 互質的不重複的數;$S_a$ 則是 $S$ 中的所有元素都乘上一個與 $n$ 互質的數 $a$。
$$ \begin{align*} &\text{let}\quad S = \set{e\mid \forall\, e(e\ \bot\ n) \wedge (0< e < n)};\ \Rightarrow |S|=\varphi(n)\\ &\text{let}\quad S_a=\set{a\cdot e\mid \forall\,e\in S},\enspace a\ \bot\ n \end{align*} $$
證明:$S_a$ 中的元素在模 $n$ 之下跟 $S$ 中的元素是完全相同且不重複的。
$$ \begin{align*} &\text{Notice that if}\quad ae_1\equiv ae_2 \pmod n\\ &\Rightarrow a(e_1-e_2)\equiv 0 \pmod n\\ \end{align*} $$
然而,因為 $a$ 與 $n$ 互質、$e_1 - e_2$ 也不可能大於 $n$,因此唯一可能的就只有 $e_1 = e_2$。
但因為 $S$ 中的元素不重複,故此條件不可能符合,進而導致此假設不可能成立。因此在 $S_a$ 中的元素在模 $n$ 之下是完全不重複$^{(1)}$、小於 $n$ $^{(2)}$、且與 $n$ 互質的$^{(3)}$。
如要符合 (1) & (2) & (3),代表 $S_a$ 中的元素會完全與 $S$ 中的一樣。因此得出:
$$ \begin{align*} \prod_{e\ \in\ S}e &\equiv \prod_{\varepsilon\ \in\ S_a}\varepsilon \pmod n\\ &= \prod_{e\ \in\ S}ae\\ &= a^{|S|}\prod_{e\ \in\ S}e\\ &= a^{\varphi(n)}\prod_{e\ \in\ S}e\\ \end{align*} $$
通過消去左右兩邊元素的乘積(因為 $\prod e$ 仍與 $n$ 互質),得出證明:
$$ \begin{align*} \prod_{e\ \in\ S}e &\equiv a^{\varphi(n)}\prod_{e\ \in\ S}e \pmod n\\ \Rightarrow a^{\varphi(n)} &\equiv 1 \pmod n\ _\blacksquare \end{align*} $$