加载中…
个人资料
xiaxia
xiaxia
  • 博客等级:
  • 博客积分:0
  • 博客访问:95,463
  • 关注人气:40
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
博文
标签:

教育

分类: 程序人生

证明:如果p是一个奇素数,g是p^2的一个原根,那么g是p^k的一个原根,k是任意自然数
什么是原根?参见
http://mathworld.wolfram.com/PrimitiveRoot.html
http://en.wikipedia.org/wiki/Primitive_root_modulo_n
简单的说如果对g来说满足g^j mod p = 1最小的自然数j=φ(p),那么g是就是p的一个原根。φ(p)是p的欧拉函数。
首先证明g是p(k=1)的一个原根。由费马小定理参见http://blog.sina.com.cn/s/blog_48e3f9cd010002uc.html
知g^(p-1) mod p = 1,  p是素数φ(p) = p - 1, 如果存在自然数j使得g^j mod p = 1, j < p - 1。
那么令g^j =  1 + a*p, a是整数, g^(pj) = (1+a*p)^p = 1 + a*p^2 + C(p,2)*a^2*p^2 + ....
显然有g^(pj) mod p^2 = 1, pj < p*(p-1) = φ(p^2) 这和g是p^2的一个原根矛盾。所以p-1是最小满足
g^j mod p = 1的自然数,g是p的一个原根。

一个有用的性质:假

(2005-06-12 14:15)
分类: 未归类的
昨天终于考完了哈哈。解放了哈哈!一上去把名字全涂了,因为给了很多空格哦15个阿,结果发现只要涂姓。接着邮箱写成电子邮箱了,前面有个人问Postcode 我一想哪有这个哦?ft!然后发现答题卡的后面还要涂发现找不到serial number,前面mm说在试题正面。然后发现要写誓词 ,随便填了突然看见下面有个signature 就填了后来发现是cancel 成绩的晕死。ETS 答题卡就把我考晕了,比数学难多了。数学倒很简单除了有的题目不好不懂,题目都弱智到小学水平。至于verbal在意料之中,惨不忍睹跨区都做不完,阅读好多都选了C,类反好多都是不认识的单词。总之彻底被纪阿姨的无敌魅力征服。
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有