askvity

What is the HCF of 65 and 117 by using Euclid's division algorithm?

Published in Number Theory 1 min read

The HCF (Highest Common Factor) of 65 and 117, determined using Euclid's division algorithm, is 13.

Euclid's Division Algorithm Explained

Euclid's division algorithm is a method for finding the HCF of two numbers. It's based on the principle that the HCF of two numbers also divides their difference. The algorithm involves repeatedly applying the division lemma until the remainder is zero. The divisor at that stage is the HCF.

Here's how to apply the algorithm to find the HCF of 65 and 117:

  1. Divide the larger number (117) by the smaller number (65):

    117 = (65 × 1) + 52

  2. Now, consider the divisor (65) and the remainder (52) from the previous step. Divide 65 by 52:

    65 = (52 × 1) + 13

  3. Again, consider the divisor (52) and the remainder (13). Divide 52 by 13:

    52 = (13 × 4) + 0

Since the remainder is now 0, the divisor in this step, which is 13, is the HCF of 65 and 117.

Therefore, HCF(65, 117) = 13.

Related Articles