2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If $2$ is a primitive root, and $3$ is a primitive root, then $2\cdot 3$ is not a primitive root. $\endgroup$ – Thomas Andrews Jan 25 '18 at 4:58
  • $\begingroup$ Ok I see. How about asking the question about the smallest prime $p$ which the first $n$ primes are primitive roots $\mod n$. $\endgroup$ – J. Linne Jan 25 '18 at 5:01
  • $\begingroup$ The title does not reflect the question. $\endgroup$ – lhf Jan 25 '18 at 10:58
  • $\begingroup$ See oeis.org/A213052. $\endgroup$ – lhf Jan 25 '18 at 10:59
  • 1
    $\begingroup$ @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? $\endgroup$ – J. Linne Jan 26 '18 at 3:17
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Peter Jan 25 '18 at 10:43
  • $\begingroup$ $p_{20}=138473837$ $\endgroup$ – Peter Jan 25 '18 at 11:41
  • $\begingroup$ Thank you so much this helps a lot! $\endgroup$ – J. Linne Jan 26 '18 at 3:14
  • $\begingroup$ oeis.org/A213052 gives the first 27 entries. $\endgroup$ – lhf Jan 26 '18 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.