1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Show that the e = order of a modulo m is equal to psi(m)

  1. Apr 3, 2012 #1
    1. The problem statement, all variables and given/known data
    http://i44.tinypic.com/33z5js3.jpg

    It is part b


    2. Relevant equations
    ae = 1 (mod m)

    a(psi(m)) = 1 (mod m)

    eu - psi(m)v = gcd(e, psi(m)) = g

    3. The attempt at a solution

    I know that eu = g + psi(m)v

    So then a(eu) = ag + psi(m)= ag*apsi(m) = ag (mod m) from the above relation.

    Also aeu = 1u = 1 mod(m)

    So then we know ag = 1 mod(m) . Because g divides e , g≤e . and because e is the smallest possible number s.t ae = 1 (mod m) e≤g so g =e.

    I am having trouble then showing that g =psi(m) can someone help me.
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Apr 3, 2012 #2
    Well, from where you are, you could try to prove that [itex]e[/itex] divides [itex]g[/itex], but I wouldn't do it (and don't know if it can be done.)

    Use the division algorithm to note that you can write [itex]phi(m) = eq + r[/itex] where [itex]0 \leq r < e[/itex] and show that [itex]r[/itex] must be zero.
     
  4. Apr 4, 2012 #3
    Ahh I see! Thank you for your help.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Show that the e = order of a modulo m is equal to psi(m)
  1. Congruence modulo m (Replies: 1)

Loading...