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 [10]
My experience with Abhyas academy is very good. I did not think that my every subject coming here will be so strong. The main thing is that the online tests had made me learn here more things.
Hiya Gupta
8thMy 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
8thAbhyas Methodology is very good. It is based on according to student and each child manages accordingly to its properly. Methodology has improved the abilities of students to shine them in future.
Manish Kumar
10thIt 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
10thBeing 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
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
7thI 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
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
8thIt 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 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.
