Difference between revisions of "Euclid's Lemma"

Revision as of 11:34, 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 $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$ .

@@ Line 11: / Line 11: @@
 ===Second Proof===
-We have <math> a\vert bc</math>, so <math> bc=na</math>, with <math> n</math> an integer. Dividing both sides by <math> a</math>, we have
+We have <math> p\vert ab</math>, so <math> ab=np</math>, with <math> n</math> an integer. Dividing both sides by <math> p</math>, we have
-<math>\frac{bc}{a}=n</math>. But <math> \gcd(a,b)=1</math> implies <math> b/a</math> is only an integer if <math> a=1</math>. So
+<math>\frac{ab}{p}=n</math>. But <math> \gcd(p,a)=1</math> implies <math> a/p</math> is only an integer if <math> p=1</math>. So
-<math>\frac{bc}{a} = b \frac{c}{a} = n </math>,
+<math>\frac{ab}{p} = a \frac{b}{p} = n </math>,
-which means <math> a</math> must divide <math> c</math>.
+which means <math> p</math> must divide <math> b</math>.
 ==See Also==

Page

Toolbox

Search

Difference between revisions of "Euclid's Lemma"

Revision as of 11:34, 23 March 2008

Contents

Proof of Euclid's Lemma

First Proof

Second Proof

See Also