A291690 - OEIS

%I #17 Oct 07 2017 14:58:04

%S 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,

%T 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,

%U 3,5,22,17,14,3,29,15,2,13,13,19,6,2,10,10,18,6,21,26

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

%C 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).

%C 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}.

%C (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.

%H Zhi-Wei Sun, <a href="/A291690/b291690.txt">Table of n, a(n) for n = 1..10000</a>

%H Zhi-Wei Sun, <a href="http://arxiv.org/abs/1405.0290">New observations on primitive roots modulo primes</a>, arXiv:1405.0290 [math.NT], 2014.

%e 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.

%e a(2) = 2 since 2 is a primitive root modulo prime(2) = 3 and also a primitive root modulo prime(3) = 5.

%e 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.

%t p[n_]:=Prime[n];

%t 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}];

%t 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}]

%o (PARI) a(n,p=prime(n))=my(q=nextprime(p+1),g=2); while(gcd(g,p*q)>1 || znorder(Mod(g,p))<p-1 || znorder(Mod(g,q))<q-1, g++); g \\ _Charles R Greathouse IV_, Aug 30 2017

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

%K nonn

%O 1,1

%A _Zhi-Wei Sun_, Aug 29 2017