Euclid's Lemma

Revision as of 11:34, 23 March 2008 by Jinkies (talk | contribs)

Euclid's Lemma is a result in number theory, that is attributed to Euclid. It states that:

A positive integer $p$ is a prime number if and only if $p|ab \Longrightarrow p|a$ or $p|b$


Proof of Euclid's Lemma

There are two proofs of Euclid's lemma.

First Proof

By assumption $\gcd(p,a)=1$, thus we can use Bezout's lemma to find integers $x,y$ such that $px+ay=1$. Hence $b\bdot(px+ay)=b$ (Error compiling LaTeX. Unknown error_msg) and $pbx+aby=b$. Since $p\mid p$ and $p \mid ab$ (by hypothesis), we conclude that $p \mid pbx + aby =b$ as claimed.

Second Proof

We have $p\vert ab$, so $ab=np$, with $n$ an integer. Dividing both sides by $p$, we have $\frac{ab}{p}=n$. But $\gcd(p,a)=1$ implies $a/p$ is only an integer if $p=1$. So $\frac{ab}{p} = a \frac{b}{p} = n$, which means $p$ must divide $b$.

See Also