# Prove [(xy=0)∧(x,y∈ℤ)]→[(x=0)∨(y=0)]

I'm working through a higher algebra textbook. It has some exercises related to the positive integers and I'm stuck on this proof. Here's what I have so far:

## Attempted proof

Assume the contrary, [(xy=0)∧(x,y∈ℤ)]→¬[(x=0)∨(y=0)]→[¬(x=0)∧¬(y=0)]→[(x≠0)∧(y≠0)]

Now let x be symbolised by the pair of positive integers (a,b). Likewise, let y be symbolised by the pair of positive integers (c,d)

Pause here. I can complete the proof iff I get a proof that ab=cd→[(a=c AND b=d) OR (a=d AND b=c) OR (a=kc AND kb=d) OR (a=kd AND kb=c)] where a,b,c,d,k are positive integers and k>1. This seems obvious to me; but it seems daunting to proof it with so many variables and equipped little more than with induction and basic logic. So, if anyone can prove either the original proposition or the one I now would like I would be most grateful. I've already checked out this similar question but the only answers there require a definition for the multiplicative inverse, which isn't defined just yet. Neither is division, or subtraction for positive integers.

## Usable Concepts

Additive and multiplicative cancellation, communicative and associative laws, the distributive law, inequality; that given a+x=b for positive integers a,x,b, a< b, and that either a< b XOR a>b XOR a=b, transitive law of inequality, postulate of finite induction.

For integers, they have been defined as pairs of positive integers. An equality (a,b)=(c,d) holds IFF a+d=b+c. (a,b)+(c,d)=(a+c,b+d), (a,b)·(c,d)=(ac+bd,ad+bc). I understand that this is probably not the standard way of doing things, so feel free to avoid the notation and stick with negative numbers, but be warned that manipulations involving positive integers must not be mixed with integers.

There are other axioms but most are irrelevant. If you'd like to know whether I have a specific concept defined yet, just ask.

For the curious, the textbook is Higher Algebra for the Undergraduate 2nd Ed. Written by Marie J. Weiss and Roy Dubisch. This isn't for homework or anything, I just got a load of old textbooks from a friend and am just working through them before I leave high school.

• How is this book defining $0$? That's not a positive integer. Oct 7, 2014 at 4:32
• It's defined as a pair of positive integers such that they are equal, i.e. (a,a) Pretty much just think of (a,b) as a-b. Oct 7, 2014 at 4:34

First, your proposed solution has an error at the first step; if $(a,b)\cdot (c,d)=0$, you cannot conclude that $(a,b)\cdot (c,d)=(a,a)$, because you've already got an $a$. You should use a different variable name, e.g. $(a,b)\cdot (c,d)=(f,f)$.
Suppose $(a,b)\cdot (c,d)=0$. Then $ac+bd=ad+bc$. Suppose that $(a,b)\neq 0$. Then $a\neq b$, and presumably you have proven that the positive integers are ordered. Hence either $a>b$ or $b>a$.
First consider the case $a>b$. Then there is some positive integer $t$ with $b+t=a$. We now rewrite $ac+bd=ad+bc$ as $$(b+t)c+bd=(b+t)d+bc$$ Each side has $bc+bd$, which we cancel additively, so we conclude that $tc=td$. But now we cancel the $t$ multiplicatively and conclude $c=d$. Hence $(c,d)=0$.
I leave the case $a<b$ for you to do; it is very similar.