Question

The HCF of 96 and 404 is :

• A. 2
• B. 4
• C. 8
• D. 16

Hint:

To find HCF (Highest Common Factor): {Prime Factorization Method:} 1. Find prime factors of each number: \(96 = 2 \times 2 \times 2 \times 2 \times 2 \times 3 = 2^5 \times 3\) \(404 = 2 \times 2 \times 101 = 2^2 \times 101\) 2. Identify common prime factors: Only 2 is common. 3. Take the lowest power of each common prime factor: Lowest power of 2 is \(2^2\). 4. HCF = \(2^2 = 4\). {Euclidean Algorithm:} Repeatedly divide and use remainders until remainder is 0. The last non-zero remainder is HCF.

Answer 1

The Correct Option is B

Concept: The Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), of two or more integers is the largest positive integer that divides each of the integers without a remainder. We can find the HCF using prime factorization or the Euclidean algorithm. Method 1: Prime Factorization Step 1: Find the prime factorization of 96 \[ 96 = 2 \times 48 \] \[ = 2 \times 2 \times 24 \] \[ = 2 \times 2 \times 2 \times 12 \] \[ = 2 \times 2 \times 2 \times 2 \times 6 \] \[ = 2 \times 2 \times 2 \times 2 \times 2 \times 3 \] \[ 96 = 2^5 \times 3^1 \] Step 2: Find the prime factorization of 404 \[ 404 = 2 \times 202 \] \[ = 2 \times 2 \times 101 \] Since 101 is a prime number (it is not divisible by any prime numbers less than or equal to \(\sqrt{101} \approx 10\), i.e., 2, 3, 5, 7), \[ 404 = 2^2 \times 101^1 \] Step 3: Identify common prime factors and their lowest powers The common prime factor is 2. The lowest power of 2 present in both factorizations is \(2^2\). (3 is a factor of 96 but not 404. 101 is a factor of 404 but not 96). Step 4: Calculate the HCF HCF = Product of common prime factors raised to their lowest powers. HCF = \(2^2 = 4\). Method 2: Euclidean Algorithm Step 1: Divide the larger number by the smaller number and find the remainder. \(404 \div 96\) \(404 = 96 \times 4 + 20\) (Since \(96 \times 4 = 384\), remainder is \(404 - 384 = 20\)) Step 2: Replace the larger number with the smaller number and the smaller number with the remainder, and repeat the division. Now divide 96 by 20. \(96 = 20 \times 4 + 16\) Step 3: Repeat the process. Now divide 20 by 16. \(20 = 16 \times 1 + 4\) Step 4: Repeat the process. Now divide 16 by 4. \(16 = 4 \times 4 + 0\) The last non-zero remainder is the HCF. HCF = 4. Both methods give HCF = 4. This matches option (2).