原根及原根猜想

yangchuanju

原根  360百科（摘要）

基本信息
中文名称  原根
外文名称  Primitive Root
应用学科  数学
适用领域范围  数论

目录       
1定义
2原根的性质
3原根的例子

定义
设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。(其中φ(m)表示m的欧拉函数)
假设一个数g对于P来说是原根，那么g^i mod P的结果两两不同,且有 1<g<P, 0<i<P,那么g可以称为是P的一个原根,归根到底就是g^(P-1) = 1 (mod P)当且仅当指数为P-1的时候成立.(这里P是素数).
简单来说，g^i mod p ≠ g^j mod p (p为素数)
其中i≠j且i, j介於1至(p-1)之间
则g为p的原根。
求原根目前的做法只能是从2开始枚举，然后暴力判断g^(P-1) = 1 (mod P)是否当且当指数为P-1的时候成立
而由于原根一般都不大，所以可以暴力得到.

原根的性质
1)可以证明，如果正整数(a,m) = 1和正整数 d 满足a^d≡1(mod m)，则 d 整除 φ(m)。因此Ordm(a)整除φ(m)。在例子中，当a= 3时，我们仅需要验证 3 的 1 、2、3 和 6 次方模 7 的余数即可。
2)记δ = Ordm(a)，则a^1，……a^(δ-1)模 m 两两不同余。因此当a是模m的原根时，a^0,a^1，……a^(δ-1)构成模 m 的简化剩余系。
3)模m有原根的充要条件是m= 1,2,4,p,2p,p^n，其中p是奇质数，n是任意正整数。
4)对正整数(a,m) = 1，如果 a 是模 m 的原根，那么 a 是整数模n乘法群(即加法群 Z/mZ的可逆元，也就是所有与 m 互素的正整数构成的等价类构成的乘法群)Zn的一个生成元。由于Zn有 φ(m)个元素，而它的生成元的个数就是它的可逆元个数，即 φ(φ(m))个，因此当模m有原根时，它有φ(φ(m))个原根。

原根的例子
设m= 7，则φ(7)等于6。
设a= 2，由于2^3=8≡1(mod 7)，2^6=64≡1(mod7)，而2!=3，2^3≡2^6(mod7)，所以 2 不是模 7 的一个原根。设a= 3，由于3^1≡3(mod 7)，3^2≡2(mod 7)，3^3≡6(mod 7)，3^4≡4(mod 7)，3^5≡5(mod 7)，3^6≡1(mod 7)，所以 3 是模 7 的一个原根。
补充一点，根据原根的性质1，只需要验证3^1，3^2，3^3，3^6即可，这样可以简化运算。

yangchuanju

素数原根表
因为在模意义下需要各种素数。
如果r*2^k+1是个素数，那么在mod r*2^k+1意义下，可以处理 2^k以内规模的数据。
记录一下 a*2^k+1型素数的原根 g。

a*2^k+1        a        k        g
3        1        1        2
5        1        2        2
17        1        4        3
97        3        5        5
193        3        6        5
257        1        8        3
7681        15        9        17
12289        3        12        11
40961        5        13        3
65537        1        16        3
786433        3        18        10
5767169        11        19        3
7340033        7        20        3
23068673        11        21        3
104857601        25        22        3
167772161        5        25        3
469762049        7        26        3
998244353(常见)        119        23        3
1004535809        479        21        3
1998585857        953        21        3
2013265921        15        27        31
2281701377        17        27        3
3221225473        3        30        5
75161927681        35        31        3
77309411329        9        33        7
206158430209        3        36        22
2061584302081        15        37        7
2748779069441        5        39        3
6597069766657        3        41        5
39582418599937        9        42        5
79164837199873        9        43        5
263882790666241        15        44        7
1231453023109121        35        45        3
1337006139375617        19        46        3
3799912185593857        27        47        5
4222124650659841        15        48        19
7881299347898369        7        50        6
31525197391593473        7        52        3
180143985094819841        5        55        6
1945555039024054273        27        56        5
4179340454199820289        29        57        3
https://www.cnblogs.com/LzyRapx/p/9109496.html

