Message Boards Message Boards

0
|
7189 Views
|
1 Reply
|
1 Total Likes
View groups...
Share
Share this post:

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

Posted 10 years ago

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 10 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