Difference between revisions of "Euclid's Lemma"

Revision as of 09:24, 15 November 2007

In Number Theory, the result that

A positive integer $p$ is a prime number if and only if $p|ab \Longrightarrow p|a$ or $p|b$

is attributed to Euclid

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

@@ Line 1: / Line 1: @@
 In [[Number Theory]], the result that
-A positive integer <math>p</math> is a [[prime number]] if and only iff <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]]

Page

Toolbox

Search

Difference between revisions of "Euclid's Lemma"

Revision as of 09:24, 15 November 2007

Proof of Euclid's lemma