1
$\begingroup$

Earlier, I submitted an erroneous proof of Euclid's Lemma which was absolutely destroyed (rightly so) by the users on this site. Many contributors to StackExchange helped me realize the fallacies in my logic, so I have done my best to reconstruct a proof that utilizes the suggestions provided to me. I am fairly new to proofs, so any constructive criticism would be greatly appreciated in this new formulation. I thank individuals for their time, and for gentle tips if any errors should exist in this new proof.

Statement S: $\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$

If either $a$ or $b$ are prime, then statement S is proved.

If neither $a$ nor $b$ are prime, then we must consider two cases.

Case 1: At least one integer, $a$ or $b$, is divisible by $p$.

This case is trivial because if at least one integer, $a$ or $b$, is divisible by $p$, then statement S is true.

Case 2: Neither $a$ nor $b$ are divisible by $p$; that is, $p \nmid a$ and $p \nmid b$

In order to prove that statement S is true, we must show that case 2 is impossible.

Since $p \nmid a$, we observe that $a$ does not contain $p$ as a factor. Since the only factors of $p$ are 1 and itself, we conclude $gcd(p,a) = 1 => a$ and $p$ are relatively prime.

Using the same reasoning, we can conclude that $gcd(b,p) = 1 => b$ and $p$ are relatively prime

If $a$ and $b$ each do not contain $p$ as a factor, then the multiple $ab$ necessarily cannot contain $p$ as a factor since no multiple of the factors of $a$ and $b$ can create a $p$.

Therefore, since $p$ is not a factor of $ab$, it must be the case that $p \nmid ab$. This is a contradiction. Thus, case 2 cannot occur.

Q.E.D.

Any thoughts?

$\endgroup$
1
  • $\begingroup$ This looks like "Euclid's lemma is true, because Euclid's lemma is true". $\endgroup$ Commented Mar 17, 2018 at 7:48

1 Answer 1

0
$\begingroup$

The statment is false: you forgot to state that $p$ is a prime number.

And the proof is wrong. When you write “If $a$ and $b$ each do not contain $p$ as a factor, then the multiple $ab$ necessarily cannot contain $p$ as a factor since no multiple of the factors of $a$ and $b$ can create a $p$.” you are stating, as if it was obvious, the very thing that you want to prove.


You can prove it as follows: if $p\nmid a$ then, since $p$ is prime, $a$ and $p$ are relatively prime and therefore there are $m,n\in\mathbb Z$ such that $pm+an=1$. So, $bpm+abn=b$. Since $p\mid bpm$ and $p\mid abn$, $p\mid b$.

$\endgroup$
2
  • $\begingroup$ How would I then show that $p$ is not a factor of $ab$? Isn't this a key insight that must be shown in order to conclude $p \nmid ab$? I mean, the only factors of $p$ are one and itself. It seems logical that if $a$ and $b$ don't have $p$ as a factor, there is no way to say $p$ is a factor of $ab$. Is there a way? I cannot think of one. $\endgroup$
    – Michael
    Commented Mar 17, 2018 at 7:57
  • $\begingroup$ @user516079 I've added a proof to my answer. Is it clear now? $\endgroup$ Commented Mar 17, 2018 at 8:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .