欧拉定理

前置芝士

欧拉函数\(\varphi(n)\) 表示 \(1\)~\(n\) 中与 \(n\) 互质的数的个数

数学定义如下

\[\varphi(n)=\sum\limits_{i=1}^n[gcd(i,n)==1] \]

欧拉函数是积性函数，即对于 \(\forall n,p\)，若\(gcd(n,p)=1\)，则有\(\varphi(np)=\varphi(n)*\varphi(p)\)。

显然，对于任意质数 \(p\)，有

\[\varphi(p)=p-1 \]

而对于任意整数，不难给出一个计算公式如下

若算数基本定理即 \(n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\) 成立，则有

\[\varphi(n)=n*\prod_{i=1}^m(1-\frac1{p_i}) \]

证明：容斥原理自己想（雾

定义

\(\forall~a~,~m~\in~Z^+~,\gcd(a,m)=1\)，则一定满足\(~a^{\varphi(m)}~\equiv~1~(mod~m)~\)。该定理被称作欧拉定理。

推导

记 \(x_i\) 为第i个与m互质的数，则共有\(\varphi(m)个x_i\)

设 \(p_i~=~a\times x_i\)

引理一：

\(\{p_i\}\) 间两两模 \(m\) 不同余，\(\{x_i\}\) 间两两模 \(m\) 不同余。

证明：

先证\(\{x_i\}\)间两两模 \(m\) 不同余：

因为\(~\forall~i~\in~[1,\phi(m)]~,~x_i~<~m~\)，故

\[~x_i\equiv x_i(mod~m) \]

又\(~\forall~i,j~\in~[1,\varphi(m)],i~\neq~j~\)都有\(~x_i~\neq~x_j~\)。于是

\[~x_i\not\equiv x_j(mod~m) \]

所以\(\{x_i\}\)间两两模 \(m\) 不同余

再证\(\{p_i\}\)间两两模 \(m\) 不同余：

反证法，若存在一对\(~i,j~\in~[1,\varphi(m)]~,~i\not=j~,p_i~\equiv~p_j~(mod~m)~\)，则

\[a~\times~x_i~\equiv~a~\times~x_j~(mod~m) \]

\[\Rightarrow~x_i~\equiv~x_j~(mod~m) \]

根据\(\{x_i\}\)间两两模\(m\)不同余，产生矛盾，于是\(\{p_i\}\)间两两模\(m\)不同余

证毕

引理2：

\(\forall~i~\in~[1,\varphi(m)]~,~p_i~\)与 \(m\) 互质。

证明

写出\(m,a,x_i,p_i\)的唯一分解式：

\[m~=~q_1^{c_1}~q_2^{c_2}~\dots~q_k^{c_k}\\ a=q_1^{d_1}~q_2^{d_2}~\dots~q_k^{d_k}\\ x_i~=~q_1^{e_1}~q_2^{e_2}~\dots~q_k^{e_k}\\ p_i~=~q_1^{e_1+d_1}~q_2^{e_2+d_2}~\dots~q_k^{e_k+d_k}\\ \]

则 \(\forall~i~,c_i~\neq~0~\)都有\(d_i=e_i=0\)，于是\(d_i+e_i~=~0\)。

于是 \(\forall~i\in[1,\varphi(m)]~,~p_i~\)与 \(m\) 互质。

证毕

根据上述引理，可得所有 \(p_i\) 的模\(m\)的解的集合与 \(\{x_i\}\) 相等，于是他们的积模\(m\)的值也相等。

于是有

\[\prod_{i=1}^{\varphi(m)}~p_i~\equiv~a^{\varphi(m)}~\prod_{i=1}^{\varphi(m)}~x_i~\equiv~\prod_{i=1}^{\varphi(m)}~x_i~(mod~m) \]

于是有 \(a^{\varphi(m)}~\equiv~1~(Mod~m)\) 。证毕。

（部分资料来自这里）