Euclid's lemma

This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (December 2009)

In mathematics, Euclid's lemma (Greek λῆμμα) is an important lemma regarding divisibility and prime numbers. In its simplest form, the lemma states that a prime number that divides a product of two integers must divide one of the two integers. This key fact requires a surprisingly sophisticated proof (using Bézout's identity), and is a necessary step in the standard proof of the fundamental theorem of arithmetic.

Euclid's lemma (also known as Euclid's first theorem) appears as proposition 30 in Book VII of Euclid's Elements. In modern notation:

If p is prime and p | ab, then either p | a or p | b.

Here | means “divides”; that is, x | y if x is a divisor of y.

In modern mathematics, “Euclid's lemma” is often used to refer to the following generalization of this statement:

If n | ab and n and a are relatively prime, then n | b.

This statement reduces to Euclid's proposition 30 in the case where n is prime.

Proof of Euclid's lemma

The standard proof of Euclid's lemma uses Bézout's identity. This states that, for any relatively prime integers x and y, there exist integers r and s such that

To prove Euclid's lemma, suppose that p is a prime factor of ab, but that p is not a factor of a. Then p and a must be relatively prime, so there exist integers r and s such that

Multiplying through by b gives

Now, the first term on the left is clearly a multiple of p. Since p divides ab, the second term on the left is also a multiple of p. It follows that b is a multiple of p, so p divides b. This proves that p is always either a divisor of a or a divisor of b. Q.E.D.

Virtually the same proof can be used to establish the more general form of Euclid's lemma, with p replaced by the integer n.

Example

Euclid's lemma in plain language says: If a number N is a multiple of a prime number p, and N = a · b, then at least one of a and b must be a multiple of p. Say,

,

,

and

.

Then either

or

.

Obviously, in this case, 7 divides 14 (x = 2).

See also

• Euclidean algorithm
• Fundamental theorem of arithmetic