cp's OEIS Frontend

A306271 a(n) is the smallest positive integer x such that x^2 mod n is a square, with x^2 >= n.

%I A306271 #45 Nov 07 2020 14:15:40
%S A306271 1,2,2,2,3,4,5,3,3,7,8,4,10,11,4,4,13,6,15,6,5,18,19,5,5,21,6,9,24,8,
%T A306271 26,6,7,29,6,6,31,32,8,7,35,10,37,16,7,40,41,7,7,10,10,19,46,12,8,9,
%U A306271 14,51,52,8,54,55,8,8,9,14,59,26,16,12,63,9,65,66,10
%N A306271 a(n) is the smallest positive integer x such that x^2 mod n is a square, with x^2 >= n.
%H A306271 Daniel Suteu, <a href="/A306271/b306271.txt">Table of n, a(n) for n = 1..10000</a>
%H A306271 Wikipedia, <a href="https://en.wikipedia.org/wiki/Congruence_of_squares">Congruence of squares</a>
%F A306271 a(n^2) = n.
%F A306271 a(p) = p - floor(sqrt(p)), for prime p > 2.
%e A306271 For n = 10, a(10) = 7, which is the smallest positive integer x such that x^2 mod n is a square and that x^2 >= n. Here 7^2 mod 10 = 9 = 3^2.
%p A306271 a:= proc(n) local k, t;
%p A306271       for k do t:= irem(k^2, n);
%p A306271         if issqr(t) and isqrt(t)<>k then break fi
%p A306271       od; k
%p A306271     end:
%p A306271 seq(a(n), n=1..100);  # _Alois P. Heinz_, Feb 01 2019
%t A306271 a[n_] := For[x = Sqrt[n]//Ceiling, True, x++, If[IntegerQ[Sqrt[PowerMod[x, 2, n]]], Return[x]]];
%t A306271 Array[a, 100] (* _Jean-François Alcover_, Nov 07 2020 *)
%o A306271 (PARI) a(n) = for(k=sqrtint(n), oo, if(issquare(k^2 % n) && sqrtint(k^2 % n) != k, return(k)));
%Y A306271 Cf. A000290, A048152, A062803, A112045, A254328, A306257.
%K A306271 nonn
%O A306271 1,2
%A A306271 _Daniel Suteu_, Feb 01 2019