Euclid's lemma

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

The lemma for natural numbers

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

Equivalently, is the following generalization:

Because if a prime number, we obtain the upper composure, composed, as it applies to each of its prime factors and thus for yourself

Evidence

The proof of the lemma can be classically performed as direct proof, he uses the lemma of Bézout and thus argues in part, outside of the natural numbers, the statement is true but obviously limited to.

Be arbitrarily. Suppose a prime divides the product, but not the factor. Then to show that a is divisor of.

From the assumption follows in particular that and are relatively prime, with Bézout then there exist two integers and so true. By multiplying this equation and some resorted supplies

According to assumption exists with one, so can exclude on the left side of the equation:

Thus is a factor of a product that results. Thus, it divides and that was to show.

Applications and generalization

The lemma of Euclid comes indirectly in almost every argument by divisibility before, especially in prime factorizations and the Euclidean algorithm. In practical computing tasks, the lemma itself plays only a minor role.

The lemma is true for principal ideal rings: Be a principal ideal ring, and irreducible in, then apply.