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,11

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.

Links

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

Example

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.

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

Crossrefs

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

Sequence in context: A306433 A308174 A126237 * A333708 A132203 A158925

Adjacent sequences: A243161 A243162 A243163 * A243165 A243166 A243167

Keyword

nonn

Author

Zhi-Wei Sun, May 31 2014

Status

approved