login
A306271
a(n) is the smallest positive integer x such that x^2 mod n is a square, with x^2 >= n.
3
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, 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, 14, 51, 52, 8, 54, 55, 8, 8, 9, 14, 59, 26, 16, 12, 63, 9, 65, 66, 10
OFFSET
1,2
FORMULA
a(n^2) = n.
a(p) = p - floor(sqrt(p)), for prime p > 2.
EXAMPLE
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.
MAPLE
a:= proc(n) local k, t;
for k do t:= irem(k^2, n);
if issqr(t) and isqrt(t)<>k then break fi
od; k
end:
seq(a(n), n=1..100); # Alois P. Heinz, Feb 01 2019
MATHEMATICA
a[n_] := For[x = Sqrt[n]//Ceiling, True, x++, If[IntegerQ[Sqrt[PowerMod[x, 2, n]]], Return[x]]];
Array[a, 100] (* Jean-François Alcover, Nov 07 2020 *)
PROG
(PARI) a(n) = for(k=sqrtint(n), oo, if(issquare(k^2 % n) && sqrtint(k^2 % n) != k, return(k)));
CROSSREFS
KEYWORD
nonn
AUTHOR
Daniel Suteu, Feb 01 2019
STATUS
approved