Mathematics >

Number Theory
Sometimes called "Euclid's lemma" in textbooks when appearing before a proof of the

fundamental theorem of arithmetic. It states that if

*p* is a

prime number and

*p|ab*, then either

*p|a* or

*p|b* ("|" means "divides").

Corollaries:

- If
*p* is a prime and *p|a*^{n}, then *p|a*.
- If
*a* and *c* are relatively prime, then *c|ab* implies *c|b*.

Incidentally, Euclid's Second Theorem states that

there are infinitely many primes.

**
References:
**
"Euclid's First Theorem" is sometimes referred as such according to MathWorld.com.
Many of these theorems appear in

Euclid's Elements.

Book VII,

proposition 30 states Euclid's First Theorem.

Book IX,

proposition 14 partially states the

fundamental theorem of arithmetic, and

proposition 20 states Euclid's Second Theorem.
Thanks to

Swap for tipping me off about this.