what is euclid,s division lemma?

 
gud day

  • 2

This lemma is very useful for finding the H.C.F. of large numbers where breaking them into factors is difficult. This method is known as Euclid’s Division Algorithm.

  • 1

 

Euclid's Division Lemma


Euclid’s division lemma, states that for any two positive integers ‘a’ and ‘b’ we can find two whole numbers ‘q’ and ‘r’ such that

Euclid’s division lemma , Euclid’s division algorithm, Euclid’s lemma, Euclid’s algorithm , H.C.F, highest common factor

Euclid’s division lemma can be used to: 
Find the highest common factor of any two positive integers and to show the common properties of numbers.
Finding H.C.F  using Euclid’s division lemma:
Suppose, we have two positive integers ‘a’ and ‘b’ such that ‘a’ is greater than ‘b’. Apply Euclid’s division lemma to the given integers ‘a’ and ‘b’ to find two whole numbers ‘q’ and ‘r’ such that, ‘a’ is equal to ‘b’ multiplied by ‘q’ plus ‘r’.

Check the value of ‘r’. If ‘r’ is equal to zero then ‘b’ is the HCF of the given numbers. If ‘r’ is not equal to zero, apply Euclid’s division lemma to the new divisor ‘b’ and remainder ‘r’. Continue this process till the remainder ‘r’ becomes zero. The value of the divisor ‘b’ in that case is the HCF of the two given numbers.
Euclid’s division algorithm can also be used to find some common properties of numbers.

plz thumbs up

  • 7

 

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 · b, then at least one of a and b must be a multiple of p. Say,

  N=56

  p=7

   

Then either

 

or

            

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

plz thumbs up 

  • 1

What is Euclids Algorithm?

  • 1
What are you looking for?