yangchuanju

百度贴吧  世界数论难题吧
最小原根猜想
https://tieba.baidu.com/p/2871190782

临时发言人2012
任意大于1的自然数n，只要n不是平方数，不是立方数，不是所有k次方数，
那么存在素数p，p的最小原根就是n.

百度百科说原根一般都不大，我的这个猜想是说，最小原根都可以很大，要多大有多大！

目前我见过的是：素数89637484042681，它的最小原根是335.

类似的有个阿廷猜想，是这样的：
对于任意不等于1、p-1及完全平方的正整数α，必定存在无穷多个素数p，以α为原根。
【来源：http://baike.soso.com/v6723499.htm】
我猜的略有不同，我猜的是存在无穷多个素数p，以α为最小原根，即这些素数都没有比α更小的原根了。

当n稍微大一点时，对应的p会相当大。
看上去证明的难度也极大。

六月神junegod
我相信你的猜想是正确的.我还认为证明虽然不容易给出,但不会很深奥.
在4000以下的素数中,17之内不是k次方数的n除了12之外都是原根.我估计10000以下的素数应该有以12为原根的.如果把10000以下的素数都查过没有发现以12为原根,则你的猜想的第一问就可能不对.


已发现12是17的原根,只不过不是最小原根.但我已确信12必定是某个稍大一点的素数的最小原根,只是我没有这方面的资料而已.

天量阳光
把9-11楼（并删除）合并一下：

在奇素数p的剩余系中，p整除n^(p-1)-1，n称为p的素剩余（n与p互素），他们是(1,2,3…n-1)mod (p).
我们可以把奇素数的素剩余可以分成很多类型,如原根.非原根
其实,立方数、奇次方数也可以做原根的,如8,当然了,8是原根时,必然有更小的原根2.

在这里,我们把素剩余分成2类:
(1)当n符合p整除n^[(p-1)/2]-1时,我们称之为范根(类似高斯范数的根)
(2)当n不符合p整除n^[(p-1)/2]-1时,我们称之为孤根

如p=7时,
n=1,2,4，8,9,11，15,16,18，22,23,25，29,30,32，36,37,39等都是范根,
n=3,5,6，10,12,13，17,19,20，24,26,27，31,33,34，38,40,41等都是孤根,
可以证明：两个范根之积是范根，两个孤根之积也是范根；而孤根与范根之积是孤根。

所有平方数都属于范根，所有原根都属于孤根。

现在，我们取出1个数，如6，我们知道6=2*3，假如6是最小原根且是孤根，那么2,3之一是范根，另一个是孤根且又不是原根，那么p-1必定是4的倍数且p-1必包含2以外的因子，
那么，我们得到一个结论，以2质数积为最小原根的p应符合三者条件之一：
（1）p-1是4的倍数且至少有一个奇素数因子
（2）p-1至少有2个不同的奇素数因子
（3）p-1至少有一个奇素数的立方因子

yangchuanju

素数原根的两个猜想（摘要）
周娟  周尚超
《华东交通大学学报》20098年12月26-6卷

猜想1：若p和q=4p+1都是素数，则q的最小原根为2。
猜想2：若p和q=2p+1都是素数，当p=1(mod 4)时，2是q的最小原根，而当p=3(mod 4)时，2不是q的最小原根。

yangchuanju

