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$


Any thoughts?

  • $\begingroup$ If $p\not \mid b$ than $pk\ne b$ for all $k$. Not just some $k$. After ore $21 \ne 3*k$ for some $k$. (Example $k = 8$. or $k =6$ or $k = ...$ anything but $7$. So $pr \ne ab$ does not mean that $ps =ab$ for some $s$ that isn't $ak$. $\endgroup$ – fleablood Mar 16 '18 at 23:47
  • $\begingroup$ "only using basic axioms for the set of integers " what precisely are these basic axioms. Is unique prime factorization part of them? (It shouldn't be) Is that two numbers have a greatest common divisor one of them? $\endgroup$ – fleablood Mar 17 '18 at 0:07
  • $\begingroup$ Is it an axiom that all fractions have a lowest form? Is it an axiom that if $\frac ab$ is in lowest terms and $\frac ab = \frac nm$ then $n=ak; m=bk$ for some integer $k$? I'm not sure if they should be but if they are, that will get you there. $\endgroup$ – fleablood Mar 17 '18 at 0:19

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$.


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$.


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$.


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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.