|
%I #36 Mar 31 2024 15:03:09
%S 3,7,11,19,23,47,59,67,71,79,83,103,107,131,139,163,167,179,191,199,
%T 211,227,239,263,271,311,347,359,367,379,383,419,443,463,467,479,487,
%U 491,503,523,547,563,587,599,607,619,647,659,719,743,751,787,823,827,839,859,863
%N Primes for which -4 is a primitive root.
%C Also, primes for which -16 is a primitive root. For proof see following comments from _Michael Somos_, Aug 07 2009:
%C Let p = 8*t + 3 be prime. It is well-known that 2 is a primitive root.
%C 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
%C -1 == 2^(4*t+1) (mod p) because 2 is primitive root.
%C -2 == 2^(4*t+2) == 4^(2*t+1) (mod p) obvious
%C 2 == (-4)^(2*t+1) (mod p) obvious, therefore -4 is also primitive root.
%C 2 == 2^(8*t+3) (mod p) obviously works not just for 2
%C 4 == 2^(8*t+4) == 16^(2*t+1) (mod p) obvious
%C -4 == (-16)^(2*t+1) (mod p) obvious, therefore -16 is also primitive root.
%C The case where p = 8*t + 7 is similar.
%C From _Jianing Song_, Dec 24 2022: (Start)
%C Equivalently, primes p == 3 (mod 4) such that the multiplicative order of 4 modulo p is (p-1)/2 (a subsequence of A216371).
%C 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)).
%C 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).
%C {(a(n)-1)/2} is the sequence of indices of fixed points of A302141.
%C 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)).
%C It seems that a(n) = 2*A163778(n-1) + 1 for n >= 2. (End)
%H Vincenzo Librandi, <a href="/A105876/b105876.txt">Table of n, a(n) for n = 1..1000</a>
%H <a href="/index/Pri#primes_root">Index entries for primes by primitive root</a>
%t pr=-4; Select[Prime[Range[200]], MultiplicativeOrder[pr, # ] == #-1 &] (* OR *)
%t a[p_, q_]:=Sum[2 Cos[2^n Pi/((2 q+1)(2 p+1))],{n,1,2 q p}]
%t 2 Select[Range[500],Rationalize[N[a[#,2],20]]==1 &]+1
%t (* _Gerry Martens_, Apr 28 2015 *)
%o (PARI) is(n)=isprime(n) && n>2 && znorder(Mod(-4,n))==n-1 \\ _Charles R Greathouse IV_, Apr 30 2015
%Y Cf. A114564, A302141, A163778. A216371 is a supersequence.
%K nonn
%O 1,1
%A _N. J. A. Sloane_, Apr 24 2005
%E Edited by _N. J. A. Sloane_, Aug 08 2009
|
