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

Questions
1

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?

2

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} *)