The HCF of 196 and 38416 using Euclid algorithm is

Foundation

Mathematics Foundation

HCF and LCM

Question

192

191

196

193

College PredictorLive

Know your College Admission Chances Based on your Rank/Percentile, Category and Home State.

Get your JEE Main Personalised Report with Top Predicted Colleges in JoSA

Let us first state Euclid’s division algorithm:

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.

Now, let us apply the Euclid’s division algorithm to the given numbers 196 and 38416 as follows:

38416 = 196 × 196 + 0

Since the remainder is 0.

Hence, the HCF of 196 and 38416 is 196.