Re: [Q] Help with PrimitiveRoot

*To*: mathgroup at smc.vnet.net*Subject*: [mg14297] Re: [mg14213] [Q] Help with PrimitiveRoot*From*: "Martin W. Mak" <mwmak at ix.netcom.com>*Date*: Tue, 13 Oct 1998 01:21:15 -0400*Organization*: Harmonic Systems*References*: <199810070700.DAA13644@smc.vnet.net.>*Sender*: owner-wri-mathgroup at wolfram.com

David H. Friedman wrote: > PrimitiveRoot[n] in NumberTheory`NumberTheoryFunctions` is supposed to > return the cyclic generator of the group of integers relatively prime > to n under multiplication mod n. PrimitiveRoot[16] = 3. The orbit of > 3 is {1,3,9,11}, but I thought the group was {1,3,5,7,9,11,13,15} > > I'm sure I'm just misunderstanding a definition... I'm a hobbyist just > starting to learn some number theory (if it matters, I'm using > Mathematica 3.0.1.1 under NT.) > > Thanks! > > David H. Friedman > dhf at interport.net David, You're correct, the orbit of 3 Modulo 16 is {1,3,9,11} and the reduced residue group Mod 16 being {1,3,5,7,9,11,13,15}. There is NO Primitive Root of 16, or of any n such that Mod[n,4] = 0. One can show that: The only positive integers that have primitive roots are 1, 2, 4 and integers of the form p^k and 2p^k with p an odd prime and k a positive integer. As it turns out there is bug in the package NumberTheoryFunctions as delivered with Mathematica. I sent WRI a fix to this last June and as far as I know they have not updated the package. Attached is the updated version of PrimitiveRoots. PrimitiveRoot[p_Integer] := Module[{res}, res /; NumberQ[ res = pr[p] ] ]; pr[2] = 1; pr[3] = 2; pr[4] = 3; pr[n_]:=$Failed /; Mod[n,4]==0; pr[n_]:= Module[{n2, res}, n2 = Quotient[n,2]; res = pr[n2]; If[SameQ[res,$Failed], $Failed, If[OddQ[res], res, res + n2] ] ] /; Mod[n, 4] == 2; pr[p_?PrimeQ] := Module[{g, flist}, g = 2; flist = (p-1)/Map[ First, FactorInteger[p-1] ]; While[JacobiSymbol[g, p] == 1 || Scan[If[PowerMod[g, #1, p] == 1, Return[True]]&, flist], g++ ]; g ]; pr[n_] := Module[{q, fi, g}, fi = FactorInteger[n]; If[ Length[fi] > 1, Return[$Failed]]; q = fi[[1,1]]; g = pr[q]; If[PowerMod[g, q - 1, q^2] == 1, g += q]; g ] /; GCD[PowerMod[2, n, n] - 2, n] > 1; Best Regards, Martin

**References**:**[Q] Help with PrimitiveRoot***From:*"David H. Friedman" <dhf@interport.net>