VOOZH about

URL: https://oeis.org/A070179

⇱ A070179 - OEIS

login
A070179
Primes p such that x^2 = 2 has a solution mod p, but x^(2^2) = 2 has no solution mod p.
18
17, 41, 97, 137, 193, 241, 313, 401, 409, 433, 449, 457, 521, 569, 641, 673, 761, 769, 809, 857, 929, 953, 977, 1009, 1129, 1297, 1321, 1361, 1409, 1489, 1657, 1697, 1873, 1993, 2017, 2081, 2137, 2153, 2161, 2297, 2377, 2417, 2521, 2609, 2617, 2633, 2713
OFFSET
1,1
COMMENTS
Complement of A014754 with regard to primes of the form 8*k+1.
These appear to be the primes p for which 4^((p-1)*n/8) mod p = (p-2)*( n mod 2)+1. For example, 4^(5*n) mod 41 = 1,40,1,40,1,40...= 39*(n mod 2)+1 and 4^(30*n) mod 241 = 1,240,1,240,1,240...= 239*(n mod 2) +1. - Gary Detlefs, Jul 06 2014
Primes p == 1 mod 8 such that 2^((p-1)/4) == -1 mod p. - Robert Israel, Jul 06 2014
A very similar sequence is A293394. - Jonas Kaiser, Nov 08 2017
LINKS
FORMULA
Primes of the form 8*k + 1 but not x^2 + 64*y^2. - Michael Somos, Mar 22 2008
a(n) ~ 8n log n. - Charles R Greathouse IV, Nov 10 2017
MAPLE
select(p -> isprime(p) and 2 &^((p-1)/4) mod p = p-1, [8*k+1$k=1..10000]); # Robert Israel, Jul 06 2014
MATHEMATICA
Select[Prime[Range[400]], Mod[#, 8] == 1 && PowerMod[2, (#-1)/4, #] == #-1 &] (* Amiram Eldar, Mar 21 2026 *)
PROG
(PARI) forprime(p=2, 2720, x=0; while(x<p&&x^2%p!=2%p, x++); if(x<p, y=0; while(y<p&&y^(2^2)%p!=2%p, y++); if(y==p, print1(p, ", "))))
(PARI) {a(n) = local(m, c, x); if( n<1, 0, c = 0; m = 1; while( c<n, m++; if( isprime(m) && m%8 == 1, x = 0; for(y=1, sqrtint( m \ 64 ), if( issquare( m - 64 * y^2, &x), break)); if( !x, c++ ))); m)} /* Michael Somos, Mar 22 2008 */
(PARI)
ok(p, r, k1, k2)={
if ( Mod(r, p)^((p-1)/gcd(k1, p-1))!=1, return(0) );
if ( Mod(r, p)^((p-1)/gcd(k2, p-1))==1, return(0) );
return(1);
}
forprime(p=2, 10^4, if (ok(p, 2, 2, 2^2), print1(p, ", ")));
/* Joerg Arndt, Sep 21 2012 */
(PARI) is(n)=n%8==1 && Mod(2, n)^(n\4)==-1 && isprime(n) \\ Charles R Greathouse IV, Nov 10 2017
(Magma) [p: p in PrimesUpTo(3000) | not exists{x: x in ResidueClassRing(p) | x^4 eq 2} and exists{x: x in ResidueClassRing(p) | x^2 eq 2}]; // Vincenzo Librandi, Sep 21 2012
KEYWORD
nonn,easy
AUTHOR
Klaus Brockhaus, Apr 29 2002
STATUS
approved