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 21: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 
.
