Re: [Q] Help with PrimitiveRoot
- To: mathgroup at smc.vnet.net
- Subject: [mg14253] Re: [Q] Help with PrimitiveRoot
- From: sguyer at NOSPAMPLEASEcs.vt.edu (Scott A. Guyer)
- Date: Mon, 12 Oct 1998 13:51:37 -0400
- Organization: Virginia Tech
- References: <6vf52q$dgh@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
In article <6vf52q$dgh at smc.vnet.net>, dhf at interport.net says...
>
> 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}
It looks like you took this definition from the Mathematica
documentation. It is a little misleading. The important caveat to
that definition is that n must be a prime power or the 2 times that
prime power. I don't think this is entirely accurate. Your example
has n = 16. Although this is 2 times a prime power, it is not
sufficient to get a single generator for the group of integers
relatively prime to 16. You will find that the number 2 and powers of
2 are very frequently exceptions to many number theory theorems.
In the example given above, {1,3,9,11} is a cyclic group of integers
relatively prime to 16 generated by 3. But the group
{1,3,5,7,9,11,13,15} is not cyclic, hence, it can have no generator.
The other cyclic subgroups include {1,5,9,13} and {1,7}.
Cheers,
--
Scott A. Guyer
Virginia Tech