Euclid's lemma

• Euclid's Lemma

Named after ancient Greek mathematician Euclid of Alexandria (fl. 300 BCE). A version of the proposition appears in Book VII of his Elements.

Euclid's lemma (uncountable)

1. (number theory) The proposition that if a prime number p divides an arbitrary product ab of integers, then p divides a or b or both;
   slightly more generally, the proposition that for integers a, b, c, if a divides bc and gcd(a, b) = 1, then a divides c;
   (algebra, by generalisation) the proposition that for elements a, b, c of a given principal ideal domain, if a divides bc and gcd(a, b) = 1, then a divides c.
   • 1998, Peter M. Higgins, Mathematics for the Curious, Oxford University Press, page 78:

     I used Euclid's Lemma in a slightly sly way in the second chapter, where I ran through the argument that ${\displaystyle {\sqrt {2}}}$ is irrational. I said there that if ${\displaystyle 2}$ is a factor of ${\displaystyle a^{2}}$ then ${\displaystyle a}$ itself must be even. This follows from Euclid's Lemma upon taking ${\displaystyle p=2}$, the only even prime, and taking ${\displaystyle b=a}$. Indeed, using Euclid's Lemma it is not hard to generalize the argument showing ${\displaystyle {\sqrt {2}}}$ to be irrational to prove that ${\displaystyle {\sqrt {p}}}$ is irrational for any prime ${\displaystyle p}$.

   • 2007, David M. Burton, The History of Mathematics, McGraw-Hill, page 179:

     If ${\displaystyle a}$ and ${\displaystyle b}$ are not relatively prime, then the conclusion of Euclid's lemma may fail to hold. A specific example: ${\displaystyle 12\mid 9\cdot 8}$, but ${\displaystyle 12\nmid 9}$ and ${\displaystyle 12\nmid 8}$.

   • 2008, Martin Erickson, Anthony Vazzana, Introduction to Number Theory‎, Taylor & Francis (Chapman & Hall / CRC Press), page 42:

     In our discussion of Euclid's lemma (Corollary 2.18), we noted that the uniqueness of factorization of integers is a fact that we often take for granted given the way it is introduced in school.

The proposition as generalised to principal ideal domains is occasionally called Gauss's lemma; some writers, however, consider this usage erroneous as another result is known by that term.

• Fundamental theorem of arithmetic on Wikipedia.Wikipedia
• Principal ideal domain on Wikipedia.Wikipedia
• Bézout's identity on Wikipedia.Wikipedia
• Schreier domain on Wikipedia.Wikipedia
• Euclid's Lemma on Wolfram MathWorld
• alternative proof of Euclid’s lemma on PlanetMath.org