A059770 First solution of x^2 = 2 mod p for primes p such that a solution exists.

0, 3, 6, 5, 8, 17, 7, 12, 32, 9, 25, 14, 38, 51, 16, 31, 46, 13, 57, 52, 20, 15, 85, 99, 22, 60, 110, 96, 132, 66, 120, 26, 167, 19, 79, 137, 53, 97, 188, 206, 21, 30, 80, 203, 187, 91, 157, 249, 201, 34, 142, 166, 222, 194, 296, 94, 67, 36, 283, 324, 27, 102, 113, 73

Offset

1,2

Comments

Solutions mod p are represented by integers from 0 to p-1. For p > 2: If x^2 = 2 has a solution mod p, then it has exactly two solutions and their sum is p; i is a solution mod p of x^2 = 2 iff p-i is a solution mod p of x^2 = 2. No integer occurs more than once in this sequence. Moreover, no integer (except 0) occurs both in this sequence and in sequence A059771 of the second solutions (Cf. A059772).

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..5000

K. Matthews, Finding square roots mod p by Tonelli's algorithm

R. Chapman, Square roots modulo a prime

Formula

a(n) = first (least) solution of x^2 = 2 mod p, where p is the n-th prime such that x^2 = 2 mod p has a solution, i.e. p is the n-th term of A038873.

Example

a(6) = 17, since 41 is the sixth term of A038873, 17 and 24 are the solutions mod 41 of x^2 = 2 and 17 is the smaller one.

Mathematica

fQ[n_] := MemberQ[{1, 2, 7}, Mod[n, 8]]; f[n_] := PowerMod[2, 1/2, n]; f@ Select[ Prime[Range[135]], fQ] (* Robert G. Wilson v, Oct 18 2011 *)

Crossrefs

Cf. A038873, A059771, A059772.

Sequence in context: A259556 A063520 A078677 * A019690 A010620 A046128

Adjacent sequences: A059767 A059768 A059769 * A059771 A059772 A059773

Keyword

nonn

Author

Klaus Brockhaus, Feb 21 2001

Status

approved