学习笔记：证明欧拉定理
chenxi797
·
·
算法·理论
前置知识：欧拉函数
什么是欧拉定理？
若 \gcd(a,b) = 1，则：
a^{\varphi(n)} \equiv 1 \ (\bmod \ p)
简单证明
设集合：
S = \{x \ | \ 1 \le x \le n,\gcd(x,n) = 1\}
不难看出，集合大小为 \varphi(n)。
将集合内每一个数 n 乘以 \gcd(a,n) = 1 的数 a，得到：
x_1x_2 \cdots x_{\varphi(n)} \equiv (ax_1)(ax_2) \cdots (ax_{\varphi(n)}) \ \ (\bmod \ n)
把 a^{\varphi(n)} 提出来，得：
x_1x_2 \cdots x_{\varphi(n)} \equiv a^{\varphi(n)} (x_1x_2 \cdots x_{\varphi(n)}) \ \ (\bmod \ n)
消去公因子得：
a^{\varphi(n)} \equiv 1
证毕。