Finding HCF of 64 and 148

The Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), is the largest number that divides two or more numbers without leaving a remainder.

We can find the HCF of 64 and 148 using the prime factorization method:

• Step 1: Prime Factorization
  • Find the prime factors of 64: $64 = 2 \times 32 = 2 \times 2 \times 16 = 2 \times 2 \times 2 \times 8 = 2 \times 2 \times 2 \times 2 \times 4 = 2 \times 2 \times 2 \times 2 \times 2 \times 2 = 2^6$
  • Find the prime factors of 148: $148 = 2 \times 74 = 2 \times 2 \times 37 = 2^2 \times 37$
• Step 2: Identify Common Factors
  • The prime factors of 64 are: $2, 2, 2, 2, 2, 2$.
  • The prime factors of 148 are: $2, 2, 37$.
  • The common prime factors are $2$ and $2$.
• Step 3: Calculate HCF
  • Multiply the common prime factors.
  • $HCF = 2 \times 2 = 4$.

Alternatively, using the Euclidean Algorithm:

• Divide 148 by 64: $148 = 2 \times 64 + 20$
• Divide 64 by the remainder 20: $64 = 3 \times 20 + 4$
• Divide 20 by the remainder 4: $20 = 5 \times 4 + 0$
• The last non-zero remainder is the HCF. In this case, it is 4.

Therefore, the highest common factor of 64 and 148 is 4.