魔方吧·中文魔方俱乐部

标题: 求解一道求原根的问题~~ [打印本页]

作者: 77hsxian 时间: 2011-11-16 22:06:05 标题: 求解一道求原根的问题~~

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 时间: 2011-11-16 22:10:09

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

作者: 潜水艇 时间: 2011-11-16 22:57:47

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

作者: wpolly 时间: 2011-11-17 00:38:13

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 时间: 2011-11-17 07:33:34 标题: 回复 4# 的帖子

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

作者: yq_118 时间: 2011-11-17 09:42:29

ϕ(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 时间: 2011-11-17 13:01:12

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

作者: superacid 时间: 2011-11-21 16:05:15

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

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

作者: superacid 时间: 2011-11-21 16:07:38

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

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)