Number theory is a special branch of mathematics in which we study about the different types of numbers and their properties. |

**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.

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:**

**We may also conclude two equivalent statements:**

**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.

**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. 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.