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

Homework Help: Congruence proof

  1. Sep 23, 2010 #1
    1. The problem statement, all variables and given/known data
    prove that if p is a prime number and a is any integer p|/a(p does not divide a), then the additive order of a modulo p is equal to p.


    2. Relevant equations



    3. The attempt at a solution
    I know p|/ a says a[tex]\neq[/tex]pn for an integer n.
    The additive order of a modulo n is the smallest positive solution to ax[tex]\equiv[/tex]0 mod n.
    Let p be a prime number and p|/ a.
    Then we can say (p, a)=1. That is p and a are relatively prime.
    That's as far as I got.
     
  2. jcsd
  3. Sep 23, 2010 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    ax=0 mod p means that p|ax. If p does not divide a, what can you infer?
     
  4. Sep 23, 2010 #3
    the additive order is p?
     
  5. Sep 23, 2010 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

  6. Sep 23, 2010 #5
    Since p does not divide a, there are no multiples of a that equal p. Thus, p must be the smallest additive order.
     
  7. Sep 23, 2010 #6

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    p not dividing a means no multiple of p equals a, not that no multiple of a equals p. And I don't see what that has to do with additive order anyway... 4 does not divide six, there are no multiples of 4 or 6 that give the other one, but the additive order of 4 mod 6 is three, not six.

    If p|ax and p does not divide a, and p is a prime, what must p divide? This is the defining property of prime numbers
     
  8. Sep 23, 2010 #7
    p divides x or p divides 1
     
  9. Sep 23, 2010 #8

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    p can't divide 1...

    You should be able to finish the proof now
     
  10. Sep 23, 2010 #9
    Ok I think this makes a bit more sense for em now. Thanks!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook