I am stuck in understanding the backward proof in Euclid's lemma, namely:

If $m\ge 2$ is an integer such that $m|ab$ always implies $m|a$ or $m|b$, then $m$ is a prime.

The usual proof uses the contrapositive, and in the book words is

We prove the contrapositive: if m is composite, then there is a product ab divisible by m, yet neither factor is divisible by m. Since m is composite, m = ab, where a < m and b < m. Thus, m divides ab, but m divides neither factor (if m | a, then m ≤ a).

My problem is in the following example, if $a=1$ and $b$ is not prime, then $m$ still divides the product $ab$ and divides $b$, which cannot happen since we pick that $m$ is composite. In other words, the proof states that if $m$ is composite then $m$ neither divides $a$, nor $b$.

Just for reference, I give the definition that the book has on composite numbers:

An integer is called composite if it is not a prime.

Where I screwed it?

  • 1
    $\begingroup$ The proof assumes that $m$ is composite so $m = ab$ is a nontrivial factorization, so $a,b\neq 1.\ $ You should *carefully* verify the proof, e.g. $\,m\mid a\iff b\mid 1,\,$ and $\,m\mid b\iff a\mid 1\ \ $ $\endgroup$ – Bill Dubuque Jul 25 '17 at 17:21
  • $\begingroup$ The problem is the "always". It's clearly not true that $m$ composite means that $m\,|\,ab$ never means that $m$ divides one of $a,b$. Just that we can find an example. For example, if $m=6$ then taking $a=2,b=3$ works. Similarly, if $m=ab$ with $a,b>1$ then we get a counterexample. $\endgroup$ – lulu Jul 25 '17 at 17:22
  • 1
    $\begingroup$ Could you write down the exact contrapositive you're trying to prove? $\endgroup$ – Arthur Jul 25 '17 at 17:23
  • 1
    $\begingroup$ To stress, the statement "if $m$ is composite then $m$ neither divides $a$ not $b$" is obviously false in general. But we do not need it to be true. All we need is a single instance where $m$ divides $ab$ but it does not divide either $a$ or $b$. $\endgroup$ – lulu Jul 25 '17 at 17:24
  • $\begingroup$ @BillDubuque That's what I tought, but I was confused because maths book tend to be very specific in what they say. The fact that it doesn't say it explicitly always makes me uncomfortable, and I have to ask to be completely sure. $\endgroup$ – user2820579 Jul 25 '17 at 17:24

Your Answer

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

Browse other questions tagged or ask your own question.