如何优雅地证明欧拉函数的积性and欧拉定理

主要是从剩余类入手的证明，又短又简洁，甚至证明只有两句话！ 剩余类似乎存在什么奇妙的抽代意义，但是我还没学到那里……轻喷，轻喷。 _____ # 剩余类相关定义 ## 剩余类 定义 1.1 > 记在模 $m$ 意义下，全部对 $m$ 同余的整数组成的集合，叫做 $m$ 的一个剩余类。 那么显然对于一个固定的模 $m$，有 $m$ 个剩余类，分别同余 $0,1,2\cdots m-1$，分别记作 $\mathrm{ Z}_{m,0},\mathrm{ Z}_{m,1},\mathrm{ Z}_{m,2}\cdots,\mathrm{ Z}_{m,m-1}$ 。记所有剩余类组成的集合是 $\mathrm{ Z}_{m}$ 。 考虑定义剩余类之间的运算 $+$ 和 $\times $ ： $$ \mathrm{ Z}_{m,a}+\mathrm{ Z}_{m,b}=\mathrm{ Z}_{m,a+b} $$ $$ \mathrm{ Z}_{m,a}\times \mathrm{ Z}_{m,b}=\mathrm{ Z}_{m,a\times b} $$ 其中 $a+b$ 和 $a\times b$ 是在模 $m$ 意义下的数加和数乘。并且可以知道，对于全体模 $m$ 意义下的剩余类 $\mathrm{ Z}_{m}$ 而言，$<\mathrm{ Z}_{m},+,\times>$ 本身是一个环。考虑如下： 1、首先 $(\mathrm{ Z}_{m},+)$ 显然是一个阿贝尔群。 2、其次 $(\mathrm{ Z}_{m},\times )$ 显然具有结合律，但是如果对于某个剩余类 $\mathrm{ Z}_{m,p}$ $(p,m)>1$ ，就说明了 $\mathrm{ Z}_{m,p}$ 本身不存在逆元 ，所以可知道 $(\mathrm{ Z}_{m},\times )$ 是一个半群。 3、同时可知在 $(\mathrm{ Z}_{m},\times )$ 中，高优先级运算 $\times $ 对低优先级运算 $+$ 有分配律。 综上，$(\mathrm{ Z}_{m},+,\times )$ 是一个环。并且不难知道 $\mathrm{ Z}_{m,0}$ 就是这个环中的零元。 但是这个环并不是正则环。考虑我们熟知的正则环 $<\mathbb Z,+,\times>$ 和 $<\mathbb R,+,\times >$ 内都不存在零因子 $a,b$ 使得 $a\neq 0,b\neq 0$ 且 $a\times b=0$ 。但是在模运算下这是可能成立的，比如可以设 $m=pq$ ，其中 $p\not \equiv q\pmod m$，那么就有 $\mathrm{ Z}_{m,p} \times \mathrm{ Z}_{m,q}=\mathrm{ Z}_{m,0}$ ，此时 $p,q$ 就均为 $\mathrm{ Z}_{m}$ 的零因子。所以可知剩余类环并不是正则的。 ## 互素剩余类 ### 定义1.2 > 若对于一个模 $m$ 意义下的剩余类 $\mathrm{ Z}_{m,k}$ 满足 $(m,k)=1$ ，那么称 $\mathrm{ Z}_{m,k}$ 为模 $m$ 的一个互素剩余类。 为了方便起见，记某个互素剩余类 $\mathrm{ Z}_{m,k}$ 为 $\mathrm{\zeta}_{m,k}$ 。同时可知这样的 $\mathrm{\zeta}_{m,k}$ 共有 $\varphi(m)$ 个。 # 剩余系 ## 定义 ### 定义2.1 > 如果对于一个集合 $\rm S$ ，满足 $\mathrm{|S|}=m$ 且 $\forall i\not=j,i\in \mathrm{S},j\in \mathrm{S}$ 有 $$ i\in\mathrm{ Z}_{m,p}, j \in \mathrm{ Z}_{m,q}, \mathrm{ Z}_{m,p}\not=\mathrm{ Z}_{m,q} $$ > 那么记这个集合为模 $m$ 的一个完全剩余系。 ### 定义2.2 > 如果对于一个集合 $\rm S$ ，满足 $\mathrm{|S|}=m$ 且 $\forall i\not=j,i\in \mathrm{S},j\in \mathrm{S}$ 有 $$ i\in\mathrm{ \zeta}_{m,p}, j \in \mathrm{ \zeta}_{m,q}, \mathrm{ \zeta}_{m,p}\not=\mathrm{ \zeta}_{m,q} $$ > 那么记这个集合为模 $m$ 的一个简化剩余系。 可知模 $m$ 的一个完全剩余系的大小是 $m$ ，一个简化剩余系的大小是 $\varphi(m)$ 。 ## 性质 ### 定理2.1 > 设 $m\in \mathbb Z_+$，$k,p\in \mathbb Z$ 且 $(k,m)=1$ ，则 > > （1）当 $x$ 遍历模 $m$ 的一个完全剩余系 $\mathrm{S}$ 时，$kx+p$ 也遍历模 $m$ 的一个完全剩余系 $\mathrm{S'}$ 。 > > （2）当 $x$ 遍历模 $m$ 的一个简化剩余系 $\mathrm{T}$ 时，$kx$ 也遍历模 $m$ 的一个简化剩余系 $\mathrm{T'}$ 。 证： （1）考虑只需要证对于任意两个模 $m$ 下不同余的 $x_i,x_j$ ， $kx_i+p,kx_j+p$ 也是不同余的，那么就可以得证。 考虑反证法。若 $kx_i+p\equiv kx_j+p\pmod m$，则有 $$ kx_i\equiv kx_j\pmod m $$ 那么由于 $(k,m)=1$ 且根据定理 > 若 $ac\equiv bc\pmod m$，且 $(m,c)=d$，则 $a\equiv b \pmod{\frac{m}{d}}$ 。 可知 $x_i\equiv x_j\pmod m$ 。矛盾。 （2）由（1）可以知道 $kx_i$ 彼此之间不同余，且因为 $(k,x_i)=(k,m)=1$ ，所以可知遍历的是一个简化剩余系。 ### 定理2.2 > 设 $(m_1,m_2)=1$ ，则： > > （1）当 $x,y$ 分别遍历模 $m_1,m_2$ 的一个完全剩余系时，$m_2x+m_1y$ 也遍历模 $m_1m_2$ 的一个完全剩余系。 > > （2）当 $x,y$ 分别遍历模 $m_1,m_2$ 的一个简化剩余系时，$m_2x+m_1y$ 也遍历模 $m_1m_2$ 的一个简化剩余系。 证： （1） 还是从证明互不同余这方面来考虑。如果存在 $x_1,x_2,y_1,y_2$ 使得 $$ m_{2} x_{1}+m_{1} y_{1} \equiv m_{2} x_{2}+m_{1} y_{2}\pmod {m_{1} m_{2}} $$ 那么首先有 $$ m_{2} x_{1}+m_{1} y_{1} \equiv m_{2} x_{2}+m_{1} y_{2}\pmod {m_{1}} $$ 即 $$ m_{2} x_{1} \equiv m_{2} x_{2}\pmod {m_{1}} $$ 那么因为 $(m_1,m_2)=1$ ，所以有 $$ x_{1} \equiv x_{2}\pmod {m_{1}} $$ 同理可知 $$ y_{1} \equiv y_{2}\pmod {m_{1}} $$ 那么就可以知道，当 $x_1,x_2$ 不同余，$y_1,y_2$ 不同余的时候，$m_2x+m_1y$ 也是不同余的。 （2） 首先由于 $(x,m_1)=(y,m_2)=1$ ，所以 $(m_2x+m_1y,m_1)=1$ 且 $(m_2x+m_1y,m_2)=1$，所以可知 $m_2x+m_1y$ 一定会属于 $m_1m_2$ 的简化剩余系。同时由（1）中的结论可知这 $\varphi(n)\varphi(m)$ 个结果是两两不同余的。于是就只需要证明 $m_1m_2$ 的简化剩余系中，均属于这 $\varphi(n)\varphi(m)$ 个元素组成的集合即可。 对于任意一个与 $m_1m_2$ 互质的元素 $q$，由（1）可知必定存在一组 $(s,t)$ 使得 $$ q\equiv m_2s+m_1t\pmod {m_1m_2} $$ 考虑若 $(s,m_1)>1$ ，则有某个$d>1,d|s$ 满足 $d|m_1\Longrightarrow d|m_1m_2$ 的同时 $d|q$ ，那么 $(m_1m_2,q)\geq d$ ，不符合互质的假设。故可知 $(s,m_1)=1$ ，同理 $(t,m_2)=1$ ，故证毕。 ## 推论 由定理 2.2(2) 可知，分别遍历模 $m_1$ 和 $m_2$ 的简化剩余系的 $x$ 和 $y$ ，在 $(m_1,m_2)=1$ 时，$m_1y+m_2x$ 遍历模 $m_1m_2$ 的一个简化剩余系。 根据乘法原理，可以得到 $\varphi(m_1)\cdot \varphi(m_2)=\varphi(m_1m_2)$ 。 这也就证明了欧拉函数 $\varphi(x)$ 是积性函数。 # 欧拉定理 > 若 $(a,m)=1$ ，则有 $a^{\varphi(m)}\equiv 1\pmod m$ . 若设 $(x_1,x_2,x_3\cdots x_{\varphi(m)})$ 是模 $m$ 的一个简化剩余系，那么由定理2.1(2)可知 $(ax_1,ax_2,ax_3\cdots ax_{\varphi(m)})$ 也是模 $m$ 的一个简化剩余系。所以有 $$ \prod_{i=1}^{\varphi(m)} x_i\equiv \prod_{i=1}^{\varphi(m)} ax_i\pmod m $$ 那么由于 $\forall i,(x_i,m)=1$，所以 $(\prod x_i,m)=1$ 。于是消一下可以得到 $$ 1\equiv a^{\varphi(m)}\pmod m $$ 证毕。 # 结语 个人感觉剩余类这部分是很有趣的，虽然以上内容大部分都是4-6里面提炼出来的。对于欧拉定理，用群论知识证明同样十分简洁。 总之，完结啦，撒花花。 数论4-6，也算是我的一场持续了三年的春花旧梦了吧。 不知道啥时候能和EI和rqy一样有对数学知识的深刻认识。慢慢来吧。只有站在越高处，才能看到越广的风景，不是吗？