

A059770


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


3



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 p1. 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 pi 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 nth prime such that x^2 = 2 mod p has a solution, i.e. p is the nth 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