A023048-107
有最小正原根n的最小素数
n  素数
1 2
2 3
3 7
4 0
5 23
6 41
7 71
8 0
9 0
10 313
11 643
12 4111
13 457
14 1031
15 439
16 0
17 311
18 53173
19 191
20 107227
21 409
22 3361
23 2161
24 533821
25 0
26 12391
27 0
28 133321
29 15791
30 124153
31 5881
32 0
33 268969
34 48889
35 64609
36 0
37 36721
38 55441
39 166031
40 1373989
41 156601
42 2494381
43 95471
44 71761
45 95525767
46 273001
47 275641
48 823766851
49 0
50 23126821
51 322999
52 129361
53 161831
54 4348468741
55 459841
56 219605251
57 471769
58 336361
59 712321
60 697591
61 1171921
62 658681
63 102896401
64 0
65 11089681
66 27955201
67 3384481
68 3733801
69 110881
70 5620201
71 3659401
72 226547941621
73 760321
74 8954401
75 194515471
76 25291561
77 8359009
78 102009601
79 7510801
80 596653488817
81 0
82 24818641
83 16889161
84 16271999719
85 23821561
86 7415641
87 41299801
88 264935161
89 6366361
90 341058118633
91 70716649
92 110591881
93 65150401
94 5109721
95 29128969
96 5260410488191
97 17551561
98 179199874981
99 2648833321
100 0
101 29418841
102 644416081
103 49443241
104 338764801
105 578689201
106 152076289
107 33358081

yangchuanju

A002229-38        A002230-38
只增不减的正原根        对应最小素数
1 1        1 2
2 2        2 3
3 3        3 7
4 5        4 23——有最小原根5
5 6        5 41——6
6 7        6 71——7
7 19        7 191——19
8 21        8 409——21
9 23        9 2161——23
10 31        10 5881——31
11 37        11 36721——37
12 38        12 55441——38
13 44        13 71761——44
14 69        14 110881
15 73        15 760321
16 94        16 5109721
17 97        17 17551561
18 101        18 29418841
19 107        19 33358081
20 111        20 45024841
21 113        21 90441961
22 127        22 184254841
23 137        23 324013369
24 151        24 831143041
25 164        25 1685283601
26 179        26 6064561441
27 194        27 7111268641
28 197        28 9470788801
29 227        29 28725635761
30 229        30 108709927561
31 263        31 386681163961
32 281        32 1990614824641
33 293        33 44384069747161
34 335        34 89637484042681
35 347        35 358973066123281
36 359        36 2069304073407481
37 401        37 4986561061454281
38 417        38 6525032504501281

yangchuanju

A002231-25        A029932-25
只增不减的素数原根        对应最小素数
1 2        1 3
2 3        2 7
3 5        3 23
4 7        4 41
5 11        5 109
6 19        6 191
7 43        7 271
8 53        8 2791
9 79        9 11971
10 107        10 31771
11 149        11 190321
12 151        12 2080597
13 163        13 3545281
14 211        14 4022911
15 223        15 73189117
16 263        16 137568061
17 277        17 443571241
18 307        18 565822531
19 347        19 1160260711
20 349        20 1622723341
21 367        21 31552100581
22 383        22 81651092041
23 461        23 96736641541
24 479        24 1867622877121
25 503        25 5000346134911

yangchuanju

周娟  周尚超给出有最小原根2的两个猜想，见4楼贴；
蔡家雄给出多个有原根10的猜想：

（一）素数倒数最大循环节长定理
设 k 为非负整数，
若 30k+7 和 120k+29 都是素数，
则 1/(120k+29) 具有最大循环节长d= 120k+28.

（二）蔡氏完全循环节问题
由 10 是 17，257，65537 的原根，
设 m= 16,  256,  65536,
设 k 为正整数，
若 30k+1 和 m*(30k+1)+1 都是素数，
则 1/(m*(30k+1)+1) 具有最大循环节长d= m*(30k+1).

设 k 为非负整数，
若 30k+7 和 m*(30k+7)+1 都是素数，
则 1/(m*(30k+7)+1) 具有最大循环节长d= m*(30k+7).

（三）蔡氏完全循环节问题
设 n>=3,
设 P 和 2^n*P+1 都是素数，
且 10^(2^n) -1 不能被 2^n*p+1 整除，
若 2^n*P+1 ≡ 17或33（mod  40），
则 10 是 2^n*P+1 的原根，
则 1/(2^n*p+1) 具有最大循环节长d= 2^n*p .

