费马小定理数论的证明方法 费马小定理数论的证明方法 2007年12月28日 星期五 01:29 P.M. 费马小定理数论的证明方法 Mod的简单介绍 (Congruence) a=b(mod m) a和b除以m以后有相同的余数 不失一般性地另a>b 则a=km+b比如7=1 mod 2 9=4 mod 5 简单的Congruence 计算 如果a=b mod m c=d mod m 则a=km+b c=tm+d 直接可推出 a+b=c+d (mod m) a-b=c-d (mod m) ab=cd (mod m) 并且可得存在正整数c 使得ac=bc (mod mc) 当然ac=bc(mod m) 费马小定理 如果a,p互质 且q是质数 则a^(p-1)=1 (mod p) 考虑数列An= a,2a,3a,4a…… (p-1)a 假设An中有2项ma, na 被p除以后的余数是相同的.那么必然有ma=na (mod p) 即a(m-n)=0(mod p) 由于a和p互质,所以m-n=0(mod p) 但是m,n属于集合{1,2,3..p-1} 且m不等于n,所以m-n不可能是p的倍数.和假设产生矛盾 所以An中任意2项被p除 得到的余数都是不同的, 并且对于任一个整数被p除以后的余数最多有p-1个,分别是 1,2,3,….p-1 而数列An中恰好有p-1个数,所以数列中的数被p除以后的余数一定正好包含 所有的1,2,3,4,5…. p-1 由此我们可以用Congruence的乘法性质, a*2a*3a*…(p-1)a=1*2*3*4..*(p-1) (mod p) 对两边进行化简,即可以得到a^(p-1)=1 (mod p) Euler’s Totient function 定义o(n)是所有比n小且和n互质的数的总数(包括1) 例如o(5)=4 o(10)=8 我们发现引入这个以后费马小定理可以改写为a^o(p)=1 (mod p) 事实上,这个结论对所有的正整数n都成立 即a^o(n)=1 (mod n) 证明过程其实和前面的证明类同.只需考虑数列An=b1*a,b2*a,b3*a…bo(n)*a 其中数列b1,b2…bo(n)
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示比n小且和n互质的数.其余证明皆相似 掌握了a^o(n)=1 (mod n)以后,最后一个问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
就是如何计算o(n) 显然n是质数时 o(n)=n-1 n=p^k, p为质数,k为非负整数时 o(n)=p^k-p^(k-1) 因为只有p,2p,3p..p^(k-1)p这些和p^k有共因数.这里面共有p^(k-1)个数 所以o(p^k)=p^k-p^(k-1) 最后证明o(mn)=o(m)*o(n)当m,n互质时 考虑数列Am A1,A2,A3…Ao(m) 数列Bn B1,B2,B3…Bo(n) 因为m,n互质所以我们总能找到c,d使得cm=1 (mod n) dn=1 (mod m) 考虑Emn=Am*dn+Bn*cm 这里 显然cm能被m 整除, 所以Emn=Am*dn(mod m)=Am (mod m) 所以Emn和m互质 同样可以证明Emn和n互质 所以Emn和mn也互质 而对于Emn
mn 我们可以通过减去k倍的mn(不影响其性质),同样得到比mn小和mn互质的整数 并且如果Am, Bn变换时Emn也会变换 而Am,Bn总共变化可以有o(m)*o(n)种 所以o(mn)=o(m)o(n)
浙公网安备 33021202002483