MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: [Q] Help with PrimitiveRoot

  • To: mathgroup at
  • Subject: [mg14253] Re: [Q] Help with PrimitiveRoot
  • From: sguyer at (Scott A. Guyer)
  • Date: Mon, 12 Oct 1998 13:51:37 -0400
  • Organization: Virginia Tech
  • References: <6vf52q$>
  • Sender: owner-wri-mathgroup at

In article <6vf52q$dgh at>, dhf at 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}.


Scott A. Guyer
Virginia Tech

  • Prev by Date: Re: Unexpected results
  • Next by Date: Re: Unexpected results
  • Previous by thread: Re: [Q] Help with PrimitiveRoot
  • Next by thread: Add to menus?