A105876 Primes for which -4 is a primitive root.

3, 7, 11, 19, 23, 47, 59, 67, 71, 79, 83, 103, 107, 131, 139, 163, 167, 179, 191, 199, 211, 227, 239, 263, 271, 311, 347, 359, 367, 379, 383, 419, 443, 463, 467, 479, 487, 491, 503, 523, 547, 563, 587, 599, 607, 619, 647, 659, 719, 743, 751, 787, 823, 827, 839, 859, 863

Offset: 1

Author

N. J. A. Sloane, Apr 24 2005

Keywords

• nonn

Comments

Also, primes for which -16 is a primitive root. For proof see following comments from Michael Somos, Aug 07 2009:

Let p = 8*t + 3 be prime. It is well-known that 2 is a primitive root.

We will use the obvious fact that if a primitive root is a power of another element, then that other element is also a primitive root. So

-1 == 2^(4*t+1) (mod p) because 2 is primitive root.

-2 == 2^(4*t+2) == 4^(2*t+1) (mod p) obvious

2 == (-4)^(2*t+1) (mod p) obvious, therefore -4 is also primitive root.

2 == 2^(8*t+3) (mod p) obviously works not just for 2

4 == 2^(8*t+4) == 16^(2*t+1) (mod p) obvious

-4 == (-16)^(2*t+1) (mod p) obvious, therefore -16 is also primitive root.

The case where p = 8*t + 7 is similar.

From Jianing Song, Dec 24 2022: (Start)

Equivalently, primes p == 3 (mod 4) such that the multiplicative order of 4 modulo p is (p-1)/2 (a subsequence of A216371).

Proof of equivalence: let ord(a,k) be the multiplicative of a modulo k. First we notice that all terms are congruent to 3 modulo 4, since -4 is a quadratic residue modulo p if p == 1 (mod 4). If ord(4,p) = (p-1)/2. Note that (p-1)/2 is odd, so it is coprime to ord(-1,p) = 2. As a result, ord(-4,p) = ((p-1)/2) * 2 = p-1. Conversely, If ord(-4,p) = p-1, we must have ord(4,p) = (p-1)/2 by noting that ord(-4,p) <= lcm(2,ord(4,p)).

Also primes p such that the multiplicative order of 16 modulo p is (p-1)/2. Proof: note that ord(16,p) = ord(-4,p)/gcd(ord(-4,p),2). If ord(-4,p) = p-1, then ord(16,p) = (p-1)/2. Conversely, if ord(16,p) = (p-1)/2, then ord(-4,p) = p-1, since otherwise ord(-4,p) = (p-1)/2 is odd, which is impossible since that -4 is not a quadratic residue modulo a prime p == 3 (mod 4).

{(a(n)-1)/2} is the sequence of indices of fixed points of A302141.

An odd prime p is a term if and only if p == 3 (mod 4) and the multiplicative order of 2 modulo p is p-1 or (p-1)/2 (p-1 if p == 3 (mod 8), (p-1)/2 if p == 7 (mod 8)).

It seems that a(n) = 2*A163778(n-1) + 1 for n >= 2. (End)

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Index entries for primes by primitive root

Crossrefs

Cf. A114564, A302141, A163778. A216371 is a supersequence.

Programs

Mathematica

pr=-4; Select[Prime[Range[200]], MultiplicativeOrder[pr, # ] == #-1 &] (* OR *)
a[p_, q_]:=Sum[2 Cos[2^n Pi/((2 q+1)(2 p+1))],{n,1,2 q p}]
2 Select[Range[500],Rationalize[N[a[#,2],20]]==1 &]+1
(* Gerry Martens, Apr 28 2015 *)

PARI

is(n)=isprime(n) && n>2 && znorder(Mod(-4,n))==n-1 \\ Charles R Greathouse IV, Apr 30 2015

Extensions

Edited by N. J. A. Sloane, Aug 08 2009