011-40705070  or  
Call me
Download our Mobile App
Select Board & Class
  • Select Board
  • Select Class
 

how can we prove Euclid's division lemma?

Asked by soumya_sarkar.....(student) , on 23/3/11


Become Expert
Score more in Math
Start Now with Video Lessons, Sample Papers, Revision Notes & more for Class-X - CBSE 

EXPERT ANSWER

Hi!
 
Lemma is a term used in algebra like axiom in geometry which is a proven statement used as a stepping-stone toward the proof of another statement. It is always true and can be verified only (but cannot be proved).
 
So, Euclid’s Lemma can be verified only through the help of examples.
 
Cheers!!!

Posted by Gopal Mohanty(MeritNation Expert)on 24/3/11

This conversation is already closed by Expert

More Answers

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
  •  `a=bxxq+r`
  • 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

   `N=14xx4`

Then either

  `x*7=14`

or

            `x*7=4`  

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

Posted by Aneeta Yadav(student)on 23/3/11

Ask a QuestionHave a doubt? Ask our expert and get quick answers.
Show me more questions

close