A059772 Smallest prime p such that n is a solution mod p of x^2 = 2, or 0 if no such prime exists.

0, 7, 7, 23, 17, 47, 31, 79, 0, 17, 71, 167, 97, 223, 127, 41, 23, 359, 199, 439, 241, 31, 41, 89, 337, 727, 0, 839, 449, 137, 73, 1087, 577, 1223, 647, 1367, 103, 0, 47, 73, 881, 1847, 967, 0, 151, 2207, 1151, 2399, 1249, 113, 193, 401, 0, 3023, 1567, 191, 0, 71

Offset

2,2

Comments

Solutions mod p are represented by integers from 0 to p-1. The following equivalences hold for n > 1: There is a prime p such that n is a solution mod p of x^2 = 2 iff n^2-2 has a prime factor > n; n is a solution mod p of x^2 = 2 iff p is a prime factor of n^2-2 and p > n. n^2-2 has at most one prime factor > n, consequently such a factor is the only prime p such that n is a solution mod p of x^2 = 2. For n such that n^2-2 has no prime factor > n (the zeros in the sequence), cf. A060515.

Links

Robert Israel, Table of n, a(n) for n = 2..10000

Formula

If n^2-2 has a (unique) prime factor p > n, then a(n) = p, else a(n) = 0.

Example

a(11) = 17, since 11 is a solution mod 17 of x^2 = 2 and 11 is not a solution mod p of x^2 = 2 for primes p < 17. Although 11^2 = 2 mod 7, prime 7 is excluded because 7 < 11 and 11 = 4 mod 7.

Maple

f:= proc(n) local P;
  P:= select(`>`, numtheory:-factorset(n^2-2), n);
  if P = {} then 0 else min(P) fi
end proc:
map(f, [$2..100]); # Robert Israel, Feb 23 2016

Mathematica

a[n_] := Module[{P}, P = Select[FactorInteger[n^2 - 2][[All, 1]], # > n&]; If[P == {}, 0, Min[P]]];
Table[a[n], {n, 2, 100}] (* Jean-François Alcover, Apr 10 2019, from Maple *)

Crossrefs

Cf. A038873, A059770, A059771, A060515.

Sequence in context: A062368 A283067 A284185 * A363102 A114369 A286858

Adjacent sequences: A059769 A059770 A059771 * A059773 A059774 A059775

Keyword

nonn

Author

Klaus Brockhaus, Feb 21 2001

Extensions

Offset corrected by R. J. Mathar, Aug 21 2009

Status

approved