login
Primes p such that x^16 = 2 has no solution mod p, but x^8 = 2 has a solution mod p.
3

%I #24 Jun 23 2024 11:26:40

%S 1217,1249,1553,1777,2833,4049,4273,4481,4993,5297,6449,6481,6689,

%T 7121,8081,8609,9137,9281,9649,10337,10369,10433,11329,11617,11633,

%U 12241,12577,13121,13441,13633,14321,14753,15121,15569,16417,16433,16673

%N Primes p such that x^16 = 2 has no solution mod p, but x^8 = 2 has a solution mod p.

%H Vincenzo Librandi, <a href="/A059287/b059287.txt">Table of n, a(n) for n = 1..150</a>

%t Select[Prime[Range[PrimePi[20000]]], !MemberQ[PowerMod[Range[#], 16, #], Mod[2, #]] && MemberQ[PowerMod[Range[#], 8, #], Mod[2, #]]&] (* _Vincenzo Librandi_, Sep 21 2013 *)

%o (Magma) [p: p in PrimesUpTo(17000) | not exists{x: x in ResidueClassRing(p) | x^16 eq 2} and exists{x: x in ResidueClassRing(p) | x^8 eq 2}]; // _Vincenzo Librandi_, Sep 21 2012

%o (PARI) select( {is_A059287(p)=Mod(2,p)^(p\gcd(8,p-1))==1&&Mod(2,p)^(p\gcd(16,p-1))!=1}, primes(1999)) \\ Could any composite number pass this test? - _M. F. Hasler_, Jun 22 2024

%o (Python)

%o from itertools import islice

%o from sympy import is_nthpow_residue, nextprime

%o def A059287_gen(startvalue=2): # generator of terms >= startvalue

%o p = max(1,startvalue-1)

%o while (p:=nextprime(p)):

%o if is_nthpow_residue(2,8,p) and not is_nthpow_residue(2,16,p):

%o yield p

%o A059287_list = list(islice(A059287_gen(),10)) # _Chai Wah Wu_, Jun 23 2024

%Y Cf. A000040, A045315, A045316.

%Y Cf. A070184 (same with x^64 instead of x^16).

%K nonn,easy

%O 1,1

%A _Klaus Brockhaus_, Jan 25 2001