Question

Rina is trying to find the highest common factor of 418 and 33 using Euclid's division algorithm (EDA). In her third step, she gets the divisor of 11. Find the remainder at the end of the 3rd step.​

Answer 1

Given:

Rina is trying to find the highest common factor of 418 and 33 using Euclid's division algorithm (EDA). In her third step, she gets the divisor of 11.  

To find:

Find the remainder at the end of the 3rd step.​

Solution:

Step 1: From given we have, 418 and 33. Let us first represent these numbers in the form of a = bq + r

⇒ 418 = 33 × 12 + 22

Step 2: Apply Euclid's division algorithm taking the divisor 33 and remainder 22

⇒ 33 = 22 × 1 + 11     [ a = bq + r]

Step 3: Apply Euclid's division algorithm taking the new divisor 22 and the new remainder 11

⇒ 22 = 11 × 2 + 0

Step 4: We cannot proceed further since the remainder is 0.

Step 5: The last divisor is 11 and we have HCF of 418 and 33 = 11