费马小定理的证明过程

费马小定理的证明过程

关于费马小定理数论的证明：
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) 表示比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如果Emn>mn 我们可以通过减去k倍的mn(不影响其性质),同样得到比mn小和mn互质的整数
并且如果Am, Bn变换时Emn也会变换 而Am,Bn总共变化可以有o(m)*o(n)种
所以o(mn)=o(m)o(n)

时代大厦的

我来拯救你吧。
我弄2个证明方法给你看看。
第一种
设一个比质数p小的正整数a，让a依次乘以1 2 3 ...到p-1,得到a,2a,3a...(p-1)a，而由于a与p互质，每次乘积所得到的余数都不一样，设如果ab与ac同余p（a,b,c均小于p），必定b=c，故若b不等于c，ac与ab不同余,则a到(p-1)a的余数恰好有p-1种，与1到p-1完全能一一对应，于是（p-1的阶乘）同余（a的p-1次方乘以p-1的阶乘），约去p-1的阶乘，就有了a的p-1次方除以p余1。
第二种（这种方法其实我自己没法做的，是照书打的，比较巧妙）
构造二项式（a+1)^p,因为展开这个二项式，每项都是C(r)(p)（组合数，下标p,上标r)*a^r,只有r等于0或者p的那一项才不被p整除，故（a+1)^p与a^p+1同余p，先归纳假设a^p次方除以p余a（这里别把它看成真理），则p整除a^a-a=a(a^(p-1)-1)，而a与p互质，a整除a^(p-1)-1,由反向的数学归纳法证明出来。