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

  • If p is a prime and p|an, 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.

"Euclid's First Theorem" is sometimes referred as such according to 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.