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
  1. Notes
  2. /Common Factors, the Euclidean Algorithm and Divisors: Quick Revision
Mathematics

Common Factors, the Euclidean Algorithm and Divisors: Quick Revision

A brief note on the HCF and the LCM, the Euclidean algorithm, Bezout's identity and the number and sum of divisors. It lists the usual slips and gives questions to check yourself.

StemPy LabWritten by StemPy Lab
Log in to save

A brief note on Common Factors, the Euclidean Algorithm and Divisors. Try each question before you open its answer.

The key facts

  • HCF and LCM: smaller and larger exponent of each prime.
  • Product rule: gcd⁡(a,b)⋅lcm⁡(a,b)=ab\gcd(a, b) \cdot \operatorname{lcm}(a, b) = abgcd(a,b)⋅lcm(a,b)=ab, for two numbers only.
  • Subtracting: gcd⁡(a,b)=gcd⁡(a−kb,b)\gcd(a, b) = \gcd(a - kb, b)gcd(a,b)=gcd(a−kb,b).
  • Coprime form: a=dxa = dxa=dx, b=dyb = dyb=dy with gcd⁡(x,y)=1\gcd(x, y) = 1gcd(x,y)=1.
  • Euclidean algorithm: gcd⁡(a,b)=gcd⁡(b,r)\gcd(a, b) = \gcd(b, r)gcd(a,b)=gcd(b,r); the HCF is the last non-zero remainder.
  • Bezout: ax+by=gcd⁡(a,b)ax + by = \gcd(a, b)ax+by=gcd(a,b) has integer solutions; ax+by=cax + by = cax+by=c is solvable exactly when gcd⁡(a,b)∣c\gcd(a, b) \mid cgcd(a,b)∣c.
  • Euclid's lemma: p∣abp \mid abp∣ab gives p∣ap \mid ap∣a or p∣bp \mid bp∣b.
  • Divisors: τ(n)=∏(ai+1)\tau(n) = \prod (a_i + 1)τ(n)=∏(ai​+1) and σ(n)=∏piai+1−1pi−1\sigma(n) = \prod \dfrac{p_i^{a_i + 1} - 1}{p_i - 1}σ(n)=∏pi​−1piai​+1​−1​.
  • Pairs: τ(n)\tau(n)τ(n) is odd only for squares; the product of the divisors is nτ(n)/2n^{\tau(n)/2}nτ(n)/2.
  • Perfect: 2p−1(2p−1)2^{p-1}(2^p - 1)2p−1(2p−1) with 2p−12^p - 12p−1 prime.

Practise with new numbers

A program to try

The program checks the product rule, searches for Bezout's xxx and yyy, and counts divisors from a list.

Read it first. Then run it. Does the count of divisors match the formula?

1. Change a, b = 84, 132 to two coprime numbers. What HCF and what pair (x,y)(x, y)(x,y) do you get?

Mistakes to avoid

  • The product rule for three numbers. It does not hold.
  • Stopping the algorithm early. Go on until a remainder is 000.
  • Expecting Bezout's xxx and yyy to be unique or positive.
  • Multiplying exponents instead of exponents plus one.
  • Assuming every 2p−1(2p−1)2^{p-1}(2^p - 1)2p−1(2p−1) is perfect. It needs 2p−12^p - 12p−1 prime.

Check yourself

  1. Find gcd⁡(84,132)\gcd(84, 132)gcd(84,132) by the Euclidean algorithm.
  1. Two numbers have HCF 777 and product 176417641764. Find their LCM.
  1. Is 10x+14y=510x + 14y = 510x+14y=5 solvable in integers?
  1. How many divisors does 24⋅532^4 \cdot 5^324⋅53 have, and what is their sum?
  1. Which numbers below 505050 have an odd number of divisors?

Sources

  • David M. Burton, Elementary Number Theory, Chapter 2 and Chapter 6.
  • Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory of Numbers, Chapters 1 and 4.
← All Notes
← Division, Divisibility Rules and Primes: Quick RevisionFactorials, Irrational Numbers, Digits and the Floor Function: Quick Revision →
More onNumber Theory

Discussion (0)

Log in to join the discussion.

Loading…

On this page

  1. The key facts
  2. Practise with new numbers
  3. A program to try
  4. Mistakes to avoid
  5. Check yourself
  6. Sources

Goes with the lesson

  1. Counting and adding the divisorsCommon Factors, the Euclidean Algorithm and Divisors

More notes on this topic

  1. Diophantine Equations and Pythagorean Triples: Quick Revision
  • Fermat, Euler and Wilson: Quick Revision
  • Congruences and the Chinese Remainder Theorem: Quick Revision
  • Factorials, Irrational Numbers, Digits and the Floor Function: Quick Revision
  • Division, Divisibility Rules and Primes: Quick Revision
  • All notes on this topic →