# How to prove cancellation property of integer multiplication?

How to prove that Multiplication has a cancellation property if $\langle 0, 0 \rangle$ is not a member of the factor to be canceled.

-
What is $\langle 0,0\rangle$, and what does it mean for it to be "a member of the factor"? Multiplication of what? You have both "number theory" (suggesting either natural numbers, integers, or perhaps rationals), and "real-analysis" (suggesting real numbers) in your question. A proof of the cancellation property depends on what you are taking for granted. –  Arturo Magidin Aug 29 '11 at 1:21
@Arturo: Please see my link. I think the sentence has been taken from there. –  user9413 Aug 29 '11 at 1:23
@Chandrasekhar: Thanks. In short, we have the natural numbers, define the integers as the equivalence classes of pairs $(m,n)$ with $m,n\in\mathbb{N}$, under equivalence relation $(m,n)\sim(r,s)$ if and only if $m+s=n+r$; and are trying to prove the cancellation property of multiplication in the integers. The book uses $\langle m,n\rangle$ for the ordered pair $(m,n)$. –  Arturo Magidin Aug 29 '11 at 1:25
@chandrasekhar I mean to say, that if $a=b \ne 0$, then $b(a-b)=(a+b)(a-b)$ doesn't mean that $b=a+b$. And Yes! It's an exercise in the book SET THEORY AND LOGIC by RR STOLL. –  gaurav Aug 29 '11 at 1:30

You start with the natural numbers $\mathbb{N}$, which include $0$. The book linked to by Chandrasekhar assumes the usual properties of addition, multiplication, and order of natural numbers as part of the axiomatic set-up; these properties include cancellation for nonzero natural numbers.

Then we define an equivalence relation on $\mathbb{N}\times\mathbb{N}$ by $$(a,b)\sim (c,d) \Longleftrightarrow a+d = b+c.$$ It is not hard to establish that this is indeed an equivalence relation. We define the set $\mathbb{Z}$ to be the set $\mathbb{N}/\sim$ of equivalence classes modulo $\sim$. Let $[a,b]$ denote the equivalence class of $(a,b)$ under $\sim$.

We define addition of integers by $$[a,b]+[c,d] = [a+c,b+d].$$ This is well-defined, and has the usual properties of addition.

Then we define multiplication of integers by: $$[a,b]\times [c,d] = [ac+bd, ad+bc].$$

Since your question is about multiplication, I'll start actually proving things here.

Theorem. Multiplication is well defined. That is, if $(a,b)\sim (x,y)$ and $(c,d)\sim (v,w)$, then $(ac+bd,ad+bc) \sim (xv+yw, xw+yv)$.

Proof. First, I prove that $(ac+bd, ad+bc) \sim (xc+yd, xd+cy)$; indeed, we know that $a+y = b+x$. Multiplying by $c$, we have $ac+yc = bc+xc$. Multiplying by $d$, we get $ad+yd=bd+xd$. So $(ac+yc)+(bd+xd) = (bc+xc)+(ad+yd)$, which proves that $(ac+bd,ad+bc)\sim (xc+yd,xd+cy)$.

Next, I prove that $(xc+yd, xd+cy)\sim (xv+yw, xw+yv)$. We know $c+w=d+v$; multiplying by $x$ and by $y$, we get $xc + xw = xd+xv$ and $yc+yw = yd+yv$. Therefore, $(xc+xw)+(yd+yv) = (xd+xv) + (yc+yw)$, which is what we want. By transitivity, we get the result. $\Box$

Therefore, multiplication of integers is well defined.

Theorem. Multiplication is commutative, associative, and distributes over sums.

Proof. Simply a matter of computing. $\Box$

Theorem. If $[a,b][x,y] = [a,b][r,s]$ and $a\neq b$, then $[x,y]=[r,s]$.

Proof. $[a,b][x,y] = [ax+by, ay+bx]$; $[a,b][r,s] = [ar+bs,as+br]$. Equality means that $$ax+by+as+br = ay+bx+ar+bs.$$ We want to show that $x+s = y+r$. These are all natural numbers, so the usual properties hold.

Note that $ax+by+as+br = a(x+s) + b(y+r)$ and $ay+bx+ar+bs = a(y+r) + b(x+s)$.

If $a\lt b$, then we can write $b=a+h$ with $h\gt 0$. Then we have \begin{align*} a(x+s) + b(y+r) &= a(y+r) + b(x+s)\\ a(x+s) + a(y+r) + h(y+r) &= a(y+r) + a(x+s) + h(x+s)\\ h(y+r) &= h(x+s). \end{align*} Since $h\neq 0$, then $y+r=x+s$, as desired. If $a\gt b$, then we can write $a=b+h$ with $h\gt 0$, and a similar computation again shows that $x+s=y+r$, as desired. $\Box$

Now, note that $(0,0)\in[a,b]$ if and only if $(0,0)\sim (a,b)$, if and only if $a=b$. Therefore, in the integers (i.e., in $(\mathbb{N}\times\mathbb{N})/\sim$) we have that $[a,b][x,y] = [a,b][r,s]$ if and only if the ordered pair $(0,0)$ is not one of the elements of the equivalence class $[a,b]$.

-