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!

Proof of cancellation law

  1. Dec 1, 2008 #1
    1. The problem statement, all variables and given/known data
    in Zp, where a does not equal 0, that [a][x] = [a][y] is the same as [x] = [y].

    This was a question on a test I just finished. Just curious how wrong my answer is. So I sort of ignored the congruence class part. I just said:

    * [a]^-1 represents the inverse of [a] *

    [a][x] = [a][y]
    [a]^-1[a][x] = [a][y][a]^-1 (by associative law)
    [1][x] = [1][y] (by the law of inverses)
    [x] = [y] (since 1 is the identity element under multiplication in congruence classes).

    so yea... did i do anything right?

    thanks for the help in advance
     
  2. jcsd
  3. Dec 1, 2008 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    At the very least mention why you think [a]-1 should exist. (it's non-zero). In fact, this is technically correct but I suspect more detail was expected (since if you know Zp is a field, this is a useless question). Here's how you probably were supposed to do it (I left two details to fill in)

    [a][x] = [a][y] if and only if p|(ax-ay) if and only if p|a(x-y)

    p|a(x-y) implies p|a or p|(x-y) (why?)

    p does not divide a (why?)

    Hence p|(x-y) and this gives [x]=[y]

    and you can run the same thing backwards

    EDIT TO ADD: I forgot to mention I'm assuming p is prime here, as otherwise the question's wrong
     
  4. Dec 1, 2008 #3
    p|a(x-y) implies p|a or p|(x-y) (why?)
    This is true, because since p is prime, we are able to apply Euclid's lemma.

    p does not divide a (why?)
    I honestly couldn't tell you why p does not divide a.

    so... did I do anything correct at all...?
     
  5. Dec 1, 2008 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Go back and read the question carefully... what do you know about a?


    Nothing you did was wrong per se, it's just that you didn't support why there should exist a congruence class of the form [a]-1, which was probably what was expected of you (alternatively, and easier is the argument I posted).
     
  6. Dec 1, 2008 #5
     
  7. Dec 1, 2008 #6

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    By definition

    [a] = [0] if and only if p|a
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof of cancellation law
  1. Law of Sines Proof (Replies: 1)

  2. Proof of Limit Laws (Replies: 10)

Loading...