cp's OEIS Frontend

A139035 Primes of the form 4*k+3 with primitive root -2.

%I A139035 #56 Dec 30 2024 17:24:13
%S A139035 7,23,47,71,79,103,167,191,199,239,263,271,311,359,367,383,463,479,
%T A139035 487,503,599,607,647,719,743,751,823,839,863,887,967,983,991,1031,
%U A139035 1039,1063,1087,1151,1223,1231,1279,1303,1319,1367,1439,1447,1487,1511,1543,1559
%N A139035 Primes of the form 4*k+3 with primitive root -2.
%C A139035 Original name: Primes with semiprimitive root 2.
%C A139035 If p is a prime, then we call r a semiprimitive root if it has order (p-1)/2 and there is no x for which a^x is congruent to -1 (mod p).  So +/- r^k, 0 <= k <= (p-3)/2 is a complete set of nonzero residues (mod p).
%C A139035 If r=2, then (-1/p)=-1 and, consequently, a(n)==-1(mod 4).
%C A139035 Besides, (2/a(n))=1. Indeed, since 2^((p-1)/2)=1 (mod p), then 2==2^((p+1)/2)=(2^((p+1)/4))^2. Therefore, (a(n))^2==1(mod 16) and thus a(n)==-1(mod 8). This yields that residues 1,2,...,2^((p-3)/2) are quadratic residues modulo a(n), while -1,-2,...,-2^((p-3)/2) are quadratic nonresidues modulo a(n). Primitive root of a(n) is greater than or equal to 3. All terms are in A115591.
%C A139035 Conjecture: primes that have both primitive root -2 and -4. - _Davide Rotondo_, Dec 20 2024
%H A139035 Amiram Eldar, <a href="/A139035/b139035.txt">Table of n, a(n) for n = 1..10000</a>
%H A139035 Christian Elsholtz, <a href="http://arxiv.org/abs/1602.05974">Almost all primes have a multiple of small Hamming weight</a>, arXiv:1602.05974 [math.NT], 2016. See p. 6.
%H A139035 Jonas Kaiser, <a href="https://arxiv.org/abs/1608.00862">On the relationship between the Collatz conjecture and Mersenne prime numbers</a>, arXiv preprint arXiv:1608.00862 [math.GM], 2016.
%H A139035 Vladimir Shevelev, <a href="http://arxiv.org/abs/0710.1354">On the Newman sum over multiples of a prime with a primitive or semiprimitive root 2</a>, arXiv:0710.1354 [math.NT], 2007.
%H A139035 Vladimir Shevelev <a href="https://doi.org/10.4064/aa136-1-7">Exact exponent in the remainder term of Gelfond's digit theorem in the binary case</a>, Acta Arithm. 136 (2009) 91-100, eq. (10).
%F A139035 Prime p is in the sequence iff p==-1(mod 8) and A002326((p-1)/2)=(p-1)/2. A sufficient condition: if p==-1 (mod 8) and (p-1)/2 is prime, then p is in the sequence (the converse statement, generally speaking, is not true).
%F A139035 A006694((a(n)-1)/2)=2 and A064287((a(n)-1)/2)=1.
%t A139035 Reap[For[p = 3, p <= 10^4, p = NextPrime[p], rp = MultiplicativeOrder[2, p]; rm = MultiplicativeOrder[-2, p]; If[rp != p-1 && rm == p-1, Sow[p]]] ][[2, 1]] (* _Jean-François Alcover_, Sep 03 2016, after _Joerg Arndt_ *)
%o A139035 (PARI)
%o A139035 { forprime (p=3, 10^4,
%o A139035     rp = znorder(Mod(+2,p));
%o A139035     rm = znorder(Mod(-2,p));
%o A139035     if ( (rp!=p-1) && (rm==p-1), print1(p,", ") );
%o A139035 );}
%o A139035 /* _Joerg Arndt_, Jun 03 2012 */
%o A139035 (PARI) is(n)=n%8==7 && isprime(n) && znorder(Mod(-2,n))==n-1 \\ _Charles R Greathouse IV_, Nov 30 2017
%Y A139035 Cf. A006694, A002326, A064287, A001917, A001122, A133954, A115591.
%K A139035 nonn
%O A139035 1,1
%A A139035 _Vladimir Shevelev_, May 31 2008, Jun 06 2008
%E A139035 New name from _Joerg Arndt_, Jun 03 2012