[Date Index]
[Thread Index]
[Author Index]
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
Prev by Date:
**SUMMARY: How {{a,b,c},{1,2,3,4,5,6,7}}-->{{a,1},{b,2},{c,3},{a,4},...,{a,7},{b,1},...}?**
Next by Date:
**Re: Unexpected results**
Previous by thread:
**[Q] Help with PrimitiveRoot**
Next by thread:
**Re: [Q] Help with PrimitiveRoot**
| |