cp's OEIS Frontend

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

%I A059770 #13 Sep 22 2013 08:11:51
%S A059770 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,
%T A059770 60,110,96,132,66,120,26,167,19,79,137,53,97,188,206,21,30,80,203,187,
%U A059770 91,157,249,201,34,142,166,222,194,296,94,67,36,283,324,27,102,113,73
%N A059770 First solution of x^2 = 2 mod p for primes p such that a solution exists.
%C A059770 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).
%H A059770 Vincenzo Librandi, <a href="/A059770/b059770.txt">Table of n, a(n) for n = 1..5000</a>
%H A059770 K. Matthews, <a href="http://www.numbertheory.org/php/tonelli.html">Finding square roots mod p by Tonelli's algorithm</a>
%H A059770 R. Chapman, <a href="http://www.maths.ex.ac.uk/~rjc/courses/nt03/sqrt.pdf">Square roots modulo a prime</a>
%F A059770 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.
%e A059770 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.
%t A059770 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 *)
%Y A059770 Cf. A038873, A059771, A059772.
%K A059770 nonn
%O A059770 1,2
%A A059770 _Klaus Brockhaus_, Feb 21 2001