Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Euclid's Lemma"

m (→‎Proof of Euclid's lemma)
(No difference)

Revision as of 20:31, 11 January 2008

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Euclid%27s_Lemma&oldid=22341"