CBSE Class 10 Maths Sample Paper 2019 | Q13

This 2019 CBSE class 10 Maths sample question paper 2019 3 mark question is from Real Numbers. Concept: Euclid's division algorithm and HCF of numbers.

Question 13: Use Euclid's division algorithm to find the HCF of 726 and 275.

Video Explanation

Explanatory Answer | CBSE Math Sample Paper 2019 Q13

Euclid's division algorithm to find HCF of 2 numbers:

1. Apply the division algorithm with the larger number, n as the dividend and the smaller number, d as the divisor. i.e., express n = qd + r, where 'q' is a positive integer and 0 ≤ r < d

2. If r ≠ 0, repeat step 1 with 'd' of step 1 as n and 'r' of step 1 as d till we get r = 0.

3. The divisor of the step in which r = 0 is the HCF of the given numbers.

Apply Euclid's division lemma to 726 and 275:

Step 1: Because 726 > 275 let us apply Euclid's division lemma to 726 with 275 as the divisor
726 = 275 × 2 + 176
Step 2: Because the remainder 176 ≠ 0, we apply the division lemma to 275 with 176 as divisor
275 = 176 × 1 + 99
Step 3: Because the remainder 99 ≠ 0, we apply the division lemma to 176 with 99 as divisor
176 = 99 × 1 + 77
Step 4: Because the remainder 77 ≠ 0, we apply the division lemma to 99 with 77 as divisor
99 = 77 × 1 + 22
Step 5: Because the remainder 22 ≠ 0, we apply the division lemma to 77 with 22 as divisor
77 = 22 × 3 + 11
Step 6: Because the remainder 11 ≠ 0, we apply the division lemma to 22 with 11 as divisor
22 = 11 × 2 + 0

The remainder has now become zero. So the iteration stops with this step.
The divisor at this stage is 11. So, the HCF of 726 and 275 is 11.