PrimitiveRoot function

The function PrimitiveRoot[n] claims to return the smallest primitive root of n. I believe this is not true.

For example PrimitiveRoot returns 11, yet 5 is the smallest primitive root of 18.

How does Mathematica select the particular primitive root that it returns under this function?

• That may be because 18 is a composite number. Mathworld states: "A primitive root of a number n (but not necessarily the smallest primitive root for composite n) can be computed in Mathematica using PrimitiveRoot[n]. " – Sjoerd C. de Vries Dec 28 '14 at 16:33
• Thanks! I have Mathematica 9. There does not seem to be a function PrimitiveRootList. Is this function "new in 10"? I can get a list of primitive roots with: Select[Range, CoprimeQ[#, 18] && MultiplicativeOrder[#, 18] == EulerPhi &] I would still like to know the answer to my original question. Thanks again! – Geoffrey Critzer Dec 28 '14 at 19:19

s\$Version

"10.0 for Mac OS X x86 (64-bit) (December 4, 2014)"

PrimitiveRoot

11

Although the documentation for PrimitiveRoot states "PrimitiveRoot[n] gives the smallest primitive root of n"; as @Sjoerd pointed out in the comments, MathWorld states: "A primitive root of a number n (but not necessarily the smallest primitive root for composite n) can be computed in Mathematica using PrimitiveRoot[n]. " Consequently, at a minimum there is a documentation error.

However, note that

PrimitiveRootList

{5, 11}

Consequently, a more robust method of finding the "smallest primitive root" would be Min[PrimitiveRootList[n]] (note that PrimitiveRootList is new to version 10).

Examples,

DeleteCases[
{#, CompositeQ[#], PrimitiveRoot[#],
Min[PrimitiveRootList[#]]} & /@ Range[2, 200],
_?(#[] === Infinity || #[] == #[] &)] //

Prepend[#, {"n", "CompositeQ", "PrimitiveRoot[n]", "Minimum"}] & //
Grid 