# Proof that the integers have no zero divisors.

There is a proposition in the Tao's Analysis book in the chapter four. I cannot prove it and I almost sure that should be too easy to do.

Definition 1: For any $a,b,c,d\in \mathbb{N}$ we shall write $\langle a,b \rangle \sim \langle c,d \rangle \iff a+_{\mathbb{N}}d=b+_{\mathbb{N}}c$

Definition 2:

The sum of two integers $\langle a,b \rangle +_{\mathbb{Z}} \langle c,d \rangle$ is defined by the formula: $\langle a,b \rangle +_{\mathbb{Z}} \langle c,d \rangle:= \langle a+_{\mathbb{N}}c\,,\,b+_{\mathbb{N}}d\rangle$.

The product of two integers $\langle a,b \rangle \cdot_{\mathbb{Z}} \langle c,d \rangle:= \langle\, a\cdot_{\mathbb{N}}c+_{\mathbb{N}}b\cdot_{\mathbb{N}}d\,,\, b\cdot_{\mathbb{N}}c+_{\mathbb{N}}a\cdot_{\mathbb{N}}d\, \rangle.$

Lemma 1: Addition and multiplication are well-defined.

Proof:

Suppose that $\langle a,b\rangle,\langle a',b'\rangle,\langle c,d\rangle, \langle c',d'\rangle \in \mathbb{N}\times \mathbb{N}$ and that $\langle a,b\rangle \sim \langle a',b'\rangle$, $\langle c,d\rangle \sim \langle c',d'\rangle$.

Addition: We need to prove that $\langle a,b\rangle +_{\mathbb{Z}} \langle c,d\rangle \sim \langle a',b'\rangle +_{\mathbb{Z}} \langle c,d\rangle$.

$\langle a,b\rangle +_{\mathbb{Z}} \langle c,d\rangle \sim \langle a+_{\mathbb{N}}c\,,\,b+_{\mathbb{N}}d \rangle$ and $\langle a',b'\rangle +_{\mathbb{Z}} \langle c,d\rangle \sim \langle a'+_{\mathbb{N}}c\,,\,b'+_{\mathbb{N}}d \rangle$. Thus we need to show that $a+_{\mathbb{N}}c+_{\mathbb{N}}b'+_{\mathbb{N}}d = b+_{\mathbb{N}}d+_{\mathbb{N}}a'+_{\mathbb{N}}c$. But since $\langle a,b\rangle \sim \langle a',b'\rangle$, i.e, $a+_{\mathbb{N}}b'=a'+_{\mathbb{N}}b$ and so by adding $c+_{\mathbb{N}}d$ we obtain the claim.

Product: Similarly we need to prove that $\langle a,b\rangle \cdot_{\mathbb{Z}} \langle c,d\rangle \sim \langle a',b'\rangle \cdot_{\mathbb{Z}} \langle c,d\rangle$.

$\langle a,b\rangle \cdot_{\mathbb{Z}} \langle c,d\rangle \sim \langle\, a\cdot_{\mathbb{N}}c+_{\mathbb{N}}b\cdot_{\mathbb{N}}d\,,\, b\cdot_{\mathbb{N}}c+_{\mathbb{N}}a\cdot_{\mathbb{N}}d\, \rangle$ and $\langle a',b'\rangle \cdot_{\mathbb{Z}} \langle c,d\rangle \sim \langle\, a'\cdot_{\mathbb{N}}c+_{\mathbb{N}}b'\cdot_{\mathbb{N}}d\,,\, b'\cdot_{\mathbb{N}}c+_{\mathbb{N}}a'\cdot_{\mathbb{N}}d\, \rangle$

Then we need to show that:

$a\cdot_{\mathbb{N}}c+_{\mathbb{N}}b\cdot_{\mathbb{N}}d+_{\mathbb{N}}b'\cdot_{\mathbb{N}}c+_{\mathbb{N}}a'\cdot_{\mathbb{N}}d=a'\cdot_{\mathbb{N}}c+_{\mathbb{N}}b'\cdot_{\mathbb{N}}d+_{\mathbb{N}}b\cdot_{\mathbb{N}}c+_{\mathbb{N}}a\cdot_{\mathbb{N}}d$ $\:\:\:\:\;\;\,c\cdot_{\mathbb{N}} \left( a+_{\mathbb{N}} b'\right)+_{\mathbb{N}} d\cdot_{\mathbb{N}} \left(a'+_{\mathbb{N}} b \right)=c\cdot_{\mathbb{N}} \left( a'+_{\mathbb{N}} b\right)+_{\mathbb{N}} d\cdot_{\mathbb{N}} \left(a+_{\mathbb{N}} b' \right)$

