主题
Search

原根

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

素数 p 的原根是一个 整数 g，使得 g (mod p) 的 乘法阶 为 p-1 (Ribenboim 1996, p. 22)。更一般地，如果 GCD(g,n)=1 ( g 和 n 是 互素 的) 且 g 的 乘法阶 为 phi(n) 模 n，其中 phi(n) 是 欧拉函数，那么 g 是 n 的原根 (Burton 1989, p. 187)。第一个定义是第二个定义的特例，因为对于素数 p，phi(p)=p-1。

数字 n 的一个原根 (但不一定是合数 n 的最小原根) 可以在 Wolfram 语言 中使用以下命令计算：PrimitiveRoot[n]。

如果 n 有原根，那么它恰好有 phi(phi(n)) 个 (Burton 1989, p. 188)，这意味着如果 p 是一个 素数，那么 p 恰好有 phi(p-1) 个模 p 不同余的原根 (Burton 1989)。对于 n=1, 2, ...，phi(phi(n)) 的前几个值是 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 4, 2, 4, 2, 4, 4, 8, ... (OEIS A010554)。如果 n 是 以下形式 之一：2, 4, p^a, 或 2p^a，其中 p 是一个 奇素数 且 a>=1 (Burton 1989, p. 204)，那么 n 有原根。存在原根的 n 的前几个值是 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, ... (OEIS A033948)，因此，阶为 n 的原根的数量，对于 n=1, 2, ... 是 0, 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, ... (OEIS A046144)。

前几个素数 p 的最小原根是 1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, ... (OEIS A001918)。以下是前几个存在原根的 n 的原根表 (OEIS A046147)。

ng(n)
21
32
43
52, 3
65
73, 5
92, 5
103, 7
112, 6, 7, 8
132, 6, 7, 11

n=1, 2, ... 的最大原根是 0, 1, 2, 3, 3, 5, 5, 0, 5, 7, 8, 0, 11, ... (OEIS A046146)。下表 (OEIS A046145) 给出了前几个 整数 n 的最小原根，省略了当 n 的原根 g(n) 不存在时的情况。

213839451583
324169751625
434339831632
5246510121665
6547510351675
7349310631692
9250310721732
10353210961783
11254511331792
132583118111812
143592121219119
17361212271935
18562312521945
19267212731972
22771713121993
23573513472023
25274513732065
26779313922112
27281214272145
292827146521811
31383214922233
34386315162263
37289315752272

设 p 为任意 奇素数 k>=1，并设

s=sum_(j=1)^(p-1)j^k.
(1)

那么

s={-1 (mod p) for p-1|k; 0 (mod p) for p-1k
(2)

(Ribenboim 1996, pp. 22-23)。对于有原根的数字 m，所有满足 (m,y)=1 的 y 都可以表示为

y=g^t (mod m),
(3)

其中 t=0, 1, ..., phi(m)-1，t 称为指标，y 是一个 整数。Kearnes (1984) 证明，对于任何 正整数 m，都存在无限多个 素数 p 使得

m<g_p<p-m.
(4)

将最小原根称为 g_p。Burgess (1962) 证明了

g_p<=Cp^(1/4+epsilon)
(5)

对于 C 和 epsilon 正 常数且 p 足够大时成立 (Ribenboim 1996, p. 24)。

Matthews (1976) 获得了“二维”阿廷常数的公式，用于 m 和 n 都是原根的素数集合。

另请参阅

阿廷猜想, 阿廷常数, 全循环素数, 乘法阶, 本原元, 单位根

使用 Wolfram|Alpha 探索

参考文献

Abramowitz, M. 和 Stegun, I. A. (编). "Primitive Roots." §24.3.4 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 827, 1972.Burgess, D. A. "On Character Sums and L-Series." Proc. London Math. Soc. 12, 193-206, 1962.Burton, D. M. "The Order of an Integer Modulo n," "Primitive Roots for Primes," and "Composite Numbers Having Primitive Roots." §8.1-8.3 in Elementary Number Theory, 4th ed. Dubuque, IA: William C. Brown Publishers, pp. 184-205, 1989.Guy, R. K. "Primitive Roots." §F9 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 248-249, 1994.Jones, G. A. 和 Jones, J. M. "Primitive Roots." §6.2 in Elementary Number Theory. Berlin: Springer-Verlag, pp. 99-103, 1998.Kearnes, K. "Solution of Problem 6420." Amer. Math. Monthly 91, 521, 1984.Lehmer, D. H. "A Note on Primitive Roots." Scripta Math. 26, 117-119, 1961.Matthews, K. R. "A Generalization of Artin's Conjecture for Primitive Roots." Acta Arith. 29, 113-146, 1976.Nagell, T. "Moduli Having Primitive Roots." §32 in Introduction to Number Theory. New York: Wiley, pp. 107-111, 1951.Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, pp. 22-25, 1996.Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, p. 97, 1994.Sloane, N. J. A. Sequences A001918/M0242, A010554, and A033948 in "The On-Line Encyclopedia of Integer Sequences."Western, A. E. 和 Miller, J. C. P. Tables of Indices and Primitive Roots. Cambridge, England: Cambridge University Press, pp. xxxvii-xlii, 1968.

在 Wolfram|Alpha 中被引用

原根

请按如下方式引用

Weisstein, Eric W. "原根。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/PrimitiveRoot.html

主题分类