The HCF (greatest common divisor, GCD) of integers is the largest integer that divides all of them. You can find it by listing factors, by prime factorization, or most efficiently by the Euclidean algorithm (useful for large numbers).
Explanation
1) Listing factors (simple, for small numbers)
- List all positive divisors of each number and pick the largest common one.
- Example: For 8 and 12, divisors of 8: 1,2,4,8; of 12: 1,2,3,4,6,12 → HCF = 4.
2) Prime factorization (good for moderate-size numbers)
- Factor each number into primes, take each common prime raised to the minimum exponent across the numbers, and multiply those.
- Example: Find HCF of 48 and 180.
- $48 = 2^4 \times 3$
- $180 = 2^2 \times 3^2 \times 5$
- Common primes: $2^{\min(4,2)} = 2^2$ and $3^{\min(1,2)} = 3$
- HCF $=2^2\times3=4\times3=12$
3) Euclidean algorithm (fastest and recommended for large numbers)
- Repeatedly replace the larger number by its remainder when divided by the smaller until remainder is 0; the last nonzero remainder is the GCD.
- Example: GCD(48,180)
- $$180 = 48\times3 + 36$$
- $$48 = 36\times1 + 12$$
- $$36 = 12\times3 + 0$$
- Last nonzero remainder = 12 → HCF = 12
For more than two numbers, compute iteratively: $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$.
Relation with LCM (for two numbers)
- $$\gcd(a,b)\times\operatorname{lcm}(a,b)=|a\times b|$$
- So if you know the LCM, you can get the GCD by $\gcd(a,b)=\dfrac{|a\times b|}{\operatorname{lcm}(a,b)}$.
Quick Python examples
import math
# Using built-in gcd (Python 3.5+)
math.gcd(48, 180) # returns 12
# Euclidean algorithm for multiple numbers
from functools import reduce
def gcd_multiple(nums):
return reduce(math.gcd, nums)
gcd_multiple([24,36,60]) # returns 12
Tips:
- Use Euclidean algorithm for large numbers or programmatic solutions.
- Use prime factorization when you need the common prime structure or for small integers.