       [Re: [Q] Help with PrimitiveRoot]

• To: mathgroup at smc.vnet.net
• Subject: [mg14315] [Re: [mg14213] [Q] Help with PrimitiveRoot]
• From: "Martin W. Mak" <mwmak at ix.netcom.com>
• Date: Tue, 13 Oct 1998 01:21:29 -0400
• Organization: Harmonic Systems
• 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 = 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 = 1;
pr = 2;
pr = 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

```

• Prev by Date: Mathmatica Problem...
• Next by Date: Mathematica 2.0.3 on PowerPC?
• Previous by thread: Re: Mathmatica Problem...
• Next by thread: Mathematica 2.0.3 on PowerPC?