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

7, 23, 47, 71, 79, 103, 167, 191, 199, 239, 263, 271, 311, 359, 367, 383, 463, 479, 487, 503, 599, 607, 647, 719, 743, 751, 823, 839, 863, 887, 967, 983, 991, 1031, 1039, 1063, 1087, 1151, 1223, 1231, 1279, 1303, 1319, 1367, 1439, 1447, 1487, 1511, 1543, 1559

Offset

1,1

Comments

Original name: Primes with semiprimitive root 2.

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

If r=2, then (-1/p)=-1 and, consequently, a(n)==-1(mod 4).

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.

Links

Amiram Eldar, Table of n, a(n) for n = 1..10000

Christian Elsholtz, Almost all primes have a multiple of small Hamming weight, arXiv:1602.05974 [math.NT], 2016. See p. 6.

Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv preprint arXiv:1608.00862 [math.GM], 2016.

V. Shevelev, On the Newman sum over multiples of a prime with a primitive or semiprimitive root 2, arXiv:0710.1354 [math.NT], 2007.

V. Shevelev Exact exponent in the remainder term of Gelfond's digit theorem in the binary case, Acta Arithm. 136 (2009) 91-100, eq. (10)

Formula

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

A006694((a(n)-1)/2)=2 and A064287((a(n)-1)/2)=1.

Mathematica

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

Prog

(PARI)
{ forprime (p=3, 10^4,
    rp = znorder(Mod(+2, p));
    rm = znorder(Mod(-2, p));
    if ( (rp!=p-1) && (rm==p-1), print1(p, ", ") );
); }
/* Joerg Arndt, Jun 03 2012 */
(PARI) is(n)=n%8==7 && isprime(n) && znorder(Mod(-2, n))==n-1 \\ Charles R Greathouse IV, Nov 30 2017

Crossrefs

Cf. A006694, A002326, A064287, A001917, A001122, A133954, A115591.

Sequence in context: A097149 A185007 A308732 * A002146 A336092 A184882

Adjacent sequences: A139032 A139033 A139034 * A139036 A139037 A139038

Keyword

nonn

Author

Vladimir Shevelev, May 31 2008, Jun 06 2008

Extensions

New name from Joerg Arndt, Jun 03 2012

Status

approved