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

费马小定理·欧拉定理

同余

定义： $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}$

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 214,922评论 6赞 497
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,591评论 3赞 389
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 160,546评论 0赞 350
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,467评论 1赞 288
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,553评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,580评论 1赞 293
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,588评论 3赞 414
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,334评论 0赞 270
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,780评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,092评论 2赞 330
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,270评论 1赞 344
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,925评论 5赞 338
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,573评论 3赞 322
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,194评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,437评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,154评论 2赞 366
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,127评论 2赞 352