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

Author

Zhi-Wei Sun, Oct 03 2013

Keywords

• nonn

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

Examples

			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
		

Links

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

Crossrefs

Cf. A001918, A229899.

Cf. A010554.

Programs

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

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

Extensions

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