Sales Toll Free No: 1-855-666-7446

Euclid's lemma


Number theory is a special branch of mathematics in which we study about the different types of numbers and their properties. Prime numbers are a very important and frequently-used numbers in mathematics. Prime numbers are the numbers that are divisible only by one and itself ; such as - 2, 3, 11, 51, 47, 19 etc. Euclid's lemma is a theorem which is defined on prime numbers. Euclid's lemma must not be confused with Euclid's algorithm. Both are very different from each other. Euclid's lemma is also known as Euclid's first theorem. It is theorem that defines the fundamental property of prime numbers. Euclid's lemma states that :
If a product of two numbers is divided by a prime number, then at least one of the two given numbers must be divided by that prime number.

More elaborately, let us suppose a and b be any two integers. Also, let a prime number p which divides the product ab. Then, p must divide either a or b or both.

For Example: A prime number 3 divides 36 (which is the product of 9 and 4). It also divides 9. This lemma is just true for prime numbers, not for composite numbers.
For Example: A composite number 4 divides 60 - the product of 6 and 10. But it neither divides 6 nor 10.

The property of prime numbers defined by Euclid's lemma is the important concept for the proof of unique prime factorization theorem (also called fundamental theorem of arithmetic).


Back to Top
Euclid's lemma was discovered by the famous ancient Greek mathematician whose name was Euclid. This lemma was eventually named after him. This is known as lemma since it is quite similar to theorem and there is no theoretical difference between theorem and lemma. Euclid's lemma was first appeared in his book VII of Eculid's elements as the proposition. Since then, this lemma was practically included in almost every book that used to cover the elementary number theory. Euclid's lemma was realized to be an important theorem in number theory. It is very important is establishing several axioms, principles and theorems that are based on prime numbers and their product.


Back to Top
The symbol, | is used when a number divides another, for example : x | y means x divides y. The formulation of Euclid's lemma can be done in the following way:

Let us suppose that there is a prime number p. Also, there are any two integers a and b, such that p divides ab (p | ab), then either p divides a (p | a) or p divides b (p | b) or both.

We can write this in the form of following statements:
p | ab $\Rightarrow$ p | a or p | b or both
We may also conclude two equivalent statements:
p $\not{|}$ a and p $\not{|}$ b $\Rightarrow$ p $\not{|}$ ab
p $\not{|}$ a but p | ab $\Rightarrow$ p | b

One more result that is concluded from Euclid's lemma is :

If p | ab and p is relatively prime or coprime to a then p | b.


Back to Top
The proof of Euclid's lemma is as follows:
Let us suppose that p is a prime number. Also a and b are two numbers such that p = ab. Then we have to prove that if p | ab, then either p | a or p | b.

Let us assume that p does not divide a. Now, we need to prove that p | b.
By our assumption "p does not divide a", we conclude that gcd (p , a) = 1

We know that the GCD of two integers can be written in the form of linear combination of two integers. If x and y be two integers, then
p x + a y = (p, a)
p x + a y = 1

Multiplying both the sides by b
p x b + a y b = b _____(1)

We know that p | ab and p | p x b which implies that
p | (p x b + a y b)
using equation (1)
p | b
Hence the Euclid's lemma is proved.

Proof of Generalized Euclid's Lemma

Back to Top
The generalized Euclid's lemma states that :
For a prime number p if p | $a_{1}a_{2}...a_{n}$, then for some i ; p | $a_{i}$
The proof is as follows.

We are going to prove this by the induction method.
In which the basic case n = 2 is already proved by the Euclid's lemma.

For n > 2, note that
$a_{1}a_{2}...a_{n}$ = ($a_{1}a_{2}...a_{n-1})\ a_{n}$
This again becomes the product of two numbers.

Therefore, by the use of Euclid's lemma, we have
Either p | $a_{1}a_{2}...a_{n-1}$ or p | $a_{n}$

First case follows from our hypothesis that
p | $a_{1}a_{2}...a_{n-1}$ for some i < n - 1

Hence by induction it is proved that p | $a_{i}$ for some i.