# Difference between revisions of "Euclid's Lemma"

(spelling) |
m (→Proof of Euclid's lemma) |
||

Line 10: | Line 10: | ||

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

Line 16: | Line 16: | ||

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

## Revision as of 10:39, 15 November 2007

In Number Theory, the result that

A positive integer is a prime number if and only if or

is attributed to Euclid

## 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 .