PrimitiveRoot function

Question

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

For example PrimitiveRoot[18] 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?

Answer 1

s$Version

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

PrimitiveRoot[18]

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[18]

{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],
   _?(#[[4]] === Infinity || #[[3]] == #[[4]] &)] //

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