Euclid's lemma

Euclid's lemma states that if a prime divides a product of integers, it divides at least one factor. It underpins the uniqueness of prime factorization.

Divisibility: An integer divides another when the latter is an integer multiple of the former. The lemma is a rule about how divisibility behaves across a product.
Fundamental theorem of arithmetic: Every integer greater than 1 has a unique prime factorization, apart from the order of its factors. Euclid's lemma is the key step proving that two prime factorizations must match.
Euclid: An ancient Greek mathematician whose work, Elements, systematized geometry and number theory. The lemma bears his name and appears in his treatment of prime numbers.
Composite number: A positive integer greater than 1 that is not prime. A composite divisor of a product need not divide either factor, unlike a prime.
Coprime integers: Two integers are coprime when their greatest common divisor is 1. If the prime does not divide one factor, that factor is coprime to the prime.
Euclidean algorithm: An algorithm for finding the greatest common divisor by repeated division with remainder. Its gcd calculations provide a route to the coprimality argument used in proofs of the lemma.
Elements (Euclid): A thirteen-book mathematical treatise by Euclid, covering geometry, number theory, and proportion. Book VII contains the proposition traditionally identified with Euclid's lemma.
Irreducible element: A nonzero nonunit in an integral domain that cannot be written as a product of two nonunits. Irreducibility alone need not guarantee the product-divisibility property outside unique factorization settings.
Bézout's identity: For integers a and b, their greatest common divisor is an integer linear combination of a and b. A Bézout combination proves the prime must divide the other factor.
Euclidean domain: An integral domain equipped with a Euclidean function that enables division with remainder. Euclidean domains support analogous prime-divides-product results through their gcd structure.

Linked from 12 pages