# Proof that $\mathbb{Z}$ has no zero divisors

Everyone knows the rules of zero divisors like $$\forall \alpha,\beta\in\mathbb{R}\;:\;\alpha\cdot\beta = 0\Rightarrow\alpha=0\vee \beta=0.$$ But how can I prove it for $\mathbb{Z}$? My first try was this one: For $\alpha\cdot \beta=0$ and $\alpha\neq 0$ let $$0=\alpha^{-1}\cdot 0=\alpha^{-1}\cdot (\alpha\cdot\beta)=(\alpha^{-1}\cdot \alpha)\cdot\beta = \beta = 0\Rightarrow \beta = 0;$$ and the same for $\beta\neq 0\Rightarrow \alpha=0$, however i realized that the multiplicative inverse of a number $\alpha\in\mathbb{Z}$ is not defined in $\mathbb{Z}$ (because $(\mathbb{Z},\cdot)$ is not a multiplicative group). What now?

Furthermore the information: it's about basic multiplication and I should prove this via the basic "rules" neutrality of 0 and 1, comparability of 0 and 1, commutativity, associativity, distributivity, irreflexivity or transitivity. Group-theory should not be mentioned in the solution as out instructors don't want us to use these "advanced techniques"!

The rules (to use some from) are the following: $\forall a,b,c\in\mathbb{Z}:$

• $a+0=a,\;\;\;\; a\cdot 1=a$
• $0<1$
• $1+(-1)=0,\;\;\;\; 0-a=(-1)\cdot a$
• $a+b=a+c \Rightarrow b=c$
• $a\cdot b=a\cdot c,a\neq 0\Rightarrow b=c$
• $0 < a \Rightarrow a\neq 0$
• $a<b\wedge b<c\Rightarrow a<c$
• $a<b\rightarrow a+c<b+c$
• $a<b\wedge 0<c\Rightarrow a\cdot c<b\cdot c$
• $a<b\wedge c < 0\Rightarrow b\cdot c < a\cdot c$
-
Perhaps you can write $\alpha \cdot \beta$ as $\underbrace{\alpha + \alpha + \cdots \alpha}_{\beta \ \text{times}}=0$ and use the fact that $\alpha \neq 0$. – user9413 Aug 15 '11 at 17:28
How did you define multiplication in $\mathbb{Z}$? Did you know the properties for $\mathbb{N}$? – Arturo Magidin Aug 15 '11 at 17:33
@Christian: Without knowing how multiplication was defined, it's rather hard to say what kind of arguments would be allowable, or what is or is not considered "advanced techniques". Also, "commutativity, associativity, distributivity, irreflexivity, transitivity" of what? You really need to say (i) how you defined $\mathbb{Z}$, and (ii) how you defined the operations in $\mathbb{Z}$. – Arturo Magidin Aug 15 '11 at 18:40
@Christian: The problem is how they were defined. You cannot have defined them "as everyone knows them" and then ask for a proof of their properties, because then the proof would be "because everyone knows this is true." – Arturo Magidin Aug 15 '11 at 19:04
@Christian: Your fifth rule, $a\cdot b = a\cdot c\Rightarrow b=c$ is incorrect; you need to assume $a\neq 0$. And if you do that, then that is equivalent to no zero divisors: if $ab = 0$ and $a\neq 0$, then $ab = a0$, hence $b=0$. – Arturo Magidin Aug 15 '11 at 19:06

The rules you provide are incorrect: your fifth "rule" currently reads: $$a\cdot b = a\cdot c \Rightarrow b=c.$$ This is not a valid rule of multiplication in $\mathbb{Z}$: after all, $0\cdot 1 = 0\cdot 0$, but we do not have $1=0$.

The correct cancellation rule is: $$\Bigl(a\cdot b = a\cdot c \land a\neq 0\Bigr) \Rightarrow b=c.$$

But this is equivalent to the fact that there are no zero divisors.

Theorem. Let $R$ be a ring. Then the following are equivalent:

1. For all $a,b,c\in R$, if $a\neq 0$ and $ab=ac$, then $b=c$.
2. For all $x,y\in R$, if $xy=0$ and $x\neq 0$, then $y=0$.

Proof. $(1)\Rightarrow (2)$: Let $x$ and $y$ be such that $xy=0$ and $x\neq 0$. Then $xy=0 = x0$, so by (1) (with $a=x$, $b=y$, $c=0$) we conclude $y=0$.

$(2)\Rightarrow (1)$: Let $a,b,c\in R$ be such that $a\neq 0$ and $ab=ac$. Then $ab-ac = 0$, so $a(b-c)=0$. Since $a\neq 0$, then by (2) (with $x=a$ and $y=b-c$) we conclude that $b-c=0$, hence $b=c$. QED

