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