分享一个有意思的数论问题，8k+3型质数最小原根为2的充分必要条件是4k+1也为质数

awei

分享一个有意思的数论问题，8k+3型质数最小原根为2的充分必要条件是4k+1也为质数
同理8k+3型质数的最小原根为2，那么4k+1必为质数。
电脑上的软件卸载了，只能用Python写的程序在Google colab上运行，不知道代码有没有错误
import requests

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def find_min_primitive_root(p):
    for g in range(2, p):
        is_primitive_root = True
        for i in range(1, p - 1):
            if pow(g, i, p) == 1:
                is_primitive_root = False
                break
        if is_primitive_root:
            return g
    return None

def main():
    for k in range(1, 100):
        num1 = 4 * k + 1
        num2 = 8 * k + 3
        if is_prime(num1) and is_prime(num2):
            g = find_min_primitive_root(num2)
            print(f"k: {k}, 4k+1: {num1}, 8k+3: {num2}, min primitive root: {g}")

if __name__ == '__main__':
    main()

awei

8k+3型质数的最小原根为2，不能断定4k+1为质数。
用wolfram-one检查的确有误。

当4k+1为质数，8k+3也为质数，8k+3的最小原根一定为2，这个推导起来也不难，计算机wolfram-one验证也很符合。


In[17]:=
Do[If[Mod[Prime[n],8]==3,If[PrimitiveRoot[Prime[n],1]==2,If[Mod[(Prime[n]-1)/2,4]==1,Print[Prime[n],"___",(Prime[n]-1)/2,"___",PrimeQ[(Prime[n]-1)/2]]]]],{n,1,100}]

3___1___False
11___5___True
19___9___False
59___29___True
67___33___False
83___41___True
107___53___True
131___65___False
139___69___False
163___81___False
179___89___True
211___105___False
227___113___True
347___173___True
379___189___False
419___209___False
443___221___False
467___233___True
491___245___False
523___261___False

In[19]:=
Do[If[Mod[Prime[n],4]==1,If[PrimeQ[2*Prime[n]+1],Print[Prime[n],"___",2*Prime[n]+1,"___",PrimitiveRoot[2*Prime[n]+1,1]]]],{n,1,1000}]
5___11___2
29___59___2
41___83___2
53___107___2
89___179___2
113___227___2
173___347___2
233___467___2
281___563___2
293___587___2
509___1019___2
593___1187___2
641___1283___2
653___1307___2
761___1523___2
809___1619___2
953___1907___2
1013___2027___2
1049___2099___2
1229___2459___2
1289___2579___2
1409___2819___2
1481___2963___2
1601___3203___2
1733___3467___2
1889___3779___2
1901___3803___2
1973___3947___2
2069___4139___2
2129___4259___2
2141___4283___2
2273___4547___2
2393___4787___2
2549___5099___2
2693___5387___2
2741___5483___2
2753___5507___2
2969___5939___2
3329___6659___2
3389___6779___2
3413___6827___2
3449___6899___2
3593___7187___2
3761___7523___2
3821___7643___2
4073___8147___2
4349___8699___2
4373___8747___2
4409___8819___2
4481___8963___2
4733___9467___2
4793___9587___2
5081___10163___2
5333___10667___2
5441___10883___2
5501___11003___2
5741___11483___2
5849___11699___2
6053___12107___2
6101___12203___2
6113___12227___2
6173___12347___2
6269___12539___2
6329___12659___2
6449___12899___2
6521___13043___2
6581___13163___2
6761___13523___2
7121___14243___2
7193___14387___2
7349___14699___2
7433___14867___2
7541___15083___2
7649___15299___2
7841___15683___2

awei

这其实也是一个寻找有原根2质数的一个方法，挺好玩