-
Sorry for the confusion, but i have now understood this one. Can you explain me more detailed why do you use the term ring and not just the set of integers? – Christian Ivicevic Aug 15 '11 at 19:19
@Christian: Because this is a general result that holds in all rings, in particular in the integers. So long as you have an addition that is associative, has a $0$, and has inverses for each element, and a multiplication that is associative and distributes over the sum, the result holds. – Arturo Magidin Aug 15 '11 at 19:27
@Christian: In fact, this kind of argument can be used in more general settings. For instance, this is essentially the proof that in a vector space, if $\alpha\mathbf{v}=\mathbf{0}$ then either $\alpha=0$ or $\mathbf{v}=\mathbf{0}$. It follows because if $\alpha\mathbf{v}=\alpha\mathbf{w}$ and $\alpha\neq 0$, then multiplying by $\frac{1}{\alpha}$ shows $\mathbf{v}=\mathbf{w}$. – Arturo Magidin Aug 15 '11 at 19:46

Hint: Show that $\mathbb{Z}$ has characteristic 0 and note that 1 generates $\mathbb{Z}$ as an additive group.

-

Suppose $\alpha = 0$ then there is nothing left to prove. So suppose that $\alpha \neq 0$. Suppose for contradiction that $\beta \neq 0$. Since $\alpha\beta = 0$, and $\beta$ is non-zero it follows that either $\alpha + \alpha + ... +\alpha = 0$, or $-(\alpha + \alpha + ... +\alpha) = 0$ for some finite positive number, $\beta$, of $\alpha$'s. However, this is a contradiction since in $\mathbb{Z}$ no element can be added to itself indefinitely to reach $0$. Hence, $\beta = 0$. $\Box$

-
I find this somewhat circular; the thing that you are trying to prove here is essentially just that the characteristic of ring of integers is $0$, so using that as a justification seems insufficient. – Carl Mummert Aug 15 '11 at 18:11
@Carl I believe you are probably right, but I can't remove the answer as he accepted it, hopefully he looks back at the page – Deven Ware Aug 15 '11 at 18:15
@Carl Mummert: I often look back :-) What other ideas do you have? – Christian Ivicevic Aug 15 '11 at 18:51
@Christian Ivicevic if you have proven that "$ab = ac \implies b = c$, $a\neq 0$" then you are done your question follows trivially – Deven Ware Aug 15 '11 at 19:09

HINT $\:$ For $\rm\ h(n) = a\:n\:,\:$ $\rm\ ker\ h = 0\ \Leftrightarrow\ h\:$ is $1$ to $1\:,\:$ i.e. $\:$ non-zero-divisor $\:\Leftrightarrow\:$ cancellable.

Said more simply, specialize $\rm\:c =0\:$ in your fifth rule: $\rm\:a\ne 0,\ a\:b = a\:c\:\Rightarrow\:b=c\:.$

-

From the rules you're provided (plus a very little more), you can give a fairly snazzy induction proof:

Theorem. Suppose $a\gt 0$; then $\forall b\gt 0$, $a\times b\neq 0$.

In fact, we can prove a little more; we'll prove that $a\times b\gt 0$, and your sixth rule then implies that $a\times b\neq 0$.

1. For $b=1$, $a\times b = a\times 1 = a$ (by your first rule), and $a\gt 0$, so $a\neq 0$ (by your sixth rule).
2. Assume that $a\times b\gt 0$. Then $a\times (b+1) = (a\times b) + (a\times 1)$ (by distribution of multiplication, which isn't on your list but should be 'basic') = $(a\times b) + a$ (by the first rule). Now, $a\times b \gt 0$ (induction hypothesis) so your eighth rule gives $\bigl((a\times b) + a\bigr) \gt a$, and then the seventh rule along with the hypothesis that $a\gt 0$ lets us conclude that $\bigl((a\times b) + a\bigr) \gt 0$, so $a\times(b+1)\gt 0$; this induction step then gives the result for all $b$.

The other cases ($b\lt 0$, etc.) can be handled straightforwardly, although you'll also need the law of the excluded middle (in the form that $a\neq 0$ implies either $a\lt 0$ or $a\gt 0$ holds) to get the final result.

-

We may assume that $\alpha$ and $\beta$ are positive. Then $\alpha \beta = (\alpha \beta) \cdot 1 = 1+1+\cdots+1\space$ ($\alpha \beta$ times). Now $1>0$ and so $0<1+1<1+1+1<\cdots<1+1+\cdots+1$. So, no positive multiple of $1$ can be zero.

-