Message Boards Message Boards

GROUPS:

How does PrimitiveRoot[n] select the particular primitive root it returns?

Posted 9 years ago
6643 Views
|
1 Reply
|
1 Total Likes
|

In Mathematica 9, the function PrimitiveRoot[n] does not always return the SMALLEST primitive root of n for composite n that have a primitive root.

How does Mathematica select the particular primitive root that it does return?

POSTED BY: Geoffrey Critzer
Posted 9 years ago

I'm not sure how the primitive root is chosen, but here are some ways to find the smallest primitive root in Mathematica.

In Mathematica 10 you can simply do

First[PrimitiveRootList[n]]

In Mathematica 9 we need to define a new function

HasPrimitiveRootQ[n_Integer?Positive] := n < 8 || (OddQ[n] && PrimePowerQ[n]) || (OddQ[n/2] && PrimePowerQ[n/2])
HasPrimitiveRootQ[_] = False;

SmallestPrimitiveRoot[n_] /; HasPrimitiveRootQ[n] := With[{g = PrimitiveRoot[n], phi = EulerPhi[n]},
  Min[PowerMod[g, Select[Range[phi], CoprimeQ[#, phi]&], n]]
]

Compare:

{PrimitiveRoot[82], SmallestPrimitiveRoot[82]}
(* {47, 7} *)
POSTED BY: Greg Hurst
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract