为什么素数p有原根？是不是只有对大于一的正整数m，m
编辑： admin 2017-23-02
-
4
是的,只有这些数有原根.素数原根的存在性是最不容易证明的.这些符号不好打,我就说一种证法.
你应该懂费马小定理吧,就是说a^(p-1)=1(mod p),所以某数a一定有一个幂模p后和1同余,这个幂指数一定是p-1的因子,最小的叫做指标.
先把p-1分解,设p-1=(a^m)*(b^n)*...
我们可以找到一个数A,它的指标是a^m.方法是设k是1,2,...,p-1里的一个数,满足k^((p-1)/a)不与1同余(都是模p,我以后不说了),那么A同余于k的((p-1)/a^m)次幂.
同样可以找到一个数B,它的指标是b^n,等等.则A*B*...就是p的一个原根
类似问题
类似问题1：对一个奇素数P,一定有原根,可以根据定义判定某个数是不是它的原根,但我想知道如何直接根据P计算它的最小元根的算法!1楼答案的哥哥，用你的搜索法确实可以判断某数是不是原根，这个我
原根Primitive Root
g^i mod p ≠ g^j mod p
其中i≠j且i,j介於1至(p-1)之间
则g为p的原根.
i,j用for循环就可以了.
编程
类似问题2：设p是一个素数.证明,p次原根有p-1个,即p次单位根中除1外都是p次原根[数学科目]
如果n是一个正整数,a^(n-1) MOD n = 1,则我们说n是一个满足基于a的伪素数.
即对于1..n-1间的任意一个整数a来说,a^(n-1) MOD n 1,则n一定是合数,若a^(n-1) MOD n = 1,则几乎可以肯定地确认n是素数,因为它出错的机会非常少.
类似问题3：求以10为原根的最小素数[数学科目]
是7.这个可以查查原根表,初等数论的书里都有,比如：华罗庚的《数论导引》第三章里有5000以内所有素数的最小原根,其中标星号的是10为原根.当然实际计算也十分简单.
类似问题4：如果p是素数,a是整数,那么p!|(a^p+(p-1)!a)[数学科目]
p!| (a^p+(p-1)!a)一般是不能成立的,有反例如p = 5,a = 2.
p | (a^p+(p-1)!a)是成立的.
由Fermat小定理,p | a^p-a.
又由Wilson定理,p | (p-1)!+1,故p | (p-1)!a+a.
相加即得p | a^p+(p-1)!a.
类似问题5：求大素数p的一个原根（素数要很大很大）
看到您的问题很久没有人回答,但是问题过期无人回答会被扣分并且你的悬赏分也会被没收!所以我给你提几条建议：1,提问要尽量完整清晰不要有生僻的字,回答者一点都不知道你的情况如果你的问题也不清楚的话回答者就不知道你说的是什么,就谈不上回答你的问题了.2,提问时不要一次性提很多相同的问题,提相同的问提让人看着很有压力很烦恼,甚至会认为你作弊的.所以一个问题提一次请出简明即可.3,提问者应该尊重回答者,别人不是你的奴隶必须为你解决问题,所以提问时请注意文明用语!尊重他人的劳动.4,不要问一些太简单的问题,不要明知故问,这是浪费回答者宝贵的时间啊!且不要问一些涉嫌违规的问题.5,不要涉及尖端科学 ,问问里只是一些普通的人,如果你提得问题连科学家都没有答案,很难在这里问出答案来 6,可以多交一些知识渊博的网友,以前的一些较难的题,如果有人回答对了,可以和回答者成为好朋友,经常保留着联系,有问题了可以互相探讨的!您可以不采纳我的答案,但请您一定要考虑下我的建议哦!