关于原根的一些疑问
  • 板块学术版
  • 楼主PCCP
  • 当前回复11
  • 已保存回复11
  • 发布时间2023/7/14 16:00
  • 上次更新2023/11/3 09:53:09
查看原帖
关于原根的一些疑问
310773
PCCP楼主2023/7/14 16:00

1.oiwiki里说:

王元于 1959 年证明了若 m 有原根,其最小原根是不多于 m0.25m^{0.25} 级别的。

但是18的最小原根是5,所以最小原根的范围究竟是多少?

2.在P6091,ix35大佬的题解里有:

怎么求一个数 nn 的所有原根?首先找到 nn 的最小原根,设为 g。具体地,若 n 存在原根,则其原根个数为 φ(φ(n)) \varphi(\varphi(n)),每一个原根都形如 gk g^k 的形式,要求满足 gcd⁡(k,φ(n))=1\gcd(k,\varphi(n))=1。

还是以18为例,18还有一个原根是11,可是11并不是5的整数次方,所以这个究竟是对还是错呢?

求助各位大佬解答蒟蒻的疑惑。

2023/7/14 16:00
加载中...