（四）梅森素数与蔡氏完全循环节问题
设 素数 p >=7，
且 (2^p -1)=30k+1 或 (2^p -1) =30k+7 也是素数，
若 (2^p -1)*16^m+1=(2^p -1)*2^(4m)+1 是素数，
则 10 是素数 (2^p -1)*16^m+1 的原根，
则 1/((2^p -1)*16^m+1) 具有最大循环节长d= (2^p -1)*16^m .

（五）生成完全循环节问题
若 3^(2n)+2^(2n+1) 是素数，
则 10 是素数 3^(2n)+2^(2n+1) 的原根。
10 是素数 3^2+2^3=17 的原根，
10 是素数 3^4+2^5=113 的原根，
10 是素数 3^6+2^7=857 的原根，
10 是素数 3^12+2^13=539633 的原根，
10 是素数 3^22+2^23=31389448217 的原根，
10 是素数 3^32+2^33=1853028778786433 的原根，
10 是素数 3^36+2^37=150094772735952593 的原根，
10 是素数 3^46+2^47=8862938260389989451257 的原根，
10 是素数 3^80+2^81=147808829414348341167722439464732709953 的原根，
10 是素数 3^154+2^155=29969067287845284806900763424259354345695037325432711901413781193689500137 的原根，
10 是素数 3^236+2^237=39867234790105605031052158475473603885214702979674478224207279045242447503005351752119734009677347787327998900593 的原根，
10 是素数 3^250+2^251= 190683748116796615589766511371277507701260429967651126103174761897479526555470283571068048447508517209471538025816027497 的原根，
10 是素数 3^992+2^993=201504468751837621839727977404685926835150439376946832443975059933977838339689818555216935505351023009283611903196552713908086356058621995407002396777618301177811343575418503951721787383304872793005232962627245632571105557936833267194815304366778547765493764740044293673929368039251196446446723938278591809721982615857996114286344721172111746288859733499249290109426007919969472996555103682274449696455944323255567670689270574629521811105681761209036785000603422679143272833 的原根，

yangchuanju

（接上楼）
（六）设 k 为正整数，t 为非负整数，
若 30k+17 和 2^(4t+3)*(30k+17)+1 都是素数，
则 10 是素数 2^(4t+3)*(30k+17)+1 的原根。
若 30k+29 和 2^(4t+3)*(30k+29)+1 都是素数，
则 10 是素数 2^(4t+3)*(30k+29)+1 的原根。

设 k 为正整数，t 为非负整数，
若 30k+1 和 2^(4t+4)*(30k+1)+1 都是素数，
则 10 是素数 2^(4t+4)*(30k+1)+1 的原根。
若 30k+7 和 2^(4t+4)*(30k+7)+1 都是素数，
则 10 是素数 2^(4t+4)*(30k+7)+1 的原根。

设 k 为正整数，t 为非负整数，
若 30k+11 和 2^(4t+5)*(30k+11)+1 都是素数，
则 10 是素数 2^(4t+5)*(30k+11)+1 的原根。
若 30k+23 和 2^(4t+5)*(30k+23)+1 都是素数，
则 10 是素数 2^(4t+5)*(30k+23)+1 的原根。

设 k 为正整数，t 为非负整数，
若 30k+13 和 2^(4t+6)*(30k+13)+1 都是素数，
则 10 是素数 2^(4t+6)*(30k+13)+1 的原根。
若 30k+19 和 2^(4t+6)*(30k+19)+1 都是素数，
则 10 是素数 2^(4t+6)*(30k+19)+1 的原根。

设 d 为非负整数，
若 3^(4d+2) -2 是素数，则 10 是素数 3^(4d+2) -2 的原根。
4d+2=2, 6, 22, 90, 102, 786, ......
若 5^(2d+2) -2 是素数，则 10 是素数 5^(2d+2) -2 的原根。
2d+2=2, 14, 26, 50, 126, 144, 260, 624, 1424.
若 7^(4d+2) -2 是素数，则 10 是素数 7^(4d+2) -2 的原根。
4d+2=2, 98, 238, 302, ......

（七）设 k 为正整数，
若 30k+17 和 8*(30k+17)+1 都是素数，
则 10 是素数 8*(30k+17)+1 的原根。
设 k 为正整数，
若 30k+29 和 8*(30k+29)+1 都是素数，
则 10 是素数 8*(30k+29)+1 的原根。
断言：无一反例，，，，，，，，，，

