Difference between revisions of "Euclid's Lemma"

Revision as of 21:31, 13 May 2008

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

A positive integer $p>1$ is a prime number if and only if $p \mid ab$ implies that $p \mid a$ or $p\mid b$ , for all integers $a$ and $b$ .

Proof of Euclid's Lemma

Without loss of generality, suppose $\gcd(p,a)=1$ (otherwise we are done). By Bezout's Lemma, there exist integers such that $x,y$ such that $px+ay=1$ . Hence $b(px+ay)=b$ and $pbx+aby=b$ . Since $p\mid p$ and $p \mid ab$ (by hypothesis), $p \mid pbx + aby =b$ , as desired.

On the other hand, if $p>1$ is not prime, then it must be composite, i.e., $p=ab$ , for integers $a,b$ both greater than 1. Then $p\nmid a$ and $p\nmid b$ . Thus the lemma's converse holds as well. $\blacksquare$

@@ Line 1: / Line 1: @@
-'''Euclid's Lemma''' is a result in [[number theory]], that is attributed to [[Euclid]]. It states that:
+'''Euclid's Lemma''' is a result in [[number theory]] attributed to [[Euclid]]. It states that:
-A positive integer <math>p</math> is a [[prime number]] if and only if <math>p|ab \Longrightarrow p|a</math> or <math> p|b </math>
+A positive integer <math>p>1</math> is a [[prime number]] if and only if <math>p \mid ab</math> implies that <math>p \mid a</math> or <math>p\mid b</math>, for all [[integer]]s <math>a</math> and <math>b</math>.
-==Proof of Euclid's Lemma==
+== Proof of Euclid's Lemma ==
-There are two proofs of Euclid's lemma.
-===First Proof===
+Without loss of generality, suppose <math> \gcd(p,a)=1</math> (otherwise we are done).  By [[Bezout's Lemma]], there exist integers such that <math>x,y</math> such that <math>px+ay=1</math>. Hence <math>b(px+ay)=b</math> and <math>pbx+aby=b</math>. Since <math> p\mid p</math> and <math> p \mid ab </math> (by hypothesis), <math>p \mid pbx + aby =b</math>, as desired.
-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===
+On the other hand, if <math>p>1</math> is not prime, then it must be composite, i.e., <math>p=ab</math>, for integers <math>a,b</math> both greater than 1.  Then <math>p\nmid a</math> and <math>p\nmid b</math>.  Thus the lemma's converse holds as well.  <math>\blacksquare</math>
-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{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{ab}{p} = a \frac{b}{p} = n </math>,
-which means <math> p</math> must divide <math> b</math>.
 ==See Also==
-*[[Euclid]]
-*[[Number theory]]
+* [[Fundamental theorem of arithmetic]]
+* [[Euclid]]
+* [[Number theory]]
 [[Category:Number theory]]

Page

Toolbox

Search

Difference between revisions of "Euclid's Lemma"

Revision as of 21:31, 13 May 2008

Proof of Euclid's Lemma

See Also