HCF of 2 Numbers Using Euclid Lemma
HCF of 2 Numbers Using Euclid Lemma
Euclid Division Algorithm to Find HCF:
It is a technique which helps us to speed up the process of computing the highest common factor. It is based on the fact
a = bq + r
Then HCF(a,b) = HCF (b,r)
= HCF (b, (a-bq)
Example: Find the HCF of 75 and 35
HCF( 75,35)= HCF( 35, (75- 2 X 35))
= HCF( 35, 5)
= HCF ( 5, (35 -7X 5))
= HCF (5,0)=5
The Euclidean algorithm ( also called Euclid s division algorithm) can be described as follows:
TO obtain HCF of two integers a and b with a > b > 0 we follow the following steps:
Step I If b=0, then HCF (a,b) = a.
If b > 0, find integers q and r such that
a = bq + r where 0< r < b.
Step II Replace a by b and b by r and go back to Step I.
Example 1 Use Euclid s division algorithm to find HCF of 196 and 3820.
Solution Here a = 3820 and b = 196
Step I 3820 = 196 X 19 + 96
q = 19 and r = 96
Step II Set a = 196 and b = 96
Go back to Step 1.
Step III 196 = 96 X 2 + 4 where q = 2 and r = 4
Step IV Set a = 96 and b = 4
Perform Step step I.
Step I 96 = 24 X 4 + 0
q = 24 and r =0
Step II Now as r = 0 So HCF = 4
Thus, HCF ( 3820, 196) = 4
Students / Parents Reviews [20]
The experience was nice. I studied here for three years and saw a tremendous change in myself. I started liking subjects like English and SST which earlier I ran from. Extra knowledge gave me confidence to overcome competitive exams. One of the best institutes for secondary education.
Aman Kumar Shrivastava
10thAbhyas is good institution and a innovative institute also. It is a good platform of beginners.Due to Abhyas,he has got knoweledge about reasoning and confidence.My son has improved his vocabulary because of Abhyas.Teacher have very friendly atmosphere also.
Manish Kumar
10thIt was good as the experience because as we had come here we had been improved in a such envirnment created here.Extra is taught which is beneficial for future.
Eshan Arora
8thAbhyas academy is great place to learn. I have learnt a lot here they have finished my fear of not answering.It has created a habit of self studying in me.The teachers here are very supportive and helpful. Earlier my maths and science was good but now it has been much better than before.
Barkha Arora
10thAbhyas institute is one of the best coaching institute in the vicinity of Ambala cantt.The institute provides good and quality education to the students.The teachers are well experienced and are very helpful in solving the problems. The major advantages of the institute is extra classes for weak...
Shreya Shrivastava
8thBeing a parent, I saw my daughter improvement in her studies by seeing a good result in all day to day compititive exam TMO, NSO, IEO etc and as well as studies. I have got a fruitful result from my daughter.
Prisha Gupta
8thThird consective year,my ward is in Abhyas with nice experience of admin and transport support.Educational standard of the institute recumbent at satisfactory level. One thing would live to bring in notice that last year study books was distributed after half of the session was over,though study ...
Ayan Ghosh
8thAbhyas is a complete education Institute. Here extreme care is taken by teacher with the help of regular exam. Extra classes also conducted by the institute, if the student is weak.
Om Umang
10thAbhyas institute is one of the best coaching institute in the vicinity of Ambala Cantt area. The teachers of the institute are well experienced and very helpful in solving the problems of the students.The good thing of the institute is that it is providing extra classes for the students who are w...
Aman Kumar Shrivastava
10thI have spent a wonderful time in Abhyas academy. It has made my reasoning more apt, English more stronger and Maths an interesting subject for me. It has given me a habbit of self studying
Yatharthi Sharma
10thMy experience was very good with Abhyas academy. I am studying here from 6th class and I am satisfied by its results in my life. I improved a lot here ahead of school syllabus.
Ayan Ghosh
8thMy experience with Abhyas Academy has been very good. When I was not in Abhyas whenever teacher ask questions I could not speak it confidently but when I came in Abhyas, my speaking skills developed and now I am the first one to give the answer of teachers question.
Upmanyu Sharma
7thIt was a good experience with Abhyas Academy. I even faced problems in starting but slowly and steadily overcomed. Especially reasoning classes helped me a lot.
Cheshta
10thAbout Abhyas metholodology the teachers are very nice and hardworking toward students.The Centre Head Mrs Anu Sethi is also a brilliant teacher.Abhyas has taught me how to overcome problems and has always taken my doubts and suppoeted me.
Shreya Shrivastava
8thMy experience with Abhyas is very good. I have learnt many things here like vedic maths and reasoning also. Teachers here first take our doubts and then there are assignments to verify our weak points.
Shivam Rana
7thAbhyas is an institute of high repute. Yogansh has taken admission last year. It creates abilities in child to prepare for competitive exams. Students are motivated by living prizes on basis of performance in Abhyas exams. He is satisfied with institute.
Yogansh Nyasi
7thIn terms of methodology I want to say that institute provides expert guidence and results oriented monitering supplements by requsite study material along with regular tests which help the students to improve their education skills.The techniques of providing education helps the students to asses...
Aman Kumar Shrivastava
10thWe started with lot of hope that Abhyas will help in better understnding of complex topics of highers classes. we are not disappointed with the progress our child has made after attending Abhyas. Though need to mention that we expected a lot more. On a scale of 1-10, we would give may be 7.
Manya
8thUsually we see institutes offering objective based learning which usually causes a lag behind in subjective examinations which is the pattern followed by schools. I think it is really a work of planning to make us students grab the advantages of modes of examination, Objective Subjective and Onli...
Anika Saxena
8thWhen I have not joined Abhyas Academy, my skills of solving maths problems were not clear. But, after joining it, my skills have been developed and my concepts of science and SST are very well. I also came to know about other subjects such as vedic maths and reasoning.