But since $a+_{\mathbb{N}}b'=a'+_{\mathbb{N}}b$ clearly LHS =RHS. The other two identities can be proved with symmetric arguments. $\,\,\;\square$

Definition 3: Given a natural number $n$ the corresponding integer is $n_{\mathbb{Z}}$ defined by the formula

$n_{\mathbb{Z}}:=\langle\, n,0\,\rangle$

(For simplicity let's use "$+$" for"$+_{\mathbb{N}}$" and "$\cdot$" for "$\cdot_{\mathbb{N}}$" and $=_{\mathbb{Z}}$ for $\sim$.

Proposition: Let $x$ and $y$ be integers such that $x \cdot_{\mathbb{Z}} y =_{\mathbb{Z}}0_{\mathbb{Z}}.$ Then either $x=_{\mathbb{Z}}0_{\mathbb{Z}}$ or $y=_{\mathbb{Z}}0_{\mathbb{Z}}$ or both.

Proof: For the sake of the contradiction suppose that $x\not=_{\mathbb{Z}}0_{\mathbb{Z}}$ and $y\not=_{\mathbb{Z}}0_{\mathbb{Z}}$. Let $x$ be the ordered pair $\langle a,b \rangle$ and $y$ be $\langle c,d \rangle$, where $a,b,c,d\in \mathbb{N}$.

Claim 1: $\langle e,f \rangle \not=_{\mathbb{Z}}0_{\mathbb{Z}}\iff e\not=f$

Proof of the Claim 1:

($\Rightarrow$) Suppose $e=f$. Clearly $\,e+0=f+0$ and so $\langle e,f \rangle =_{\mathbb{Z}} \langle\, 0,0\,\rangle =_{\mathbb{Z}}0_{\mathbb{Z}}$.

($\Leftarrow$) Now suppose $\langle e,f \rangle =_{\mathbb{Z}}0_{\mathbb{Z}}$. So $\,e+0=f+0$ and then $\,e=f$ as desired. $\,\,\square$

Then by claim 1, $a\not=b$ and $c\not=d$.

$\langle a,b \rangle \cdot_{\mathbb{Z}} \langle\, c,d \rangle = \langle a\cdot c+b\cdot d\,,\,b\cdot c+a\cdot d \,\rangle = 0_{\mathbb{Z}}$

So, $a\cdot c+b\cdot d = b\cdot c+a\cdot d$

And here is where I'm stuck.

I thought that maybe I could use the the trichotomy of ordered for natural numbers and analyze that each case entails a contradiction but it is really a mess. So, my question is: what do you think is the clever way to do that?

Really would appreciate a help. Thanks.

• Subtract, that gives you $(a-b)\cdot (c-d) = 0$. – Daniel Fischer Aug 22 '13 at 19:16
• @DanielFischer You can't subtract in the natural numbers! Or if you do, you don't get that $(a-b)=0$ only if $a=b$. – Thomas Andrews Aug 22 '13 at 19:17
• it's worth asking for what $x,y$ is $\langle x,y\rangle\sim 0_{\mathbb Z}$ first... @JoseAntonio – Thomas Andrews Aug 22 '13 at 19:19
• @ThomasAndrews Duh. Okay, case analysis. If $a > b$ and $c > d$, else ... – Daniel Fischer Aug 22 '13 at 19:19
• Yeah, even then, you need to be sure that subtraction has been defined in his natural numbers - it greatly depends on the order of the book's arguments. @DanielFischer – Thomas Andrews Aug 22 '13 at 19:20

Suppose $\langle a,b \rangle \cdot \langle c,d \rangle = 0_\mathbb{Z}$ and $\langle a,b\rangle \neq 0_\mathbb{Z}$. We prove that $\langle c , d \rangle = 0_\mathbb{Z}$.

So we have $ac + bd = ad + bc$ and $a \neq b$ and we want to show that $c=d$.

Since we are working on the Natural numbers, we can't use subtraction, which would make this easy. But we can work around this limitation by using the definition of the $<$ relation on $\mathbb{N}$.

Case 1: $a>b$

Then $a = b+k$ for some $k\in \mathbb{N}$, $k \neq 0$.

So $(b+k) c + bd = (b+k) d + bc$.

$\Rightarrow b(c+d) + kc = b(c+d) + kd$

$\Rightarrow kc = kd$

$\Rightarrow c=d$.

Here we used in the last two steps that terms and factors can be cancelled from both sides of an equation. You might have already proved that or you can prove it with induction.

Case 2: $a<b$

similar to case 1.

• We already proved that, the cancellation law for addition in the chapter 1. Thanks. Let me work with that...:) – Jose Antonio Aug 22 '13 at 19:43
• That seems to be too easy. Thanks :) – Jose Antonio Aug 22 '13 at 20:24

