【学习笔记】从剩余类到欧拉定理

「重学4-6」系列的最后一篇文章。

感觉剩余类这部分内容,以纯数论的眼光去看待,是十分优美的。

嗯,将来自己抽代真正入门之后,可能就会多一点别的角度了吧。

剩余类相关定义

剩余类

定义 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 $ :

其中 $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\not =0,b\not = 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}$ 有

那么记这个集合为模 $m$ 的一个完全剩余系。

定义2.2

如果对于一个集合 $\rm S$ ,满足 $\mathrm{|S|}=m$ 且 $\forall i\not=j,i\in \mathrm{S},j\in \mathrm{S}$ 有

那么记这个集合为模 $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$,则有

那么由于 $(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_1,m_2)=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)$ 使得

考虑若 $(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$ 的一个简化剩余系。所以有

那么由于 $\forall i,(x_i,m)=1$,所以 $(\prod x_i,m)=1$ 。于是消一下可以得到

证毕。

结语

个人感觉剩余类这部分是很有趣的,虽然以上内容大部分都是4-6里面提炼出来的。对于欧拉定理,用群论知识证明同样十分简洁。

总之,完结啦,撒花花。

数论4-6,也算是我的一场持续了三年的春花旧梦了吧。

不知道啥时候能和EI和rqy一样有对数学知识的深刻认识。慢慢来吧。只有站在越高处,才能看到越广的风景,不是吗?