Lemma of Euclid

The Euclid's lemma is a basic Lemma in the classical arithmetic or elementary number theory . His statement is usually used to prove the fundamental theorem of arithmetic , more precisely for the uniqueness of the prime factorization . It already appears in Euclid's Elements (Book VII, Proposition 30).

The lemma for natural numbers

The contemporary translation of the classical formulation for natural or whole numbers is:

If a prime number divides a product , so does one (or both) of the factors . ${\displaystyle p}$ ${\displaystyle ab}$

The following generalization is equivalent to this:

If the product divides and is coprime to one of the factors, it divides the other. ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle ab}$

Because if it is a prime number, you get the upper version again; is composite , it applies to each of its prime factors and therefore to itself. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

proof

The proof of the lemma can classically be carried out as a direct proof , it uses the lemma of Bézout and thus argues partly outside the natural numbers, but the statement is obviously also valid to a limited extent . ${\displaystyle \mathbb {N} }$

Be arbitrary. Suppose a prime number divides the product but not the factor . Then we have to show that is a divisor of . ${\displaystyle a,b\in \mathbb {Z} }$ ${\displaystyle p}$ ${\displaystyle ab}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle b}$

From the assumption it follows in particular that and are coprime. With Bézout there are then two whole numbers and , so that holds. This equation is multiplied by and rearranged somewhat ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle sp+ta=1}$ ${\displaystyle b}$

${\displaystyle p(sb)+(ab)t=b}$.

According to the assumption there is a with , so on the left side of the equation you can exclude: ${\displaystyle c\in \mathbb {Z} }$ ${\displaystyle ab=cp}$ ${\displaystyle p}$

${\displaystyle p(sb+ct)=b}$.

So is factor of a product that results. Thus it shares what was to be shown. ${\displaystyle p}$ ${\displaystyle b}$ ${\displaystyle b}$

Applications and generalization

Euclid's lemma occurs indirectly in almost every argument by means of divisibility, especially with prime factorization and the Euclidean algorithm . In practical arithmetic problems, the lemma itself only plays a subordinate role.

The lemma also applies to main ideal rings : Let be a main ideal ring, and irreducible in , then applies . ${\displaystyle H}$ ${\displaystyle a,b,p\in H}$ ${\displaystyle p}$ ${\displaystyle H}$ ${\displaystyle p\mid ab\Rightarrow p\mid a\lor p\mid b}$

Individual evidence

1. ↑ Euclid's Elements, Book VII, Prop 30 (English translation, with original proof)
2. ↑ Jürgen Wolfart: Introduction to Algebra and Number Theory . Vieweg, Braunschweig / Wiesbaden 1996, ISBN 3-528-07286-5 , pp. 76 .