Quadratic Nonresidue

Author

Eric W. Weisstein
April 16, 2005

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

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

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

Enumeration

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

nonres=MapIndexed[Complement[Range[#2[[1]]-1],#1]&,res,{1}];

Take[nonres,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}&,nonres]],1]]]],PixelConstrained->True,ImageSize->400]
]

Flatten[Take[nonres,20]]

Numbers of Quadratic Residues

Length/@nonres

<<Utilities`Plot`

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

Smallest Quadratic Nonresidues

sm=First/@Drop[nonres,2]

{#,Flatten[Position[sm,#]]+2}&/@Union[sm]//ColumnForm

Flatten[Position[sm,2]]+2

Plot[3/2Log[n]^2,{n,.1,10},PlotStyle->Red]

Thread[sm<Table[3/2Log[n]^2,{n,Length[sm]}]]

<<Utilities`Plot`

Show[PixelPerfect[NaryPlot[First/@nonres],BlockSize->2]]