有關歐拉定理

Last updated on October 28, 2024

Contents

  1. 前言
  2. 正文

前言

如副標,只是記錄一下自己複習的歐拉定理證明流程 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*} $$


有關歐拉定理
https://phantom0174.github.io/2023/02/about-eulers-theorem/
Author
phantom0174
Posted on
March 16, 2023
Updated on
October 28, 2024
Licensed under