Difference between revisions of "Euclid's Lemma"
m (Euclid's lemma moved to Euclid's Lemma: per A:NAME) |
(wikify) |
||
Line 1: | Line 1: | ||
− | + | '''Euclid's Lemma''' is a result in [[number theory]], that is 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</math> is a [[prime number]] if and only if <math>p|ab \Longrightarrow p|a</math> or <math> p|b </math> | ||
− | |||
− | ==Proof of Euclid's | + | ==Proof of Euclid's Lemma== |
There are two proofs of Euclid's lemma. | There are two proofs of Euclid's lemma. | ||
− | First Proof | + | ===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(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. | ||
− | + | ===Second Proof=== | |
− | 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> a\vert bc</math>, so <math> bc=na</math>, with <math> n</math> an integer. Dividing both sides by <math> a</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{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{bc}{a} = b \frac{c}{a} = n </math>, | <math>\frac{bc}{a} = b \frac{c}{a} = n </math>, | ||
which means <math> a</math> must divide <math> c</math>. | which means <math> a</math> must divide <math> c</math>. | ||
+ | |||
+ | ==See Also== | ||
+ | *[[Euclid]] | ||
+ | *[[Number theory]] | ||
+ | |||
+ | [[Category:Number theory]] |
Revision as of 20:33, 11 January 2008
Euclid's Lemma is a result in number theory, that is attributed to Euclid. It states that:
A positive integer is a prime number if and only if or
Proof of Euclid's Lemma
There are two proofs of Euclid's lemma.
First Proof
By assumption , thus we can use Bezout's lemma to find integers such that . Hence and . Since and (by hypothesis), we conclude that as claimed.
Second Proof
We have , so , with an integer. Dividing both sides by , we have . But implies is only an integer if . So , which means must divide .