Primitive Root

Author

Eric W. Weisstein
March 18, 2004

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

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

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

Code

PrimitiveRoots[p_]:=Select[Range[p-1],PrimitiveRootQ[#,p]&]
PrimitiveRootQ[g_,p_]:=MultiplicativeOrder[g,p]==EulerPhi[p]

Table of Primitive Roots

Table[{n,PrimitiveRoots[n]},{n,2,13}]//ColumnForm

Number of Primitive Roots

Table[EulerPhi[EulerPhi[n]],{n,20}]

Length/@PrimitiveRoots/@Range[20]

Primitive roots exist for the following values of n

Position[Length/@PrimitiveRoots/@Range[22],_?Positive]//Flatten

Primitive Roots of Prime Numbers

Select[Table[primitiveRoot[Prime[n]],{n,100}],Positive[#]&]

Table[PrimitiveRoot[Prime[n]],{n,100}]

Smallest Primitive Root

Table[primitiveRoot[n],{n,100}]

Select[Table[{n,primitiveRoot[n]},{n,240}],Positive[#[[2]]]&]

Select[%12,Positive[#]&]

Largest Primitive Root

Table[primitiveRoots[n][[-1]],{n,100}]

Select[%13,Positive[#]&]

Mathematica's (Not Necessarily Smallest)

v4.2

prs=Function[n,{n,PrimitiveRoot[n],LeastPrimitiveRoot[n]}]/@Select[Range[100],PrimePowerQ]

Select[prs,#[[2]]>#[[3]]&]

v5.0

prs=Function[n,{n,PrimitiveRoot[n],LeastPrimitiveRoot[n]}]/@Select[Range[100],primePowerQ]

Select[prs,#[[2]]>#[[3]]&]//TableForm

Table[PrimitiveRoot[n],{n,100}] /. PrimitiveRoot[n_]->0

Select[Table[{n,PrimitiveRoot[n],First@primitiveRoots[n]},{n,100}],#[[-1]]>0&]

Select[%,#[[2]]≠#[[3]]&]

Union[Mod[#^Range[9],10]]&/@{3,7}

Union[Mod[#^Range[17],18]]&/@{5,11}