HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Common Factors, the Euclidean Algorithm and Divisors
  1. 1The highest common factor and the least common multiple
  2. 2The Euclidean algorithm and Bezout's identity
  3. 3Counting and adding the divisors
  1. Mathematics
  2. /Common Factors, the Euclidean Algorithm and Divisors
  3. /The highest common factor and the least common multiple

Course 27.2·Lesson 1 of 3

The highest common factor and the least common multiple

The highest common factor (HCF, also called the greatest common divisor, gcd⁡\gcdgcd) 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\gcd(a, b) \cdot \operatorname{lcm}(a, b) = abgcd(a,b)⋅lcm(a,b)=ab

Lesson 1 of 3Show all lessonsHide
Common Factors, the Euclidean Algorithm and Divisors
  1. 1The highest common factor and the least common multiple
  2. 2The Euclidean algorithm and Bezout's identity
  3. 3

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\gcd(a, b) \cdot \operatorname{lcm}(a, b) = abgcd(a,b)⋅lcm(a,b)=ab;
  • use the rules gcd⁡(a,b)=gcd⁡(a−kb,b)\gcd(a, b) = \gcd(a - kb, b)gcd(a,b)=gcd(a−kb,b) and gcd⁡(ka,kb)=kgcd⁡(a,b)\gcd(ka, kb) = k \gcd(a, b)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 252252252 cm long and 198198198 cm wide. You want square tiles, all the same size, that cover it exactly. The side of the tile must divide both 252252252 and 198198198. The largest such side is the highest common factor.

Two buses leave a station together. One returns every 121212 minutes and the other every 181818 minutes. They next leave together after a time that both 121212 and 181818 divide. The smallest such time is the least common multiple, here 363636 minutes.

The words and the symbols

For integers aaa and bbb, not both 000:

  • gcd⁡(a,b)\gcd(a, b)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)(a, b)(a,b).
  • lcm⁡(a,b)\operatorname{lcm}(a, b)lcm(a,b) is the smallest positive integer that is a multiple of both, for a,b≠0a, b \ne 0a,b=0. Some books write [a,b][a, b][a,b].
  • aaa and bbb are coprime (or relatively prime) when gcd⁡(a,b)=1\gcd(a, b) = 1gcd(a,b)=1. For example 888 and 151515 are coprime, though neither is prime.

From the prime factorisations

Write both numbers with the same primes, allowing exponent 000. A divisor of a=∏pαa = \prod p^{\alpha}a=∏pα is a product ∏pδ\prod p^{\delta}∏pδ with each δ≤α\delta \le \alphaδ≤α. 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⁡(α,β).\displaystyle \gcd(a, b) = \prod p^{\min(\alpha, \beta)}, \qquad \operatorname{lcm}(a, b) = \prod p^{\max(\alpha, \beta)}.gcd(a,b)=∏pmin(α,β),lcm(a,b)=∏pmax(α,β).

For the hall: 252=22⋅32⋅7252 = 2^2 \cdot 3^2 \cdot 7252=22⋅32⋅7 and 198=2⋅32⋅11198 = 2 \cdot 3^2 \cdot 11198=2⋅32⋅11. So gcd⁡=2⋅32=18\gcd = 2 \cdot 3^2 = 18gcd=2⋅32=18 and lcm⁡=22⋅32⋅7⋅11=2772\operatorname{lcm} = 2^2 \cdot 3^2 \cdot 7 \cdot 11 = 2772lcm=22⋅32⋅7⋅11=2772. The tiles have a side of 181818 cm.

The product rule. For each prime, min⁡(α,β)+max⁡(α,β)=α+β\min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \betamin(α,β)+max(α,β)=α+β. Multiply over all primes:

gcd⁡(a,b)⋅lcm⁡(a,b)=ab(a,b>0).\displaystyle \gcd(a, b) \cdot \operatorname{lcm}(a, b) = ab \quad (a, b > 0).gcd(a,b)⋅lcm(a,b)=ab(a,b>0).

Check: 18×2772=49896=252×19818 \times 2772 = 49896 = 252 \times 19818×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\gcd(2, 4, 6) \cdot \operatorname{lcm}(2, 4, 6) = 2 \times 12 = 24gcd(2,4,6)⋅lcm(2,4,6)=2×12=24, but 2×4×6=482 \times 4 \times 6 = 482×4×6=48.

Rules that do not need the factorisation

