原根的计算

公子相 · 发表于 2023-11-5 02:53:37

PARI如何高效地计算一个已知素数的全部原根的积？

uahexuk · 发表于 2023-11-5 02:53:44

ulenkusefihj · 发表于 2023-11-5 02:53:52

很简单，除了p=3以外，其它全部为1

油条大哥大 · 发表于 2023-11-5 02:54:11

为什么？

Marleslots · 发表于 2023-11-5 02:54:41

如果g是p的原根，那么$g^{-1}$也是原根，所以除非存在原根g使得$g=g^{-1}$,不然所有原根乘积为1.
而$g=g^{-1}$等价于原根g满足$g^2=1$,显然只能p=3

eheotolee · 发表于 2023-11-5 02:55:09

应该只能穷举，素数和源根之间好像没有关系式吧

		自动登录	找回密码
密码			立即注册