求解一道求原根的问题~~

77hsxian

RT求50的原根
我算成了这样....50-1=49他的因子有1,7,49
2^7≡28(mod50) 2^49≡12(mod50)
3^7≡37(mod50) 3^7≡33(mod50)
5^7≡25(mod50) 5^7≡25(mod50)
7^7≡43(mod50) 7^7≡43(mod50)
发现到7都没找到原根怎么办~?还要继续往上找么?

77hsxian

顺便想问问怎么判断一个数有没有原根啊?

潜水艇

原根？！表示环境工程专业的本科生果断不懂~~~~

wpolly

n有原根当且仅当n=2 4 p^a 2p^a (p为奇素数)

50可以这么求：

已知2是5的原根
算出2^4=16(mod 25),2^10=24(mod 25)得到2也是25的原根
所以2+25=27就是50的原根

77hsxian

为啥2是5的原根,2是25的原根就说明2+25就是50的原根啊?

yq_118

ϕ(50) = 20

3^1≡3(mod 50)
3^2≡9(mod 50)
3^4≡31(mod 50)
3^5≡43(mod 50)
3^10≡49(mod 50)
3^20≡1(mod 50)

所以3是50的原根。

77hsxian

phi(50)不是只有1 3 5 7 11 13 17 19 23 27 29 31 37 41 43 47 16个么= =

superacid

楼主对原根的理解有问题。。

如果(a,n)=1，且如果使得a^d mod n = 1成立的最小的正整数d=phi(n)
那么a是n的原根

superacid

另外，如果n有原根，那么n的原根个数为phi(phi(n))