A229910 a(n) = |{0 < g < prime(n): both g and g + g^{-1} are primitive roots modulo prime(n)}|, where g^{-1} is the inverse of g modulo prime(n).

0, 0, 0, 0, 2, 0, 4, 2, 4, 4, 2, 4, 8, 6, 10, 8, 14, 4, 4, 12, 8, 6, 20, 24, 16, 16, 12, 26, 8, 16, 14, 12, 24, 14, 32, 10, 20, 18, 40, 48, 44, 4, 30, 16, 32, 18, 14, 18, 56, 8, 60, 40, 12, 40, 64, 64, 72, 20, 40, 32, 36, 80, 22, 44, 24, 72, 22, 36, 86, 32, 84, 88, 40, 24, 28, 94, 104, 28, 76, 28

Offset

1,5

Comments

Conjecture: a(n) > 0 for all n > 6. In other words, for any prime p > 13, there is a primitive root g modulo p such that g + g^{-1} is also a primitive root modulo p, where g^{-1} is the inverse of g modulo p.

Note that a(n) is even for any n > 1. In fact, if g is a primitive root modulo a prime p > 3, then the inverse of g mod p is different from g since g^2 cannot be congruent to 1 modulo p.

Conjecture: Let F be a finite field with |F| = q > 13. Then there is a primitive root g of F (i.e., a generator of the cyclic group F\{0}) such that g + g^{-1} is also a primitive root of F. If q > 61, then there exists a primitive root g of F such that g - g^{-1} is also a primitive root of F.

The author has proved this for any finite field F with |F| > 2^{66}.

Links

M. F. Hasler, Table of n, a(n) for n = 1..1000

Example

a(5) = 2 since 2 and 6 are primitive roots modulo prime(5) = 11 with 2*6 == 1 (mod 11) and 2 + 6 = 8 also a primitive root modulo 11.
This example recalls that there is no symmetry g -> -g (in Z/pZ) (nor a symmetry w.r.t. odd/even g), therefore one cannot (unfortunately) compute a(n) by taking twice the count of the g<prime(n)/2 which satisfy the condition. E.g., for p=19=prime(8), only g = 14 (= -5) and g = 15 (= -4) are in the set. - M. F. Hasler, Oct 06 2013

Mathematica

gp[g_, p_]:=gp[g, p]=Mod[g, p]>0&&Length[Union[Table[Mod[g^k, p], {k, 1, p-1}]]]==p-1
a[n_]:=Sum[If[gp[g, Prime[n]]&&gp[g+PowerMod[g, -1, Prime[n]], Prime[n]], 1, 0], {g, 1, Prime[n]-1}]
Table[a[n], {n, 1, 80}]

Prog

(PARI) A229910(n)=my(p=prime(n)); sum(g=2, p-2, znorder(Mod(g, p))==p-1 & Mod(g, p)^-1+g & znorder(Mod(g, p)^-1+g)==p-1) \\ M. F. Hasler, Oct 06 2013
(PARI) A229910(n)={my(p=prime(n), u=0, s=0, i); n=p-1; for(g=2, p-2, bittest(u, g)&next; znorder(Mod(g, p))<n&next; u+=1<<lift(i=Mod(g, p)^-1); i+g||next; znorder(i+g)<n||s++); s*2} \\ about 20% faster. - M. F. Hasler, Oct 06 2013
(Perl) use ntheory ":all"; sub a229910 { my $p=nth_prime(shift); scalar(grep {is_primitive_root($_, $p) && is_primitive_root($_+invmod($_, $p), $p)} 2..$p-2); } # Dana Jacobsen, Sep 19 2016

Crossrefs

Cf. A001918, A229899.

Cf. A010554.

Sequence in context: A094572 A323905 A079534 * A097042 A332001 A196606

Adjacent sequences: A229907 A229908 A229909 * A229911 A229912 A229913

Keyword

nonn

Author

Zhi-Wei Sun, Oct 03 2013

Extensions

Values a(1..400) double checked and extended to n=1000 by M. F. Hasler, Oct 06 2013

Status

approved