A306271 a(n) is the smallest positive integer x such that x^2 mod n is a square, with x^2 >= n.
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
Keywords
Examples
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.
Links
- Daniel Suteu, Table of n, a(n) for n = 1..10000
- Wikipedia, Congruence of squares
Programs
-
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 *)
-
PARI
a(n) = for(k=sqrtint(n), oo, if(issquare(k^2 % n) && sqrtint(k^2 % n) != k, return(k)));
Formula
a(n^2) = n.
a(p) = p - floor(sqrt(p)), for prime p > 2.