Cancellation Law

MathematicalPhysicist · Nov 8, 2003

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:
(a+1)c-d(a+1)/a
(a+1)*(c-d)/a
now from this how can i get c-d/a or c=d (mod a)?

Hurkyl · Nov 8, 2003

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

MathematicalPhysicist · Nov 9, 2003

Originally posted by Hurkyl
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

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
m+n>=d.

Hurkyl · Nov 9, 2003

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

Or

(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.

MathematicalPhysicist · Nov 9, 2003

Originally posted by Hurkyl

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.

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.

Hurkyl · Nov 9, 2003

Which is why I said

xp + yq is an element of S if it is positive.

(added emphasis)