A291690 Least positive integer g which is a primitive root modulo prime(n) and also a primitive root modulo prime(n+1).

5, 2, 3, 17, 2, 6, 3, 10, 10, 3, 13, 13, 12, 5, 5, 2, 2, 2, 7, 11, 28, 6, 6, 7, 7, 11, 5, 6, 6, 3, 6, 6, 3, 2, 12, 6, 18, 20, 5, 2, 2, 21, 19, 5, 3, 3, 3, 5, 6, 6, 21, 7, 14, 6, 5, 7, 15, 6, 11, 3, 3, 5, 22, 17, 14, 3, 29, 15, 2, 13, 13, 19, 6, 2, 10, 10, 18, 6, 21, 26

Offset: 1

Author

Zhi-Wei Sun, Aug 29 2017

Keywords

• nonn

Comments

Clearly, a(n) < prime(n)*prime(n+1) by the Chinese Remainder Theorem. It seems that for any positive integer n other than 1, 4, 8 there is a prime p < prime(n) which is a primitive root modulo prime(n) and also a primitive root modulo prime(n+1).

Conjecture: (i) For any distinct primes p and q, there is a positive integer g not exceeding sqrt(4*p*q+1) such that g is a primitive root modulo p and also a primitive root modulo q. We may require further that g < sqrt(p*q) if {p,q} is not among the 15 pairs {2,3}, {2,11}, {2,13}, {2,59}, {2,131}, {2,181}, {3,7}, {3,31}, {3,79}, {3,191}, {3,199}, {5,271}, {7,11}, {7,13} and {7,71}.

(ii) For each integer n > 1, there is a constant c(n) > 0, such that for any n distinct primes p(1),...,p(n) there is a positive integer g < c(n)*(p(1)*...*p(n))^(1/n) which is a primitive root modulo p(k) for all k = 1,...,n.

Examples

			a(1) = 5 since 5 is a primitive root modulo prime(1) = 2 and also a primitive root modulo prime(2) = 3, but none of 1, 2, 3, 4 has this property.
a(2) = 2 since 2 is a primitive root modulo prime(2) = 3 and also a primitive root modulo prime(3) = 5.
a(4) = 17 since 17 is the least positive integer which is a primitive root modulo prime(4) = 7 and also a primitive root modulo prime(5) = 11.
		

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
• Zhi-Wei Sun, New observations on primitive roots modulo primes, arXiv:1405.0290 [math.NT], 2014.

Crossrefs

Cf. A000040, A242345, A243164, A243403, A291615, A291657.

Programs

Mathematica

p[n_]:=Prime[n];
Do[g=0;Label[aa];g=g+1;If[Mod[g,p[n]]==0||Mod[g,p[n+1]]==0,Goto[aa]];Do[If[Mod[g^(Part[Divisors[p[n]-1],i])-1,p[n]]==0,Goto[aa]],{i,1,Length[Divisors[p[n]-1]]-1}];
Do[If[Mod[g^(Part[Divisors[p[n+1]-1],j])-1,p[n+1]]==0,Goto[aa]],{j,1,Length[Divisors[p[n+1]-1]]-1}];Print[n," ",g],{n,1,80}]

PARI

a(n,p=prime(n))=my(q=nextprime(p+1),g=2); while(gcd(g,p*q)>1 || znorder(Mod(g,p))Charles R Greathouse IV, Aug 30 2017