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

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, 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, 10, 7, 9, 11, 5, 6, 5, 9, 11, 8, 6, 9

Offset: 1

Author

Zhi-Wei Sun, May 31 2014

Keywords

• nonn

Comments

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

(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).

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

Examples

			a(4) = 1 since 3 is prime with 3*4 = 12 a primitive root modulo prime(4) = 7.
a(9) = 1 since 7 is prime with 7*9 = 63 a primitive root modulo prime(9) = 23.
a(10) = 1 since 5 is prime with 5*10 = 50 a primitive root modulo prime(10) = 29.
a(12) = 1 since 2 is prime with 2*12 = 24 a primitive root modulo prime(12) = 37.
		

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 1..10000

Crossrefs

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

Programs

Mathematica

dv[n_]:=Divisors[n]
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}]