2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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]. " $\endgroup$ – Sjoerd C. de Vries Dec 28 '14 at 16:33
  • $\begingroup$ 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[18], CoprimeQ[#, 18] && MultiplicativeOrder[#, 18] == EulerPhi[18] &] I would still like to know the answer to my original question. Thanks again! $\endgroup$ – Geoffrey Critzer Dec 28 '14 at 19:19
1
$\begingroup$
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

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.