limjunyoung
级别: 荣誉会员 一等解题奖
发贴: 893
威望: 616
金币: 1943
注册时间:2006-04-26
最后登陆:2008-11-24
|
|
无聊..发点数论的东西给大家吧-.-
Wilson's Theorem
p为质数的充要条件是, (p-1)!=-1(mod p)
证明: 充分性:如果p是合数,那么p必然可以分解成至少2个比它小的数,所以(p-1)!必然能被p整除,因此p不能为合数,所以p只能为质数
必要性:1=1 (mod p) p-1=-1(mod p) 而2到p-2这些数都与p互质,所以根据Euclid extended algorithm,必然能将2到p-2这些数分为(p-3)/2组两两相对的数(设为a,b) 使得ab=1(mod p)
因此当p是质数时 (p-1)!=-1(mod p)
简单介绍一下Euclid extended algorithm.
由欧式算法求2个数的最大公约数的方法是
假设整数a>b>=1 那么(a+1)b>ab>=a
设p是最大的整数,使得a=qb+r, r是正整数.
比如a=7,b=2 那么q=3 r=1
再设b=Qr+r2 同样Q是最大的整数使得r2为正整数时式子成立
如此不断反复,最终使等式左边的数能够被完全分解
例如a=893, b=705
算法为 893=1*705+188
705=3*188+141
188=1*141+47
141=3*47+0
所以893和705的最大公约数为47
以此为例,这个算法的原理是47能被141整除,所以188就能被47整除,以此类推得到893和705能被47整除
设最大公约数为c. 首先c能整除893和705.它必然能整除188.(否则1式不成立)
以此类推,c必然整除47
从2方面同时来看.因此这个算法给出的是最大公约数,而不仅仅是公约数
Euclid extended algorithm 就是建立在此基础上
设a,b最大公约数为c,那么必然存在整数x,y 使得ax+by=c
同样我们以893和705为例 这里c=47
47=188-1*147=188-(705-3*188)=4*188-705=4*(893-705)-705=4*893-5*705
所以这里x=4 y=-5
其实计算x,y的方法就是逆推,而前面给出的证明由于p和2到p-2的数都互质,所以c=1
所以令b=p 就可以推出前面的证明
|
寻论网 -> 寻论社区-(中学生-大学生顶级论坛) -> 中学数学 非常解答 -> 高中数学 非常解答 -> 无聊..发点数论的东西给大家吧-.-
