The highest common factor and the least common multiple
The highest common factor (HCF, also called the greatest common divisor, gcd) of two numbers is the largest number that divides both. The least common multiple (LCM) is the smallest positive number that both divide. From the prime factorisations, the HCF takes the smaller exponent of each prime and the LCM the larger, so gcd(a,b)⋅lcm(a,b)=ab
Lesson 1 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
find the HCF and the LCM from prime factorisations, and prove gcd(a,b)⋅lcm(a,b)=ab;
use the rules gcd(a,b)=gcd(a−kb,b) and gcd(ka,kb)=kgcd(a,b);
work with coprime numbers and decide which values an HCF of two expressions can take.
Tiles and timetables
A hall floor is 252 cm long and 198 cm wide. You want square tiles, all the same size, that cover it exactly. The side of the tile must divide both 252 and 198. The largest such side is the highest common factor.
Two buses leave a station together. One returns every 12 minutes and the other every 18 minutes. They next leave together after a time that both 12 and 18 divide. The smallest such time is the least common multiple, here 36 minutes.
The words and the symbols
For integers a and b, not both 0:
gcd(a,b) is the largest integer that divides both. India's school books call it the HCF. Many books write it as (a,b).
lcm(a,b) is the smallest positive integer that is a multiple of both, for a,b=0. Some books write [a,b].
a and b are coprime (or relatively prime) when gcd(a,b)=1. For example 8 and 15 are coprime, though neither is prime.
From the prime factorisations
Write both numbers with the same primes, allowing exponent 0. A divisor of a=∏pα is a product ∏pδ with each δ≤α. So a common divisor has each exponent at most the smaller of the two. Similarly, a common multiple has each exponent at least the larger:
gcd(a,b)=∏pmin(α,β),lcm(a,b)=∏pmax(α,β).
For the hall: 252=22⋅32⋅7 and 198=2⋅32⋅11. So gcd=2⋅32=18 and lcm=22⋅32⋅7⋅11=2772. The tiles have a side of 18 cm.
The product rule. For each prime, min(α,β)+max(α,β)=α+β. Multiply over all primes:
gcd(a,b)⋅lcm(a,b)=ab(a,b>0).
Check: 18×2772=49896=252×198.
Three numbers. The HCF and LCM of three numbers use the smallest and largest of three exponents. The product rule does not carry over: gcd(2,4,6)⋅lcm(2,4,6)=2×12=24, but 2×4×6=48.
Rules that do not need the factorisation
Factorising a large number is slow. These rules avoid it.
Subtracting.gcd(a,b)=gcd(a−kb,b) for any integer k. A number divides a and b exactly when it divides a−kb and b, by the rule for combinations. So the two pairs have the same common divisors.
Scaling.gcd(ka,kb)=kgcd(a,b) for k>0.
Dividing out. If d=gcd(a,b), then gcd(da,db)=1. So any two numbers are a=dx and b=dy with x and y coprime. Then lcm(a,b)=dxy.
Coprime divisors. If a∣n and b∣n and gcd(a,b)=1, then ab∣n. This is the fact we used in course 1 to join two divisibility rules.
Coprime factor. If a∣bc and gcd(a,b)=1, then a∣c. No prime of a is in b, so all of a sits inside c.
Which values can an HCF take?
Olympiads like questions such as this one. What are the possible values of gcd(n+1,n2+1), as n runs over the integers?
Reduce.n2+1=(n+1)(n−1)+2. By rule 1, gcd(n+1,n2+1)=gcd(n+1,2).
Read it off. That is 2 when n is odd and 1 when n is even.
So the HCF is always 1 or 2, and both happen. The trick is to remove multiples of one expression from the other until a constant is left.
Practise with new numbers
Try it in Python
The program finds the HCF and the LCM from prime factorisations and compares them with Python's own math.gcd and math.lcm. Then it tests the product rule on ninety thousand pairs.
Common mistakes
Mixing up min and max. The HCF takes the smaller exponent, the LCM the larger one.
Using the product rule for three numbers. It holds for two numbers only.
Calling coprime numbers prime.8 and 15 are coprime and both composite.
Writing gcd(a,b)=gcd(a+b,b) as gcd(a,b)=gcd(a+b,a−b). The second one can differ: gcd(3,5)=1 but gcd(8,2)=2.
Remember these
gcd takes the smaller exponents, lcm the larger.
gcd(a,b)⋅lcm(a,b)=ab for two positive numbers.
gcd(a,b)=gcd(a−kb,b).
a=dx, b=dy with gcd(x,y)=1, and then lcm(a,b)=dxy.
If a∣bc and gcd(a,b)=1, then a∣c.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Find gcd(315,294) and lcm(315,294) from the factorisations.
Two numbers have HCF 14 and LCM 420. One of them is 70. Find the other.
Show that gcd(n,n+1)=1 for every integer n.
Which values can gcd(n+3,n2+2) take?
Can two numbers have HCF 6 and LCM 100?
References
David M. Burton, Elementary Number Theory, Chapter 2, sections 2.3 and 2.4 on the greatest common divisor and the least common multiple.
NCERT, Mathematics Textbook for Class X, Chapter 1 (Real Numbers), for the HCF and the LCM from prime factorisations.
Enroll free in Common Factors, the Euclidean Algorithm and Divisors
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.