A105876 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

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

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

PROG

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

CROSSREFS