# what is euclid division lemma?where it is used?wht is the significance of that lemma?what is algorithim and lemma?

### Asked by ramya1994 | 1st Apr, 2011, 07:28: PM

### Dear Student,
**Euclid's Division Lemma**

**Introduction:**

In mathematics, Euclid's lemma is most important lemma as regards divisibility and prim numbers. In simplest form, lemma states that a prime number that divides a product of two integers have to divide one of the two integers. This key fact requires a amazingly sophisticated proof and is a wanted step in the ordinary proof of the fundamental theorem of arithmetic.

**Euclid’s Division Lemma**

- Euclid’s division lemma, state that for a few two positive integers ‘a’ and ‘b’ we can obtain two full numbers ‘q’ and ‘r’ such that
- Euclid’s division lemma can be used to:

Find maximum regular factor of any two positive integers and to show regular properties of numbers.
- Finding Highest Common Factor (HCF) using Euclid’s division lemma:

Suppose, we hold two positive integers a and b such that a is greater than b. Apply Euclid’s division lemma to specified integers a and b to find two full numbers q and r such that, a is equal to b multiplied by q plus r.
- 'r' value is verified. If r is equal to zero then b is the HCF of the known numbers.
- If r is not equal to zero, apply Euclid’s division lemma to the latest divisor b and remainder r.
- Maintain this process till remainder r becomes zero. Value of divisor b in that case is the HCF of two given numbers.

Euclid’s division algorithm can be used to find some regular properties of numbers.

**Example**

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

N=56

p=7

N=14 x 4

Then either

Y x 7 = 14

or

Y x 7 = 4

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

Regards

Team Topperlearning

**Euclid's Division Lemma**

**Introduction:**

In mathematics, Euclid's lemma is most important lemma as regards divisibility and prim numbers. In simplest form, lemma states that a prime number that divides a product of two integers have to divide one of the two integers. This key fact requires a amazingly sophisticated proof and is a wanted step in the ordinary proof of the fundamental theorem of arithmetic.

**Euclid’s Division Lemma**

- Euclid’s division lemma, state that for a few two positive integers ‘a’ and ‘b’ we can obtain two full numbers ‘q’ and ‘r’ such that
- Euclid’s division lemma can be used to:

Find maximum regular factor of any two positive integers and to show regular properties of numbers. - Finding Highest Common Factor (HCF) using Euclid’s division lemma:

Suppose, we hold two positive integers a and b such that a is greater than b. Apply Euclid’s division lemma to specified integers a and b to find two full numbers q and r such that, a is equal to b multiplied by q plus r. - 'r' value is verified. If r is equal to zero then b is the HCF of the known numbers.
- If r is not equal to zero, apply Euclid’s division lemma to the latest divisor b and remainder r.
- Maintain this process till remainder r becomes zero. Value of divisor b in that case is the HCF of two given numbers.

Euclid’s division algorithm can be used to find some regular properties of numbers.

**Example**

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

N=56

p=7

N=14 x 4

Then either

Y x 7 = 14

or

Y x 7 = 4

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

Regards

Team Topperlearning

### Answered by | 2nd Apr, 2011, 08:15: AM

## Related Videos

### Kindly Sign up for a personalised experience

- Ask Study Doubts
- Sample Papers
- Past Year Papers
- Textbook Solutions

#### Sign Up

#### Verify mobile number

Enter the OTP sent to your number

Change