Cancellation Law

  • #1
MathematicalPhysicist
Gold Member
4,285
201

Main Question or Discussion Point

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)?
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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
 
  • #3
MathematicalPhysicist
Gold Member
4,285
201
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.
 
  • #4
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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.
 
  • #5
MathematicalPhysicist
Gold Member
4,285
201
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.
 
  • #6
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Which is why I said

xp + yq is an element of S if it is positive.
(added emphasis)
 

Related Threads on Cancellation Law

Replies
17
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
10
Views
4K
  • Last Post
Replies
17
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
1K
Replies
2
Views
577
  • Last Post
Replies
6
Views
2K
Replies
2
Views
3K
Replies
2
Views
2K
Top