Results 1 to 2 of 2

Math Help - order of primitive roots

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    46

    order of primitive roots

    let m be a positive integer and let a be an integer with (a,m)=1.
    (a) Prove that if Ordm(a)=xy (with x and y positive integers), then ordm(a^x)=y
    (b) prove that if ordm(a)=m-1, then m is a prime number.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by mndi1105 View Post
    let m be a positive integer and let a be an integer with (a,m)=1.
    (a) Prove that if Ordm(a)=xy (with x and y positive integers), then ordm(a^x)=y
    Because (a^x)^y = a^{xy} \equiv 1(\bmod m). Now if k<y so that (a^x)^k \equiv 1 then it means a^{kx}\equiv 1(\bmod m) and kx < xy but xy is order of a. This is a contradiction. Thus the order of a^x must be y

    (b) prove that if ordm(a)=m-1, then m is a prime number.
    That is because \text{ord}(a) =m-1 \leq \phi(m) \leq m - 1.
    The inequalities force \phi(m) = m-1.
    This happens if and only if m is prime.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Order of integers and primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 31st 2010, 05:43 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: 1
    Last Post: May 14th 2009, 04:14 AM
  4. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 17th 2008, 08:09 PM
  5. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 15th 2008, 06:58 PM

Search Tags


/mathhelpforum @mathhelpforum