cp's OEIS Frontend

A364867 Primes p such that the multiplicative order of 9 modulo p is (p-1)/2.

%I A364867 #25 Nov 24 2024 09:29:52
%S A364867 5,7,11,17,19,23,29,31,43,47,53,59,71,79,83,89,101,107,113,127,131,
%T A364867 137,139,149,163,167,173,179,191,197,199,211,223,227,233,239,251,257,
%U A364867 263,269,281,283,293,311,317,331,347,353,359,379,383,389,401,419,443,449,461,463,467,479,487
%N A364867 Primes p such that the multiplicative order of 9 modulo p is (p-1)/2.
%C A364867 Primes p such that the multiplicative order of 9 modulo p is of the maximum possible value.
%C A364867 Primes p such that 3 or -3 (or both) is a primitive root modulo p. Proof of equivalence: let ord(a,k) be the multiplicative order of a modulo p. if ord(3,p) = p-1, then clearly ord(9,p) = (p-1)/2. If ord(-3,p) = p-1, then we also have ord(9,p) = (p-1)/2. Conversely, suppose that ord(9,p) = (p-1)/2, then ord(3,p) = p-1 or (p-1)/2, and ord(-3,p) = p-1 or (p-1)/2. If ord(3,p) = ord(-3,p) = (p-1)/2, then we have that (p-1)/2 is odd and (-1)^((p-1)/2) == 1 (mod p), a contradiction.
%C A364867 A prime p is a term if and only if one of the two following conditions holds: (a) 3 is a primitive root modulo p; (b) p == 3 (mod 4), and the multiplicative order of 3 modulo p is (p-1)/2 (in this case, we have p == 11 (mod 12) since 3 is a quadratic residue modulo p).
%C A364867 A prime p is a term if and only if one of the two following conditions holds: (a) -3 is a primitive root modulo p; (b) p == 3 (mod 4), and the multiplicative order of -3 modulo p is (p-1)/2 (in this case, we have p == 7 (mod 12) since -3 is a quadratic residue modulo p).
%C A364867 No terms are congruent to 1 modulo 12, since otherwise we would have 9^((p-1)/4) = (+-3)^((p-1)/2) == 1 (mod p). - _Jianing Song_, May 14 2024
%H A364867 Jianing Song, <a href="/A364867/b364867.txt">Table of n, a(n) for n = 1..10000</a>
%e A364867 7 is a term since the multiplicative order of 9 modulo 7 is 3 = (7-1)/2.
%t A364867 okQ[p_] := MultiplicativeOrder[9, p] == (p - 1)/2;
%t A364867 Select[Prime[Range[100]], okQ] (* _Jean-François Alcover_, Nov 24 2024 *)
%o A364867 (PARI) isA364867(p) = isprime(p) && (p!=3) && znorder(Mod(9, p)) == (p-1)/2
%o A364867 (Python)
%o A364867 from sympy import n_order, nextprime
%o A364867 from itertools import islice
%o A364867 def A364867_gen(startvalue=4): # generator of terms >= startvalue
%o A364867     p = max(startvalue-1,3)
%o A364867     while (p:=nextprime(p)):
%o A364867         if n_order(9,p) == p-1>>1:
%o A364867             yield p
%o A364867 A364867_list = list(islice(A364867_gen(),20)) # _Chai Wah Wu_, Aug 11 2023
%Y A364867 Union of A019334 and A105875.
%Y A364867 A105881 is the subsequence of terms congruent to 3 modulo 4.
%Y A364867 Cf. A211245 (order of 9 mod n-th prime), A216371.
%K A364867 nonn,easy
%O A364867 1,1
%A A364867 _Jianing Song_, Aug 11 2023