A333669 The smallest nontrivial quadratic residue modulo n.

4, 3, 2, 4, 4, 4, 3, 4, 3, 2, 4, 4, 2, 4, 4, 4, 4, 3, 2, 4, 4, 3, 4, 4, 4, 4, 2, 4, 3, 2, 4, 4, 3, 4, 3, 4, 2, 4, 4, 4, 4, 2, 2, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 4, 3, 2, 4, 4, 4, 3, 4, 4, 3, 4, 2, 4, 2, 3, 4, 4, 4, 3, 2, 4, 4, 2, 3, 4, 4, 4, 4, 4

Offset: 5

Author

Peter Schorn, May 07 2020

Keywords

• nonn
• easy

Comments

The values are 2, 3 and 4. If 2 is a square modulo n (see A057126) the value is 2. Otherwise, if 3 is a square modulo n (see A057125) the value is 3. If neither 2 or 3 are a square modulo n the value is 4.

Dedicated to Urs Meyer at the occasion of his 60th birthday.

Examples

			The squares modulo 5 are 1 and 4, therefore a(5) = 4.
Modulo 6 the squares are 1, 3 and 4 which makes a(6) = 3.
a(7) = 2 since 2 == 3^2 (mod 7).
		

Links

• Robert Israel, Table of n, a(n) for n = 5..10000

Crossrefs

Cf. A057126 for the n where the value is 2 and A057125 for the n where the value is 3 if n was not in A057126.

Programs

Maple

f:= proc(n) uses numtheory; if quadres(2,n)=1 then 2 elif quadres(3,n)=1 then 3 else 4 fi end proc:
map(f, [$5..100]); # Robert Israel, Sep 15 2020

Mathematica

qrQ[m_, n_] := Module[{k}, Reduce[Mod[m-k^2, n]==0, k, Integers] =!= False];
a[n_] := If[qrQ[2, n], 2, If[qrQ[3, n], 3, 4]];
a /@ Range[5, 100] (* Jean-François Alcover, Oct 25 2020 *)

PARI

a(n) = if(issquare(Mod(2,n)),2,issquare(Mod(3,n)),3,4)