近世代数理论基础6：费马小定理·欧拉定理

2019-02-11 本文已影响52人溺于恐

费马小定理·欧拉定理

同余

定义： $m\in Z_+$ , $a,b\in Z$ ,若 $m|(a-b)$ ,则称a与b模m同余,记作 $a\equiv b(mod\;m)$ ,否则称a与b模m不同余,记作 $a\not\equiv b(mod\; m)$

利用同余,可在整数集合Z上诱导出一个关系 $R:R=\{(a,b)|a\equiv b(mod\; m),a,b\in Z\}$ ,称为模m同余关系

定理

定理： $m\in Z_+$ ,则模m同余关系是等价关系,即

(1) $\forall a\in Z$ ,有 $a\equiv a(mod\; m)$

(2) $a\equiv b(mod\; m)\Rightarrow b\equiv a(mod\; m)$

(3) $a\equiv b(mod\; m),b\equiv c(mod\; m)\Rightarrow a\equiv c(mod\; m)$

注：

1.模m同余关系的商集记作 $Z/mZ$

2.任一整数a所在的同余类记作 $[a]$ ,也称为同余类或剩余类

3.任一整数a用m除所得的余数只能为 $0,1,2,\cdots,m-1$ 中的一个, $Z/mZ=\{[0],[1],[2],\cdots,[m-1]\}$ 为模m的完全剩余类,其中 $[i]$ 为那些除m所得的余数为i的所有整数构成的集合

运算性质

定理： $m\in Z_+$ , $a,b,c,d,a_1,a_2,b_1,b_2\in Z$ ,则

1.若 $a_1\equiv b_1(mod\; m),a_2\equiv b_2(mod\;m)$ ,则

$a_1+a_2\equiv b_1+b_2(mod\; m)$

$a_1a_2\equiv b_1b_2(mod\; m)$

2. $a+b\equiv c(mod\; m)\Rightarrow a=c-b(mod\;m)$

3. $ad\equiv bd(mod\;m)且(d,m)=1\Rightarrow a\equiv b(mod\;m)$

4.若 $a\equiv b(mod\;m)$ ,d为a,b,m的任一公因数,则

${a\over d}\equiv {b\over d}(mod\;{m\over d})$

5.若 $a\equiv b(mod\; m_i),i=1,2,\cdots,t$ ,则

$a\equiv b(mod\;[m_1,m_2,\cdots,m_t])$

6. $a\equiv b(mod\;m)\Rightarrow \forall d\gt 0,d|m,有a\equiv b(mod\; d)$

7. $a\equiv b(mod\;m)\Rightarrow (a,m)=(b,m)$

证明：

3. $ad\equiv bd(mod\;m)且(d,m)=1\Rightarrow a\equiv b(mod\;m)$

$由ad\equiv bd(mod\;m)$

$m|(ad-bd)=d(a-b)$

$\because (m,d)=1$

$\therefore \exists s,t\in Z使ms+dt=1$

$两边乘(a-b)可得$

$ms(a-b)+dt(a-b)=a-b$

$\because m|ms,m|d(a-b)$

$\therefore m|(a-b)$

$即a\equiv b(mod\; m)\qquad\mathcal{Q.E.D}$

完全剩余系

定义： $m\in Z_+$ , $a_0,a_1,\cdots,a_{m-1}\in Z$ ,若其中任意两个数均不在模m的同一个剩余类中,则称 $\{a_0,a_1,\cdots,a_{m-1}\}$ 为模m的一个完全剩余系

缩系

若 $[i]$ 中有某个数与m互素,则 $[i]$ 中所有的数与m均互素,此时称 $[i]$ 为与模m互素的一个剩余类,因而有 $\varphi(m)$ 个与模m互素的剩余类,在与模m互素的每个剩余类中取一个数,得到 $\varphi(m)$ 个与模m互素的数,它们组成的集合称为模m的一个缩系

