Proof of Euclid's Lemma through contradiction

Question

I tried to prove Euclid's Lemma. Please tell me if it's correct, I'm new to proofs.

Euclid's Lemma: Let $p$ be a prime number and $a$ and $b$ be natural numbers greater than 1, then if $p|ab$ we know $p|a$ or $p|b$

I rewrote this as: $[p$ prime $\land$ $\forall a,b \in \mathbb{N}, a,b \gt 1] \Rightarrow [ p|ab \Rightarrow (p|a \lor p|b)]$

Proof by contradiction.

Suppose the antecedent is true and the consequence is false. That is $[p|ab \land p|a \land p|b] (*)$ is true.

Then $b=pc$ and $a=pd$ and $ab=p^2cd$. In this case $cd$ must also necessarily be divisible by $p$ since $p$ is prime. In this case $a$ and $b$ can only be multiples of $p$ for $(*)$ to hold true. But this is in contradiction with the antecedent that $\forall a,b \in \mathbb{N}, a,b \gt 1$.

because p is prime and the only divisors of a prime number is 1 or itself — Strîmtu Gheorghe, May 04 '17 at 16:07
Could we not have $b = p$ and $a = p$ and then $c = d = 1$. In which case $p \nmid cd$. — Sean Haight, May 04 '17 at 16:12
if $c=d=1$ it still holds true that there is contradiction, I guess, as I said I'm new to this — Strîmtu Gheorghe, May 04 '17 at 16:17

score 0 · Answer 1 · answered Aug 17 '18 at 17:49

I'll prove this lemma by contradiction for $\forall a,b \in \mathbb N$ Suppose the claim is wrong, then:(we negate lemma)
if we rewrite implication $x \to y\ as\ \neg x \lor y $, then its negation would be: $x \land \neg y$
(2)You should negate the whole statement at once
Negation of original claim is:
$$\exists prime\ p: \exists a,b \in \mathbb N: p|ab \land \neg(p|a \lor p|b)$$ $$\exists prime\ p: \exists a,b \in \mathbb N: p|ab \land (p \nmid a) \land (p \nmid b)$$ (3)now we have to get the contradiction combining all the constituent parts of the line above, and everything what had led us to that line above.
Now we'll use the division theorem and get a contradiction.
$p \nmid b$ means $b=n_1p+r_1, 1 \le r_1 <p$
same for $p \nmid a$:
$p \nmid a$ means $a=n_2p+r_2, 1 \le r_2 <p$
now $ab = (n_2p+r_2)(n_1p+r_1)$
$p|ab$ so $ab=n_3p$, combine this with prev line:
$ab = (n_2p+r_2)(n_1p+r_1) = n_3p$
because $r_1 <p$ and $r_2 < p$, there's no way we get multiple of p to the left$\square$

Proof of Euclid's Lemma through contradiction

1 Answers1