Proving Euclid's Lemma using basic axioms of Z.

Question

I'm attempting to prove Euclid's Lemma in class, and while there are many proofs available on the internet which use Bezout's Identity and greatest common divisors and the Linear Diophantine equation, my class was specifically instructed to prove Euclid's Lemma only using basic axioms for the set of integers and properties of equality. As such, I was thinking that I could present a sketch of the proof I have in mind, and I hope that I could receive some feedback as to whether it is correct or if there are any problems and how to fix them if they exist. Thanks!

Statement: $\forall a,b \in \mathbb{Z}$, If $p\mid ab$, then $p \mid a$ or $p \mid b$, where $p$ is a prime integer.

Proof: (By Contradiction)

Let $p,a,b \in \mathbb{Z}$ where $p$ is a prime integer.

Suppose that $p \mid ab$ and $p \nmid a$

In order to prove the statement, it must be shown that $p \mid b$

Assume that $p \nmid b$

If $p \nmid b$, then $pk \neq b$ for some $k \in \mathbb{Z}$

Observe that $pk \neq b => pak \neq ab$

Since $\mathbb{Z}$ is closed under multiplication and $a,k \in \mathbb{Z}$, $ak = r$ where $r \in \mathbb{Z}$

Therefore, $pr \neq ab$ which implies that $p \nmid ab$

This is a contradiction since we were given $p \mid ab$

Thus, it must be true that $p \mid b$

Q.E.D.

Any thoughts?

Answer 1

If $p\not \mid b$ then $pk \ne b$ for all $k$ not just one $k$. (For example $3*k \ne 21$ for some $k$ i.e. for $k=6$, $3*k =18 \ne 21$. And yet somehow, $3|21$.)

So if we use that $p\ne ak$ for all $k$ we can say that $pak \ne ab$ for any $k$.

We can't say $r =ak$ because we don't have any specific $k$ in mind. But we can so that $pr \ne ab$ for any $r$ *that is a multiple of $a$.

But so far it could very possibly be that $ps = ab$ for some $s$ that is not a multiple of $a$.

I think you are doomed.

FWIW it's probably not a good idea to use the double negative that $pk \ne b$ for all$k$. It's better to say: there does not exist any $k$ so that $pk = b$.

Answer 2

Unfortunately, your proof is incorrect (and unlikely to be salvagable). The first really big red flag is that you have not used the assumption of primality of $p$ anywhere!

Some specific criticisms:

• You say that if $p \nmid b$ then $b \ne kp$ for some $k \in \mathbb{Z}$; this is true regardless of any assumptions about divisibility. You should say for all $k \in \mathbb{Z}$.

• This error propogates. Showing the existence of $r \in \mathbb{Z}$ such that $pr \ne ab$ doesn't tell you anything about the divisors of $ab$.

Answer 3

Hah, that's a nice false proof. Not only did you not use the primality of $p$ anywhere, but you also nowhere use that $p\not\mid a$.

Be careful using "$\neq$". It doesn't work the same as "$=$", so avoid using $\neq$ in chain reasonings. $pr\neq ab$ says nothing about whether or not $p$ divides $ab$; take for example $p=2=a$, $b=3$ and $r=4$. Then $pr=8\neq 12=ab$, yet still $p\mid ab$.

As for your proof, I think you might want to start over. Try not to use $\neq$. I'd start out by writing what it means for $p$ to be prime as well as think about what $p\not\mid a$ means. Also; perhaps the contrapositive is easier to prove. If $p$ divides neither $a$ nor $b$, can it still divide $ab$? Why or why not?

Answer 4

An elementary proof, using only that a non-empty set of natural numbers has a smallest element (well-order of $\mathbf Z$):

Suppose $p$ doesn't divide $a$. To prove that $p$ necessarily divides $b$, consider the set: $$X=\bigl\{x\in\mathbf N^*\mid p\;\text{divides }\;xb\bigr\}.$$ This set is not empty, since it contains $a$ and $p$. Hence it has a smallest element, $x_0$.

Claim : $x_0$ divides all the elements of $X$.

Indeed, let $x$ be any element in $X$. Proceed to Euclidean division by $x_0$: we can find natural numbers $q, r\enspace(0\le r\le x_0)$ such that $x=qx_0+r$. Multiplying both sides of this relation by $b$: $$xb =qx_0b+rb\iff rb=xb-qx_0b,$$ we see that $rb$ is divisible by $p$. However, this contradicts the minimality of $x_0$, unless $r=0$. Thus, the claim is proved.

In particular, $x_0$ divides both $a$ and $p$, which belong to $X$. But as $a$ and $p$ are coprime, it implies $x_0=1$, whence $p$ divides $x_0b=b$.