CBSE Class 9 Answered

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