Services & ResourcesWolfram ForumsMathGroup Archive

[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

• References:
  • [Q] Help with PrimitiveRoot
    • From: "David H. Friedman" <dhf@interport.net>