Factorising a large number is slow. These rules avoid it.

  1. Subtracting. gcd⁡(a,b)=gcd⁡(a−kb,b)\gcd(a, b) = \gcd(a - kb, b)gcd(a,b)=gcd(a−kb,b) for any integer kkk. A number divides aaa and bbb exactly when it divides a−kba - kba−kb and bbb, by the rule for combinations. So the two pairs have the same common divisors.
  2. Scaling. gcd⁡(ka,kb)=kgcd⁡(a,b)\gcd(ka, kb) = k\gcd(a, b)gcd(ka,kb)=kgcd(a,b) for k>0k > 0k>0.
  3. Dividing out. If d=gcd⁡(a,b)d = \gcd(a, b)d=gcd(a,b), then gcd⁡(ad,bd)=1\gcd\big(\tfrac{a}{d}, \tfrac{b}{d}\big) = 1gcd(da​,db​)=1. So any two numbers are a=dxa = dxa=dx and b=dyb = dyb=dy with xxx and yyy coprime. Then lcm⁡(a,b)=dxy\operatorname{lcm}(a, b) = dxylcm(a,b)=dxy.
  4. Coprime divisors. If a∣na \mid na∣n and b∣nb \mid nb∣n and gcd⁡(a,b)=1\gcd(a, b) = 1gcd(a,b)=1, then ab∣nab \mid nab∣n. This is the fact we used in course 1 to join two divisibility rules.
  5. Coprime factor. If a∣bca \mid bca∣bc and gcd⁡(a,b)=1\gcd(a, b) = 1gcd(a,b)=1, then a∣ca \mid ca∣c. No prime of aaa is in bbb, so all of aaa sits inside ccc.

Which values can an HCF take?

Olympiads like questions such as this one. What are the possible values of gcd⁡(n+1,n2+1)\gcd(n + 1, n^2 + 1)gcd(n+1,n2+1), as nnn runs over the integers?

  1. Reduce. n2+1=(n+1)(n−1)+2n^2 + 1 = (n + 1)(n - 1) + 2n2+1=(n+1)(n−1)+2. By rule 1, gcd⁡(n+1,n2+1)=gcd⁡(n+1,2)\gcd(n + 1, n^2 + 1) = \gcd(n + 1, 2)gcd(n+1,n2+1)=gcd(n+1,2).
  2. Read it off. That is 222 when nnn is odd and 111 when nnn is even.

So the HCF is always 111 or 222, 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.

Read it first. Then run it. Do the two methods agree?

1. Change a, b = 252, 198 to two numbers of your own. Predict the HCF from the factorisations first.

2. Write a test for three numbers: is math.gcd(x, y, z) * math.lcm(x, y, z) == x * y * z true for all of them? Find a pair of cases that disagree.

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. 888 and 151515 are coprime and both composite.
  • Writing gcd⁡(a,b)=gcd⁡(a+b,b)\gcd(a, b) = \gcd(a + b, b)gcd(a,b)=gcd(a+b,b) as gcd⁡(a,b)=gcd⁡(a+b,a−b)\gcd(a, b) = \gcd(a + b, a - b)gcd(a,b)=gcd(a+b,a−b). The second one can differ: gcd⁡(3,5)=1\gcd(3, 5) = 1gcd(3,5)=1 but gcd⁡(8,2)=2\gcd(8, 2) = 2gcd(8,2)=2.

Remember these

  • gcd⁡\gcdgcd takes the smaller exponents, lcm⁡\operatorname{lcm}lcm the larger.
  • gcd⁡(a,b)⋅lcm⁡(a,b)=ab\gcd(a, b) \cdot \operatorname{lcm}(a, b) = abgcd(a,b)⋅lcm(a,b)=ab for two positive numbers.
  • gcd⁡(a,b)=gcd⁡(a−kb,b)\gcd(a, b) = \gcd(a - kb, b)gcd(a,b)=gcd(a−kb,b).
  • a=dxa = dxa=dx, b=dyb = dyb=dy with gcd⁡(x,y)=1\gcd(x, y) = 1gcd(x,y)=1, and then lcm⁡(a,b)=dxy\operatorname{lcm}(a, b) = dxylcm(a,b)=dxy.
  • If a∣bca \mid bca∣bc and gcd⁡(a,b)=1\gcd(a, b) = 1gcd(a,b)=1, then a∣ca \mid ca∣c.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. Find gcd⁡(315,294)\gcd(315, 294)gcd(315,294) and lcm⁡(315,294)\operatorname{lcm}(315, 294)lcm(315,294) from the factorisations.
  1. Two numbers have HCF 141414 and LCM 420420420. One of them is 707070. Find the other.
  1. Show that gcd⁡(n,n+1)=1\gcd(n, n + 1) = 1gcd(n,n+1)=1 for every integer nnn.
  1. Which values can gcd⁡(n+3,n2+2)\gcd(n + 3, n^2 + 2)gcd(n+3,n2+2) take?
  1. Can two numbers have HCF 666 and LCM 100100100?

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.
No payment. You can leave at any time.

Problems (3)

Two positive whole numbers a < b have the sum a + b = 96 and the least common multiple lcm(a, b) =…Advanced · High School (11–12) · by StemPy Lab
Let dn = gcd(n² + 3, n + 2) for positive whole numbers n…Hard · High School (11–12) · by StemPy Lab
For two numbers, gcd · lcm equals the product…Advanced · High School (11–12) · by StemPy Lab
Next: lesson 2The Euclidean algorithm and Bezout's identity
← Common Factors, the Euclidean Algorithm and Divisors
← PreviousThe Euclidean algorithm and Bezout's identity →

Discussion (0)

Log in to join the discussion.

Loading…

.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

Counting and adding the divisors