cp's OEIS Frontend

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

%I A291690 #17 Oct 07 2017 14:58:04
%S A291690 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 A291690 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 A291690 3,5,22,17,14,3,29,15,2,13,13,19,6,2,10,10,18,6,21,26
%N A291690 Least positive integer g which is a primitive root modulo prime(n) and also a primitive root modulo prime(n+1).
%C A291690 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 A291690 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 A291690 (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 A291690 Zhi-Wei Sun, <a href="/A291690/b291690.txt">Table of n, a(n) for n = 1..10000</a>
%H A291690 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 A291690 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 A291690 a(2) = 2 since 2 is a primitive root modulo prime(2) = 3 and also a primitive root modulo prime(3) = 5.
%e A291690 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 A291690 p[n_]:=Prime[n];
%t A291690 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 A291690 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 A291690 (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 A291690 Cf. A000040, A242345, A243164, A243403, A291615, A291657.
%K A291690 nonn
%O A291690 1,1
%A A291690 _Zhi-Wei Sun_, Aug 29 2017