A058853 Primes p such that x^43 = 2 has a solution mod p.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277

Offset: 1

Author

Patrick De Geest, Dec 15 2000

Keywords

• nonn
• easy

Comments

Primes not of the form 43k + 1. - Charles R Greathouse IV, Aug 22 2011 [Not so! The smallest counterexample is 5419: 5419 = 43*126 + 1, but 2^43 == 2 (mod 5419), so it is here. - Jianing Song, Mar 07 2021]

Differs from A000040 - the prime 173 does not appear.

For case x^31 = 2 the first missing prime is 311 (64th term).

For case x^47 = 2 the first missing prime is 283 (61st term).

For case x^59 = 2 the first missing prime is 709 (127th term).

For case x^61 = 2 the first missing prime is 367 (73rd term).

Complement of A059243 relative to A000040. - Vincenzo Librandi, Sep 14 2012

From Jianing Song, Mar 07 2021: (Start)

It is conjectured that this sequence has density 42/43 ~ 0.976744 over all the primes.

N | # of terms among

| the first N primes

------+--------------------

10^4 | 9758

10^5 | 97681

10^6 | 976798

10^7 | 9767551

10^8 | 97674723

If the conjecture is correct, then a(n) ~ 43/42 * n log n.

In general, let p be a prime, a be an integer that is not a p-th power, then it seems that the density of prime factors of x^p - a over all the primes is 1 - 1/p. This is well-known to be correct for p = 2. (End)

The generalized conjecture above is equivalent to: let P(p,1) be the set of primes congruent to 1 modulo p, P(p,1;a) be the set of primes q congruent to 1 modulo p such that x^p == a (mod q) has a solution, where p is a prime, a is not a p-th power, then the density of P(p,1;a) over P(p,1) is 1/p. - Jianing Song, Mar 09 2021

Links

• R. J. Mathar, Table of n, a(n) for n = 1..1000
• Index entries for related sequences

Programs

Magma

[p: p in PrimesUpTo(400) | exists(t){x : x in ResidueClassRing(p) | x^43 eq 2}]; // Vincenzo Librandi Sep 14 2012

Mathematica

ok[p_]:= Reduce[Mod[x^43 - 2, p] == 0, x, Integers] =!= False; Select[Prime[Range[1000]], ok]  (* Vincenzo Librandi Sep 14 2012 *)

PARI

isA058853(p) = isprime(p) && ispower(Mod(2,p), 43) \\ Jianing Song, Mar 07 2021

Extensions

The old formula "a(n) ~ 42/41 * n log n" based on false observation from Charles R Greathouse IV, Aug 22 2011 removed by Jianing Song, Mar 07 2021