Results 1 to 2 of 2

Math Help - Primitive Roots

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Primitive Roots

    I'm asked to find a primitive root modulo powers of odd primes. I have to write a program that calculates but I'm having a hard time coming up with an algorithm that will calculate this.

    For example, let our odd prime be 5. How would I find a primitive root of, say 5^3?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,382
    Thanks
    749

    Re: Primitive Roots

    well, you could try a brute force approach since you have φ(p^k - 1) generators.

    so you write a subroutine that calculates the order of a (mod p^k - 1), by just checking a, a^2, etc., and test if that equals p^k - 1.

    (something like:
    a = 2
    (#)n = 2
    (*)while n < p^k -1, calculate a^n (mod p^k - 1),
    (**)....while a^n (mod p^k - 1) > 1,
    ...............n-->n+1, goto (*)
    ..........else order(a) = n, goto (***)
    ....else, output (a)
    (***)a-->a+1, goto (#)

    or some such equivalent)

    it's not pretty, but it should work.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 10th 2011, 05:15 PM
  2. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 24th 2010, 01:15 PM
  3. primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 24th 2009, 12:27 PM
  4. Primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 6th 2008, 09:00 AM
  5. Help With primitive roots
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: October 28th 2007, 01:37 PM

Search Tags


/mathhelpforum @mathhelpforum