Question

HCF \((132, 77)\) is:

• A. \(11\)
• B. \(77\)
• C. \(22\)
• D. \(44\)

Answer 1

The Correct Option is A

Step 1: Understanding the problem:
We are asked to find the Highest Common Factor (HCF) of the numbers 132 and 77.
The HCF of two numbers is the largest number that divides both numbers exactly (without leaving a remainder).

Step 2: Using the Euclidean algorithm:
The Euclidean algorithm is an efficient method to find the HCF of two numbers. It involves repeatedly applying the division algorithm:
\[ \text{HCF}(a, b) = \text{HCF}(b, a \mod b) \] where \( a \mod b \) is the remainder when \( a \) is divided by \( b \). We continue this process until the remainder is 0. The divisor at this point will be the HCF.

Step 3: Applying the Euclidean algorithm:
We will apply the Euclidean algorithm to 132 and 77:
1. First, divide 132 by 77:
\[ 132 \div 77 = 1 \quad \text{(quotient)} \quad \text{remainder} = 132 - 77 \times 1 = 132 - 77 = 55 \] So, \( 132 \mod 77 = 55 \). Now, we find \( \text{HCF}(77, 55) \).

2. Next, divide 77 by 55:
\[ 77 \div 55 = 1 \quad \text{(quotient)} \quad \text{remainder} = 77 - 55 \times 1 = 77 - 55 = 22 \] So, \( 77 \mod 55 = 22 \). Now, we find \( \text{HCF}(55, 22) \).

3. Now, divide 55 by 22:
\[ 55 \div 22 = 2 \quad \text{(quotient)} \quad \text{remainder} = 55 - 22 \times 2 = 55 - 44 = 11 \] So, \( 55 \mod 22 = 11 \). Now, we find \( \text{HCF}(22, 11) \).

4. Finally, divide 22 by 11:
\[ 22 \div 11 = 2 \quad \text{(quotient)} \quad \text{remainder} = 22 - 11 \times 2 = 22 - 22 = 0 \] Since the remainder is 0, the divisor at this step, 11, is the HCF.

Step 4: Conclusion:
The HCF of 132 and 77 is 11.