Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of the Order Divisibility Property

  1. Mar 12, 2012 #1
    The Order Divisibility Property states that if an = 1 (mod p), then the order ep(a) of a (mod p) divides n.

    How can I go about proving this?

    Additionally, if a is relatively prime to p, when does the congruence am = an (mod p) hold? Is there a proof for this as well?

    Thanks!!
     
  2. jcsd
  3. Mar 12, 2012 #2

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Hint for 1: The division algorithm says we can write ##n=qe_p(a)+r##. What can you say about r?

    Hint for 2: If a is relatively prime to p, what is ##e_p(a)##?
     
  4. Mar 13, 2012 #3
    For the first one, r must equal zero, but I'm not sure how to show that it is true.

    For the second, would the order ep(a) = p-1 ?
     
  5. Mar 13, 2012 #4
    Not really; other integer less than p-1 could do the trick. Anyway, I believe morphism was simply trying to make you think about the very definition of 'order'. And what would you need to do to this definition in order to transform it into something like the premises that you are given.
     
  6. Mar 13, 2012 #5

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    As for the first problem, the division algorithm tells us that ##0 \leq r < e_p(a)##. What can you do with this, squire636?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof of the Order Divisibility Property
Loading...