定理：若 $a_1,a_2,\cdots,a_{\varphi(m)}\in Z$ ,则 $\{a_1,a_2,\cdots,a_{\varphi(m)}\}$ 为模m的一个缩系 $\Leftrightarrow $$(a_i,m)=1$ 且 $\forall i,j=1,2,\cdots,\varphi(m)$ ,有 $a_i\not\equiv a_j(mod\; m)$

定理：若 $m,n\in N$ ,且 $(m,n)=1$ ,则当x与y分别跑遍模m的一个完全剩余系时, $nx+my$ 恰好跑遍模mn的一个完全剩余系

证明：

$当x和y分别跑遍模m和模n的一个完全剩余系时$

$nx+my恰好取mn个值$

$下证它们为模mn两两不同余$

$设nx_1+my_1=nx_2+my_2(mod\; m)$

$则nx_1\equiv nx_2(mod\; m),my_1\equiv my_2(mod\; n)$

$又(m,n)=1$

$x_1\equiv x_2(mod\; m)$

$y_1\equiv y_2(mod\; n)$

$\therefore x_1=x_2,y_1=y_2\qquad\mathcal{Q.E.D}$

定理：若 $m,n\in N$ 且 $(m,n)=1$ ,则当 $x,y$ 分别跑遍模m,n的一个缩系时, $nx+my$ 恰好跑遍模mn的一个缩系, $\varphi(mn)=\varphi(m)\varphi(n)$

证明：

$当x,y分别跑遍模m和模n的完全剩余系时$

$nx+my跑遍模mn的完全剩余系$

$若(x,m)=1,(m,n)=1$

$可证(nx,m)=1$

$同理,(y,n)=1,(m,n)=1$

$可证(my,n)=1$

$\therefore (nx+my,m)=1,(nx+my,n)=1$

$\therefore (nx+my,mn)=1$

$若(nx+my,mn)=1$

$则(nx+my,m)=(nx+my,n)=1$

$即(nx,m)=(my,n)=1$

$\therefore (x,m)=(y,n)=1$

$即当x,y分别跑遍模m,n的缩系时$

$nx+my恰好跑遍模mn的一个缩系\qquad\mathcal{Q.E.D}$

推论：设 $a=p_1^{k_1}p_2^{k_2}\cdots p_t^{k_t}$ ,则

$\varphi(a)=a(1-{1\over p_1})(1-{1\over p_2})\cdots(1-{1\over p_t})$

欧拉定理

定理：设 $m\in Z,m\gt 1$ , $(a,m)=1$ ,则 $a^{\varphi(m)}\equiv 1(mod\; m)$

证明：

$设a_1,a_2,\cdots,a_{\varphi(m)}是模m的一个缩系$

$易证aa_1,aa_2,\cdots,aa_{\varphi(m)}也为模m的一个缩系$

$两个缩系中的元可不同$

$但它们取模m后的余数却对应相等$

$\therefore (aa_1)(aa_2)\cdots(aa_{\varphi(m)})\equiv a_1a_2\cdots a_{\varphi(m)}(mod\; m)$

$即a^{\varphi(m)}(a_1a_2\cdots,a_{\varphi(m)})\equiv a_1a_2\cdots a_{\varphi(m)}(mod\; m)$

$对任意1\le i\le \varphi(m),有(a_i,m)=1$

$\therefore (a_1a_2\cdots a_{\varphi(m)},m)=1$

$\therefore a^{\varphi(m)}\equiv 1(mod m)\qquad\mathcal{Q.E.D}$

在实际应用中经常要计算 $a^k$ 模m的值,利用欧拉定理,先计算 $k=q\varphi(m)+k_0$ ,其中 $0\le k_0\lt \varphi(m)$ ,即 $k_0\equiv k(mod\; \varphi(m))$ ,即 $a^k\equiv a^{k_0}(mod\; m)$ ,从而简化运算