# Smallest prime $p$ which every integer $< n$ is a primitive root $\mod p$

Another interesting question related to primitive roots is what is the smallest prime $p$ for which the primes less than $n$ are primitive roots $\mod p$. The sequence of primes would be $[p, p_2, p_3,...]$ for every additional prime $k > n$. For instance, the first prime is $3$ because $3$ is the smallest prime $p$ such that $2$ is a primitive root $\mod p$. The next prime in this sequence is $5$ because $5$ is the smallest prime $p$ such that $2$ and $3$ are primitive roots $\mod p$.It follows that $53$ is the third prime in the sequence because it is the smallest prime $p$ such that $2, 3,$ and $5$ are primitive roots $\mod p$. The fourth prime in the sequence is $173$ the smallest prime $p$ such that $2, 3, 5,$ and $7$ are primitive roots $\mod p$. The fifth would also be $173$ the smallest prime $p$ such that $2, 3, 5, 7$ and $11$ are primitive roots $\mod p$, and so on. Duplicates in the sequence are allowed. Is anyone able to provide the list of primes in this sequence (up to say, the first $100$ of them) or a program that could do the work? Thanks in advance.

• If $2$ is a primitive root, and $3$ is a primitive root, then $2\cdot 3$ is not a primitive root. – Thomas Andrews Jan 25 '18 at 4:58
• Ok I see. How about asking the question about the smallest prime $p$ which the first $n$ primes are primitive roots $\mod n$. – J. Linne Jan 25 '18 at 5:01
• The title does not reflect the question. – lhf Jan 25 '18 at 10:58
• See oeis.org/A213052. – lhf Jan 25 '18 at 10:59
• @lhf it seems all the primes in this sequence (except 3) are congruent to $5 \mod 24$. Is there a way to prove this by any chance? – J. Linne Jan 26 '18 at 3:17

The following PARI/GP-program does the job :

? k=3;x=primes(k);p=prime(k);gef=0;while(gef==0,p=nextprime(p+1);s=select(n->zno
rder(Mod(n,p))==p-1,x);if(s==x,gef=1));print(p)
53
?


Just change $k$ to get the smallest prime for another $k$.

The smallest primes for $k\le 18$ are :

? for(k=1,20,x=primes(k);p=prime(k);gef=0;while(gef==0,p=nextprime(p+1);s=select
(n->znorder(Mod(n,p))==p-1,x);if(s==x,gef=1));print(k," ",p))
1 3
2 5
3 53
4 173
5 173
6 293
7 2477
8 9173
9 9173
10 61613
11 74093
12 74093
13 74093
14 170957
15 360293
16 679733
17 2004917
18 2004917


The calculation for $k=19$ is currently running.

• The program calculates the smallest prime $p_k$, such that the first $k$ primes are primitive roots modulo $p_k$. The program just found $p_{19}=69009533$ and is running for $k=20$. – Peter Jan 25 '18 at 10:43
• $p_{20}=138473837$ – Peter Jan 25 '18 at 11:41
• Thank you so much this helps a lot! – J. Linne Jan 26 '18 at 3:14
• oeis.org/A213052 gives the first 27 entries. – lhf Jan 26 '18 at 11:39