Proof that the integers have no zero divisors.

Question

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.

Answer 1

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.

Answer 2

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.