Quadratic Residue

Author

Eric W. Weisstein
August 29, 2005

This notebook downloaded from http://mathworld.wolfram.com/notebooks/NumberTheory/QuadraticResidue.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/QuadraticResidue.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Enumeration

Strangl's Definition

Take[res=Table[Select[Union@Mod[Range[n]^2,n],(GCD[#,n]==1&)],{n,200}],20]

Flatten[Rest[Take[res,10]]]

Length/@res

s[n_]:=Length[Union[Mod[Range[n]^2,n]]]
q[n_]:=Count[Union@Mod[Range[n]^2,n],_?(GCD[#,n]==1&)]

pns=Flatten[Outer[List,Prime[Range[2,5]],Range[3,5]],1]

q((p^n))==s((p^n))-s((p^(n-2)))

q/@(Power@@@pns)

s/@(Power@@@pns)-s/@(Power[#1,#2-2]&@@@pns)

List of Residues

res=DeleteCases[Union/@Table[Mod[Range[n-1]^2,n],{n,200}],0,2];

Take[res,20]

With[{n=200},
array=Table[0,{n},{n}];
ArrayPlot[Reverse[Transpose[ReplacePart[array,1,Flatten[Transpose/@Rest[MapIndexed[{Table[#2[[1]],{Length[#1]}],#1}&,res]],1]]]],PixelConstrained->True,ImageSize->400]
]

Flatten[res]

Numbers of Quadratic Residues

Length/@res

<<Utilities`Plot`

IntegerListPlot[Length/@res,AxesLabel->TraditionalForm/@{n,L[n]},ImageSize->400]

Largest Quadratic Residues

Last/@Rest[res]

<<Utilities`Plot`

Show[PixelPerfect[NaryPlot[Last/@DeleteCases[Union/@Table[Mod[Range[n-1]^2,n],{n,2,256}],0,2]],BlockSize->2]]