---
title: Euler Theorem
tags: crypto
lang: zh_tw
---

* [筆記總覽](https://hackmd.io/@LJP/rkerFdnqS)

[TOC]

# Euler's Theorem
參考 [Euler’s Theorem: proof by modular arithmetic](https://mathlesstraveled.com/2017/11/30/eulers-theorem-proof-by-modular-arithmetic/)

請先閱讀前一章節 [Euler's phi Function](https://hackmd.io/@LJP/r1ujih8IY)

若 $a, m$ 互質, 則:
$$
a^{\phi(m)} \equiv 1\ (mod\ m)
$$

> 加強版的 [Fermat's Little Theorem](https://hackmd.io/@LJP/ry_Ei3L8Y)

## Proof
$M$ 為在 $Z_M^*$ 中所有跟 $m$ 互質的數字的集合

$M = \{M_1, M_2, ..., M_{\phi(m)}\}, x \perp m, x \in M$

定義 $A$ 為 $M$ 的所有元素都乘上 $a$ 的集合
$A = \{A_1 = aM_1, A_2 = aM_2, ..., A_{\phi(m)} = aM_{\phi(m)}\}$

因為 $a, m$ 互質，將 $A$ 中所有元素都 $mod\ m$，將這個新集合叫做 $A^{'}$
會發現 $A^{'}, M$ 這兩個集合一樣 !

根據上面特性，以下式子成立
$$
\prod_{i = 1}^{\phi(m)}A_i \equiv \prod_{i = 1}^{\phi(m)}M_i\ (mod\ m)
$$

而 $\prod_{i = 1}^{\phi(m)}A_i$ 可以提出 $\phi(m)$ 個 $a$

$$
\prod_{i = 1}^{\phi(m)}A_i = a^{\phi(m)}\prod_{i = 1}^{\phi(m)}M_i
$$

$$
\begin{split}
\prod_{i = 1}^{\phi(m)}A_i &\equiv \prod_{i = 1}^{\phi(m)}M_i\ (mod\ m) \\
a^{\phi(m)}\prod_{i = 1}^{\phi(m)}M_i &\equiv \prod_{i = 1}^{\phi(m)}M_i\ (mod\ m) \\
a^{\phi(m)} &\equiv 1\ (mod\ m) \\
\end{split}
$$

得證