A243164 - OEIS

%I #12 Jun 01 2014 18:39:58

%S 0,0,0,1,0,0,1,1,1,1,2,1,2,2,3,3,3,2,3,4,2,2,4,3,3,5,3,5,5,6,2,5,5,4,

%T 4,2,4,6,7,6,7,2,7,4,7,4,4,6,7,3,7,7,3,7,7,9,7,6,5,6,6,7,7,9,4,9,8,2,

%U 10,7,9,11,5,6,5,9,11,8,6,9

%N Number of primes p < n such that p*n is a primitive root modulo prime(n).

%C Conjecture: (i) a(n) > 0 for all n > 6.

%C (ii) Any integer n > 6 can be written as k + m with k > 0 and m > 0 such that k*m is a primitive root modulo prime(n).

%C We have verified part (i) for all n = 7, ..., 2*10^5.

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

%e a(4) = 1 since 3 is prime with 3*4 = 12 a primitive root modulo prime(4) = 7.

%e a(9) = 1 since 7 is prime with 7*9 = 63 a primitive root modulo prime(9) = 23.

%e a(10) = 1 since 5 is prime with 5*10 = 50 a primitive root modulo prime(10) = 29.

%e a(12) = 1 since 2 is prime with 2*12 = 24 a primitive root modulo prime(12) = 37.

%t dv[n_]:=Divisors[n]

%t Do[m=0;Do[Do[If[Mod[(Prime[k]*n)^(Part[dv[Prime[n]-1],i]),Prime[n]]==1,Goto[aa]],{i,1,Length[dv[Prime[n]-1]]-1}];m=m+1;Label[aa];Continue,{k,1,PrimePi[n-1]}];Print[n," ",m];Continue,{n,1,80}]

%Y Cf. A000040, A000720, A237497, A237578, A242748.

%K nonn

%O 1,11

%A _Zhi-Wei Sun_, May 31 2014