Difference between revisions of "Euclid's Lemma"

(wikify)
Line 1: Line 1:
In [[Number Theory]], the result that
+
'''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>
  
is attributed to [[Euclid]]
 
  
==Proof of Euclid's lemma==
+
==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 $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(a,b)=1$, thus we can use Bezout's lemma to find integers $x,y$ such that $ax+by=1$. Hence $c\cdot(ax+by)=c$ and $acx+bcy=c$. Since $a\mid a$ and $a \mid bc$ (by hypothesis), we conclude that $a \mid acx + bcy =c$ 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$.

See Also