GMAT GRE 1st Grade 2nd Grade 3rd Grade 4th Grade 5th Grade 6th Grade 7th grade math 8th grade math 9th grade math 10th grade math 11th grade math 12th grade math Precalculus Worksheets Chapter wise Test MCQ's Math Dictionary Graph Dictionary Multiplicative tables Math Teasers NTSE Chinese Numbers CBSE Sample Papers 
Euclids Division AlgorithmCovid19 has led the world to go through a phenomenal transition . Elearning is the future today. Stay Home , Stay Safe and keep learning!!! In this section we will discuss Euclids Division Algorithm.We have seen that the said lemma is nothing but a restatement of the long division process which we have been using all these years. In this section, we will learn one more application of Euclids division lemma known as Euclids Division Algorithm. An algorithm means a series of well defined steps which provide a procedure of calculation repeated successively on the results of earlier steps till the desired result is obtained. Theorem : If a and b are positive integers such that a = bq + r, then every common divisor of a and b is a common divisor of b and r, and viceversa. Proof : Let c be a common divisor of a and b. Then, c a ⇒ a = cq1 for some integer q1 c b ⇒ b = cq2 for some integer q2. Now, a = bq + r ⇒ r = a – bq ⇒ r = cq1 – cq2 q ⇒ r = c( q1 – q2q) ⇒ c  r ⇒ c r and c  b ⇒ c is a common divisor of b and r. Hence, a common divisor of a and b is a common divisor of b and r. Euclids Division Algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers. Recall that the HCF of two positive integers a and b is the largest positive integer d that divides both a and b.  Let us state Euclid’s division algorithm clearly. To obtain the HCF of two positive integers, say c and d, with c > d, follow the steps below: Step 1 : Apply Euclid’s division lemma, to c and d. So, we find whole numbers, q and r such that c = dq + r, 0 ≤ r < d. Step 2 : If r = 0, d is the HCF of c and d. If r ≠ 0, apply the division lemma to d and r. Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be the required HCF. This algorithm works because HCF (c, d) = HCF (d, r) where the symbol HCF (c, d) denotes the HCF of c and d, etc.  Examples : 1) Use Euclid’s algorithm to find the 420 and 130. Solution : Step:1 Since 420 > 130 we apply the division lemma to 420 and 130 to get , 420 = 130 x 3 + 30 Step:2 Since 30 ≠ 0 , we apply the division lemma to 130 and 30 to get 130 = 30 x 4 + 10 Step:3 Since 10 ≠ 0 , we apply the division lemma to 30 and 10 to get 30 = 10 x 3 + 0 The remainder has now become zero, so our procedure stops. Since the divisor at this Step is 10, the HCF of 420 and 130 is 10.  2) Use Euclid’s algorithm to find the 65 and 117. Solution : Step:1 Since 117 > 65 we apply the division lemma to 117 and 65 to get , 117 = 65 x 1 + 52 Step:2 Since 52 ≠ 0 , we apply the division lemma to 65 and 52 to get 65 = 52 x 1 + 13 Step:3 Since 13 ≠ 0 , we apply the division lemma to 52 and 13 to get 52 = 13 x 4 + 0 The remainder has now become zero, so our procedure stops. Since the divisor at this Step is 13, the HCF of 117 and 52 is 13. Euclid's Geometry • Euclid Geometry • Euclids division lemma • Euclids division Algorithm • Fundamental Theorem of Arithmetic • Finding HCF LCM of positive integers • Proving Irrationality of Numbers • Decimal expansion of Rational numbers Home Page Covid19 has affected physical interactions between people. Don't let it affect your learning.
More To Explore
