Difference between revisions of "Euclid's Lemma"

Revision as of 10:26, 23 March 2008

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 $a\vert bc$ , so $bc=na$ , with $n$ an integer. Dividing both sides by $a$ , we have $\frac{bc}{a}=n$ . But $\gcd(a,b)=1$ implies $b/a$ is only an integer if $a=1$ . So $\frac{bc}{a} = b \frac{c}{a} = n$ , which means $a$ must divide $c$ .

@@ Line 8: / Line 8: @@
 ===First Proof===
-By assumption <math> \gcd(a,b)=1</math>, thus we can use Bezout's lemma to find integers <math> x,y</math> such that <math> ax+by=1</math>. Hence <math> c\cdot(ax+by)=c</math> and <math> acx+bcy=c</math>. Since <math> a\mid a</math> and <math> a \mid bc </math> (by hypothesis), we conclude that <math> a \mid acx + bcy =c </math> as claimed.
+By assumption <math> \gcd(p,a)=1</math>, thus we can use Bezout's lemma to find integers <math> x,y</math> such that <math> px+ay=1</math>. Hence <math> b\bdot(px+ay)=b</math> and <math> pbx+aby=b</math>. Since <math> p\mid p</math> and <math> p \mid ab </math> (by hypothesis), we conclude that <math> p \mid pbx + aby =b </math> as claimed.
 ===Second Proof===

Page

Toolbox

Search

Difference between revisions of "Euclid's Lemma"

Revision as of 10:26, 23 March 2008

Contents

Proof of Euclid's Lemma

First Proof

Second Proof

See Also