cp's OEIS Frontend

A070179 Primes p such that x^2 = 2 has a solution mod p, but x^(2^2) = 2 has no solution mod p.

%I A070179 #47 Sep 08 2022 08:45:05
%S A070179 17,41,97,137,193,241,313,401,409,433,449,457,521,569,641,673,761,769,
%T A070179 809,857,929,953,977,1009,1129,1297,1321,1361,1409,1489,1657,1697,
%U A070179 1873,1993,2017,2081,2137,2153,2161,2297,2377,2417,2521,2609,2617,2633,2713
%N A070179 Primes p such that x^2 = 2 has a solution mod p, but x^(2^2) = 2 has no solution mod p.
%C A070179 Complement of A014754 with regard to primes of the form 8*k+1.
%C A070179 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
%C A070179 Primes p == 1 mod 8 such that 2^((p-1)/4) == -1 mod p. - _Robert Israel_, Jul 06 2014
%C A070179 A very similar sequence is A293394. - _Jonas Kaiser_, Nov 08 2017
%H A070179 Bruno Berselli, <a href="/A070179/b070179.txt">Table of n, a(n) for n = 1..1000</a>
%F A070179 Primes of the form 8*k + 1 but not x^2 + 64*y^2. - _Michael Somos_, Mar 22 2008
%F A070179 a(n) ~ 8n log n. - _Charles R Greathouse IV_, Nov 10 2017
%p A070179 select(p -> isprime(p) and 2 &^((p-1)/4) mod p = p-1, [8*k+1$k=1..10000]); # _Robert Israel_, Jul 06 2014
%o A070179 (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,","))))
%o A070179 (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 */
%o A070179 (PARI)
%o A070179 ok(p, r, k1, k2)={
%o A070179 if ( Mod(r,p)^((p-1)/gcd(k1,p-1))!=1, return(0) );
%o A070179 if ( Mod(r,p)^((p-1)/gcd(k2,p-1))==1, return(0) );
%o A070179 return(1);
%o A070179 }
%o A070179 forprime(p=2,10^4, if (ok(p,2,2,2^2),print1(p,", ")));
%o A070179 /* _Joerg Arndt_, Sep 21 2012 */
%o A070179 (PARI) is(n)=n%8==1 && Mod(2,n)^(n\4)==-1 && isprime(n) \\ _Charles R Greathouse IV_, Nov 10 2017
%o A070179 (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
%Y A070179 Cf. A038873, A040098, A040100, A059667, A070180-A070188, A014754.
%K A070179 nonn,easy
%O A070179 1,1
%A A070179 _Klaus Brockhaus_, Apr 29 2002