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
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
KEYWORD
nonn
AUTHOR
Vladimir Shevelev, May 31 2008, Jun 06 2008
EXTENSIONS
New name from Joerg Arndt, Jun 03 2012
STATUS
approved