A306271 - OEIS

%I #45 Nov 07 2020 14:15:40

%S 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 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 14,51,52,8,54,55,8,8,9,14,59,26,16,12,63,9,65,66,10

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

%H Daniel Suteu, <a href="/A306271/b306271.txt">Table of n, a(n) for n = 1..10000</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Congruence_of_squares">Congruence of squares</a>

%F a(n^2) = n.

%F a(p) = p - floor(sqrt(p)), for prime p > 2.

%e 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 a:= proc(n) local k, t;

%p       for k do t:= irem(k^2, n);

%p         if issqr(t) and isqrt(t)<>k then break fi

%p       od; k

%p     end:

%p seq(a(n), n=1..100);  # _Alois P. Heinz_, Feb 01 2019

%t a[n_] := For[x = Sqrt[n]//Ceiling, True, x++, If[IntegerQ[Sqrt[PowerMod[x, 2, n]]], Return[x]]];

%t Array[a, 100] (* _Jean-François Alcover_, Nov 07 2020 *)

%o (PARI) a(n) = for(k=sqrtint(n), oo, if(issquare(k^2 % n) && sqrtint(k^2 % n) != k, return(k)));

%Y Cf. A000290, A048152, A062803, A112045, A254328, A306257.

%K nonn

%O 1,2

%A _Daniel Suteu_, Feb 01 2019