Hint

First prove by induction that for any $\langle a,b\rangle$ there is an $n\in\mathbb N$ so that $\langle a,b\rangle\sim \langle n,0\rangle$ or $\langle a,b\rangle\sim\langle 0,n\rangle$. Start with $\langle a,0\rangle$ and proceed by induction on $b$.

I presume you've proven that $\cdot_{\mathbb Z}$ is well-defined? That's actually a much harder proof, on some level.

This makes your cases far more clear.

• Actually, I don't like this answer, because this might be being use as a Corollary to prove $\cdot_Z$ is well-defined. It does say $=0$ rather than $\sim 0$, so it sort of implies that we are talking as if it is already well-defined, but it is not clear. – Thomas Andrews Aug 22 '13 at 19:43
• I'm not sure if I understand your comment. Surely it should be proved that multiplication is well defined before anything else about multiplication (such as non-existance of zero divisors) is proved. – Brusko651 Aug 22 '13 at 19:48
• I agree that the notation implies it is proven to be well-defined. But an equivalent version of $xy\sim 0$ implies $x\sim 0$ or $y\sim 0$ could be a corollary for well-defined-ness. @Brusko651 – Thomas Andrews Aug 22 '13 at 19:49
• @Thomas: Yes I've worked in that also, I mean in which addition and multiplication are well-defined and not seems to be too hard, so maybe I'm wrong with something – Jose Antonio Aug 22 '13 at 19:52
• Let me edit my original post to put my proof or well-definiteness of the operation $\cdot_{\mathbb{Z}}$ and ${+_{\mathbb{Z}}}$ – Jose Antonio Aug 22 '13 at 19:57

I'm working through this on my own right now, so I'm aware of exactly what we have proven already. Here's my solution. It might be longwinded, but I'm trying to be thorough.

For integers $a$ and $b$, first we prove the statement "If $ab=0$ then $a=0$ or $b=0$":

Given $ab=0$, suppose, for contradiction, that $a$ and $b$ are both nonzero. Then there are three possibilities: (i) $a$ is positive, $b$ is positive; (ii) $a$ is negative, $b$ is negative; (iii) one of $a$ or $b$ is positive and one is negative (without loss of generality, say $a$ is positive and $b$ is negative). In each case, the product is nonzero, a contradiction.

In case (i), both $a$ and $b$ are natural numbers, so we use the result that a product of positive natural numbers is nonzero, Lemma 2.3.3.

In case (ii), $a = 0-c$ for some positive natural number $c$, and $b=0-d$ for some positive natural number $d$. So

$ab=(0-c)(0-d)=(0*0+cd)-(0d+0c)=cd-0=cd$

using Definition 4.1.2 for the second equality. So $ab=cd$, a product of positive natural numbers.

In case (iii), $b=0-d$ for some positive natural number $d$. So

$ab=(a-0)(0-d)=(0a+0d)-(ad+0*0)=0-ad=-(ad)$

where $ad$ is the product of positive natural numbers, therefore a positive natural number. By Lemma 4.1.5, the negation of a positive natural number is nonzero.

Now we prove the converse, "If $a=0$ or $b=0$ then $ab=0$":

Suppose, without loss of generality, that $a=0$. Then if $b$ is zero or positive, use the result for natural numbers. If $b$ is negative, $b=0-d$ for some positive natural number $d$. Then

$ab=(0-0)(0-d)=(0*0+0*d)-(0*d+0*0)=0-0=0$.