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

Expert Answer:

Dear Student,

Euclid's Division Lemma


              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.


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=14 x 4

Then either

                  Y x 7 = 14


                   Y x 7 = 4       

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



Team Topperlearning

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

Queries asked on Sunday & after 7pm from Monday to Saturday will be answered after 12pm the next working day.