CBSE Class 10 Maths Sample Paper 2019 | Q13

Section C | Real Numbers HCF - Euclid's Algorithm

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.

NCERT Solution to Class 10 Maths

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.

Try CBSE Online CoachingClass 10 Maths

Register in 2 easy steps and
Start learning in 5 minutes!

NCERT Solution to Exercise QuestionsCBSE Class 10 Maths

WhatsApp: WhatsApp Now
Email: learn@maxtute.com