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

作者: 溺于恐 | 来源:发表于2019-02-11 07:36 被阅读52次

数论四大定理
近世代数理论基础6：费马小定理·欧拉定理
2020-01-22（学习笔记附录）
欧拉定理
费马小定理与欧拉定理
同余方程(组)
逆向-RSA加密
资格赛 A题
费马大定理（二）：接力：前赴后继的358年
《费马大定理》有感

费马小定理·欧拉定理

同余

定义： $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)$ ,从而简化运算

费马小定理

推论：若p为素数, $\forall a\in Z$ ,则 $a^p\equiv a(mod\; p)$

证明：

$\forall a\in Z$

$\because p为素数$

$\therefore (a,p)=1或(a,p)=p$

$若(a,p)=1$

$由欧拉定理$

$a^{\varphi(p)}=a^{p-1}\equiv 1(mod\; p)$

$\therefore a^p\equiv a(mod\; p)$

$若(a,p)=p$

$则p|a$

$\therefore a^p\equiv a\equiv 0(mod\; p)\qquad\mathcal{Q.E.D}$

数论四大定理
威尔逊定理、欧拉定理、孙子定理、费马小定理
近世代数理论基础6：费马小定理·欧拉定理
费马小定理·欧拉定理同余定义：,,若,则称a与b模m同余,记作,否则称a与b模m不同余,记作利用同余,可在整...
2020-01-22（学习笔记附录）
数论概论同余式、幂与费马小定理费马小定理：p为质数，a除以p不为0，则a^(p-1) 除以p余1 欧拉公式：若...
欧拉定理
欧拉函数欧拉函数是小于等于的正整数中与互质的数的个数。欧拉定理对于任意互素的和，有参考链接费马小定理...
费马小定理与欧拉定理
定义若整数a和整数b，除以正整数m得到的余数相等，称为a，b模m同余，记作。费马小定理若p为质数，a是任意整数并且...
同余方程(组)
第二章同余欧拉-费马定理定理1 （i）欧拉函数是积性的，即如果，则有（ii）设是的标准分解，...
逆向-RSA加密
RSA （三个人的名字）非对称加密！（现代加密算法）原根欧拉函数、欧拉定理（费马小定）模反元素m ^（e * d）...
资格赛 A题
画图说话：分析：9937 为质数，费马小定理+逆元，除法变乘法，快速幂取余费马小定理公式推导：(b/a)mo...
费马大定理（二）：接力：前赴后继的358年
欧拉：直到18世纪，1753年，距离费马大定理的出现已经过去了100多年，数学巨人欧拉对此也产生了浓厚的兴趣。 ...
《费马大定理》有感
总起: 《费马大定理》是一本由辛格写的关于证明费马大定理的历史的书。从费马大定理的起源，数学界对它的探索，到最终...

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

费马小定理·欧拉定理

同余

定理

运算性质

完全剩余系

缩系

欧拉定理

费马小定理

相关文章

数论四大定理

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

2020-01-22（学习笔记附录）

欧拉定理

费马小定理与欧拉定理

同余方程(组)

逆向-RSA加密

资格赛 A题

费马大定理（二）：接力：前赴后继的358年

《费马大定理》有感

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

近世代数