设 k 为正整数，
若 30k+11 和 32*(30k+11)+1 都是素数，
则 10 是素数 32*(30k+11)+1 的原根。
设 k 为正整数，
若 30k+23 和 32*(30k+23)+1 都是素数，
则 10 是素数 32*(30k+23)+1 的原根。
断言：无一反例，，，，，，，，，，

设 k 为正整数，
若 30k+13 和 64*(30k+13)+1 都是素数，
则 10 是素数 64*(30k+13)+1 的原根。
设 k 为正整数，
若 30k+19 和 64*(30k+19)+1 都是素数，
则 10 是素数 64*(30k+19)+1 的原根。
断言：无一反例，，，，，，，，，，

设 k 为正整数，
若 30k+17 和 128*(30k+17)+1 都是素数，
则 10 是素数 128*(30k+17)+1 的原根。
设 k 为正整数，
若 30k+29 和 128*(30k+29)+1 都是素数，
则 10 是素数 128*(30k+29)+1 的原根。
断言：无一反例，，，，，，，，，，

（八）由 10 是素数 p=(2k+1)^2 -2 的原根，则 10 是素数 p^(4d+2) -2 的原根。
由 10 是素数 7=3^2 -2 的原根，则 10 是素数 7^(4d+2) -2 的原根。
由 10 是素数 23=5^2 -2 的原根，则 10 是素数 23^(4d+2) -2 的原根。
由 10 是素数 47=7^2 -2 的原根，则 10 是素数 47^(4d+2) -2 的原根。
由 10 是素数 167=13^2 -2 的原根，则 10 是素数 167^(4d+2) -2 的原根。
由 10 是素数 223=15^2 -2 的原根，则 10 是素数 223^(4d+2) -2 的原根。
由 10 是素数 727=27^2 -2 的原根，则 10 是素数 727^(4d+2) -2 的原根。
由 10 是素数 1087=33^2 -2 的原根，则 10 是素数 1087^(4d+2) -2 的原根。
由 10 是素数 1223=35^2 -2 的原根，则 10 是素数 1223^(4d+2) -2 的原根。
由 10 是素数 1367=37^2 -2 的原根，则 10 是素数 1367^(4d+2) -2 的原根。
由 10 是素数 1847=43^2 -2 的原根，则 10 是素数 1847^(4d+2) -2 的原根。
由 10 是素数 2207=47^2 -2 的原根，则 10 是素数 2207^(4d+2) -2 的原根。

蔡家雄老师关于有原根10素数的猜想很多，分散在《数论小猜想》等多个帖子中，上面的摘录不完全，也有重复，编号是笔者随意添加的。
摘录的内容如有错误，请老师更正！

yangchuanju

【转载】蔡家雄贴
【完全循环节等差(9240)九生素数有无穷多组】

10是如下等差9生素数(公差9240)的原根，即：这些素数倒数具有最大循环节长！！！

1---(95339,104579,113819,123059,132299,141539,150779,160019,169259)

2---(7827167,7836407,7845647,7854887,7864127,7873367,7882607,7891847,7901087)

3---(9195167,9204407,9213647,9222887,9232127,9241367,9250607,9259847,9269087)

4---(32288903,32298143,32307383,32316623,32325863,32335103,32344343,32353583,32362823)

5---(59941697,59950937,59960177,59969417,59978657,59987897,59997137,60006377,60015617)

6---(72980177,72989417,72998657,73007897,73017137,73026377,73035617,73044857,73054097)

7---(77003567,77012807,77022047,77031287,77040527,77049767,77059007,77068247,77077487)

8---(121526753,121535993,121545233,121554473,121563713,121572953,121582193,121591433,121600673)

9---(121535993,121545233,121554473,121563713,121572953,121582193,121591433,121600673,121609913)

10---(171184589,171193829,171203069,171212309,171221549,171230789,171240029,171249269,171258509)