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

Cancellation Law

  1. Nov 8, 2003 #1
    in mathworld the definition of this is:"If bc=bd(mod a) and (b,a)=1 (i.e., a and b are relatively prime), then c=d (mod a)".

    now lets see if i understand it relatively primes are "Two integers are relatively prime if they share no common positive factors (divisors) except 1" now let's say for the case of (3,2) or any other case we should translate it to b and a therefore (a+1,a)now lets put it the first formula like this:
    now from this how can i get c-d/a or c=d (mod a)?
  2. jcsd
  3. Nov 8, 2003 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Why are you dividing things by a?

    Anyways, the key is to use one of the properties of gcds:

    For any integers a and b:
    if gcd(m, n) = d then there exist integers u and v such that:
    d = um + vn
  4. Nov 9, 2003 #3
    im dividing by a because the definition of c=d (mod a) is (c-d)/a integer.

    now a few questions:
    1. how is this known thing about gcd gives the explanation to the c. law?
    2. how did you derive to the equation d=um+vn?
    i can see that m/d+n/d=m+n/d and that for m=-n(mod d) m-(-n)>=d
  5. Nov 9, 2003 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You really should state completely what you mean then. e.g.

    (a+1)*(c-d)/a is an integer

    or, if you prefer,

    a | (a+1)*(c-d)

    Anyways, you know that gcd(b, a) = 1. From this, we can conclude there are u and v such that:

    bu + av = 1


    (bu = 1) mod a

    This u is the mod a multiplicative inverse of b. Once you know b is invertible, the rest of the proof looks just like what you'd do in ordinary arithmetic.

    As to the proof of this gcd property, I'll leave it as a series of exercises.

    Given integers m and n not both zero, define
    S = {um + vn | u and v are integers and ua + vb > 0}
    and let d be the minimum value in S.

    Step 1:
    Prove that if p and q are elements of S, then for any integers x and y, xp + yq is an element of S if it is positive.

    Step 2:
    Prove that d divides every element of S.
    (Hint: use the division algorithm, step 1, and the fact that d is the minimum value in s)

    Step 3:
    Prove that |m| and |n| are elements of S. This implies that d divides m and d divides n.

    Step 4:
    Prove that if c is any common divisor of m and n, then c divides d.

    Conclude that d defined in this way is the greatest common divisor of m and n.
  6. Nov 9, 2003 #5
    i dont think this statement is true because if x and y are both negative and p and q are both positive then xp+yq would be negative.
  7. Nov 9, 2003 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Which is why I said

    (added emphasis)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Cancellation Law
  1. Cancelling squares (Replies: 2)

  2. Cancelling confusion (Replies: 2)

  3. Cancelling differentials (Replies: 10)