A059770 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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.