I saw on the internet the following Proof of Euclid's lemma, which states that if a prime number divides the product of two numbers, then it must divide at least one of the two numbers.
Since $p \mid bc$, there exists an integer $n$ such that $bc = np$.
Now, assume $p\nmid b$. I.e. there are integers $k, i$ with $0< i < p$, such that $b = kp + i$And therefore, $$np = bc = c(kp +i ) = kpc + ci \implies ci = p(n – kc)$$
So, $p$ is a factor of $ci$ and since $0 < i < k$ , $p$ must be a factor of $c$.
I am particularly confused by the last statement:
… since $0 < i < k$, $p$ must be a factor of $c$
This does not make sense to me… $i$ needs not be less than $k$.
This proof was selected as the best answer in a Yahoo question
I would be grateful if someone could explain me what is going on at the end of the proof or if it is wrong.
UPDATE: I need a proof that does not use the gcd algorithm.
Best Answer
Suppose there were a counterexample, with $pa=bc$, $p$ a prime, but neither $b$ nor $c$ divisible by $p$. Then there would be a counterexample with $p$ as small as possible and, for that $p$, $b$ as small as possible. Note that $b\gt1$, since otherwise we would have $pa=c$, which means $p$ divides $c$.
We first note that $b\lt p$, since otherwise $pa'=p(a-c)=(b-p)c=b'c$ would be a smaller counterexample. But now $b\gt1$ implies $b$ is divisible by some prime $q$, which means we have $q$ dividing $pa$ with $q\le b\lt p$. By the minimality of $p$ as a counterexample, we conclude that $q$ divides $a$ (since it can't divide $p$). If we now write $a=a'q$ and $b=b'q$ and note that $b'\lt b\lt p$ implies $p$ doesn't divide $b'$ either, we find that $pa'=b'c$ is a smaller counterexample, which is a contradiction. Thus there can be no counterexample.
Remark (added later): The subtlety of Euclid's lemma is sometimes demonstrated with examples of multiplicative systems in which the lemma does not hold. One standard example is the set of positive integers congruent to $1$ mod $4$; another is the set of even integers. For the set $\{1,5,9,13,17,21,\ldots\}$ we have $9$, $21$ and $49$ as primes -- that is, none is the product of other numbers in the set (except, of course, themselves times $1$) -- yet $9\cdot49=21\cdot21$. As for the even integers, the primes are $\{2,6,10,14,18,\ldots\}$ -- that is, anything that's twice an ordinary odd number -- yet $2\cdot30=6\cdot10$.
It's worth seeing where the proof given above fails for these examples.
The failure point in both cases is in the statement "otherwise $pa'=p(a-c)=(b-p)c=b'c$ would be a smaller counterexample," but for different reasons. The set of integers congruent to $1$ mod $4$ is not closed under subtraction, so the statement simply makes no sense. For the set of even integers, the statement makes sense, but it's not true: $2$ does not divide $6$, but it does divide $6-2=4=2\cdot2$. What's going on is that, although the even integers are a ring, it's a ring without a unit (because $1$ is odd, not even): The theorem $d\mid n\implies d\mid (n+d)$ holds because its proof goes $d\mid n\implies n=dm\implies n+d=dm+d=d(m+1)\implies d\mid (n+d)$, and that proof falls apart if you don't have the number $1$.
Alternative proof (added later): I wondered from the outset if it was really necessary to make the double assumption that both $p$ and $b$ (given $p$) are as small as possible. It turns out it's enough to assume you have a counterexample with minimal $b$.
Among all counterexamples $pa=bc$ (with $p$ prime and not dividing either $b$ or $c$), there would have to be one with minimal $b$. Note that $b\not\mid a$, since otherwise $p$ would divide $p(a/b)=c$. Note also that $b\not\mid p$.
We first argue that $b$ must itself be prime. If not -- if $b=b'b''$ with $b',b''\lt b$ -- then either $p\mid b'(b''c)$ or $p\mid b''c$ would be a smaller counterexample. That is, since $p$ doesn't divide $b$, it can't divide any divisor of $b$ (that's true whether $p$ is prime or not), so if the minimality of $b$ rules out $b'(b''c)$ as a counterexample (because $b'\lt b$), we must conclude $p$ divides $b''c$, which itself violates the assumed minimality of $b$.
Now write $p=bk+r$ with $0\lt r\lt b$. (We have $0\lt r$ since $b\not\mid p$.) Since $b$ divides $pa$, it also divides $ra$, but $b$ clearly doesn't divide $r$ (since $0\lt r\lt b$) nor, as noted above, does it divide $a$. So this gives us a new counterexample: a prime number, $b$, that divides a product, $ra$, without dividing either factor. Most important, the first of those factors, $r$, is smaller than $b$. This contradicts the assumed minimality of $b$, so we can conclude that no counterexamples exist.