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. /Counting and adding the divisors

Course 27.2·Lesson 3 of 3

Counting and adding the divisors

If n=p1a1⋯pkakn = p_1^{a_1} \cdots p_k^{a_k}n=p1a1​​⋯pkak​​

Lesson 3 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

  • count the divisors of a number, and the divisors with a given property, from its factorisation;
  • add the divisors with the formula for σ(n)\sigma(n)σ(n);
  • use the pairing of divisors, and prove Euclid's rule for even perfect numbers.

How many ways to make a rectangle?

You have 504504504 unit squares and want to arrange them in a rectangle. Each rectangle needs a width that divides 504504504. How many widths are there? Listing them takes a while. A formula takes a second.

The number of divisors

Write 504=23⋅32⋅7504 = 2^3 \cdot 3^2 \cdot 7504=23⋅32⋅7. By the fundamental theorem, every divisor is 2i⋅3j⋅7k2^i \cdot 3^j \cdot 7^k2i⋅3j⋅7k with

0≤i≤3,0≤j≤2,0≤k≤1.\displaystyle 0 \le i \le 3, \qquad 0 \le j \le 2, \qquad 0 \le k \le 1.0≤i≤3,0≤j≤2,0≤k≤1.

Each choice gives a different divisor. There are 4×3×2=244 \times 3 \times 2 = 244×3×2=24 choices.

![A grid of the 24 divisors of 504 = 2 cubed times 3 squared times 7. The columns are the powers of 2 (1, 2, 4, 8), the rows are the powers of 3 (1, 3, 9), and the grid appears twice, once without the factor 7 and once with it. Each cell holds the product, for example 8 times 9 times 7 = 504 in the last cell. A caption says 4 times 3 times 2 = 24 divisors.](https://tuygolavdykfydmasiqc.supabase.co/storage/v1/object/public/discussion-images/57b80fd5-0d05-40b0-bb7c-fdadd190c00d/figures/ch27-number-theory-divisibility-and-primes/nt-n2-divisors.png) In general, for n=p1a1p2a2⋯pkakn = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}n=p1a1​​p2a2​​⋯pkak​​,

τ(n)=(a1+1)(a2+1)⋯(ak+1).\displaystyle \tau(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1).τ(n)=(a1​+1)(a2​+1)⋯(ak​+1).

The Greek letter τ\tauτ (tau) is the usual name. Many books write d(n)d(n)d(n) instead, and some write σ0(n)\sigma_0(n)σ0​(n).

Divisors with a property. Restrict the exponents.

  • Even divisors of 504: i≥1i \ge 1i≥1, so 3×3×2=183 \times 3 \times 2 = 183×3×2=18.
  • Odd divisors: i=0i = 0i=0, so 1×3×2=61 \times 3 \times 2 = 61×3×2=6.
  • Square divisors: all exponents even: i∈{0,2}i \in \{0, 2\}i∈{0,2}, j∈{0,2}j \in \{0, 2\}j∈{0,2}, k=0k = 0k=0, so 2×2×1=42 \times 2 \times 1 = 42×2×1=4.

The sum of the divisors

Expand this product:

(1+2+4+8)(1+3+9)(1+7).\displaystyle (1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 7).(1+2+4+8)(1+3+9)(1+7).

Each term of the expansion picks one power of each prime, so each term is one divisor of 504504504, and each divisor appears once. So the product is the sum of all divisors: 15×13×8=156015 \times 13 \times 8 = 156015×13×8=1560. With the sum of a geometric series,

σ(n)=p1a1+1−1p1−1⋅p2a2+1−1p2−1⋯pkak+1−1pk−1.\displaystyle \sigma(n) = \frac{p_1^{a_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{a_2 + 1} - 1}{p_2 - 1} \cdots \frac{p_k^{a_k + 1} - 1}{p_k - 1}.σ(n)=p1​−1p1a1​+1​−1​⋅p2​−1p2a2​+1​−1​⋯pk​−1pkak​+1​−1​.

Multiplicative. If gcd⁡(m,n)=1\gcd(m, n) = 1gcd(m,n)=1, then τ(mn)=τ(m)τ(n)\tau(mn) = \tau(m)\tau(n)τ(mn)=τ(m)τ(n) and σ(mn)=σ(m)σ(n)\sigma(mn) = \sigma(m)\sigma(n)σ(mn)=σ(m)σ(n). The primes of mmm and of nnn do not mix. For numbers that share a prime it fails: τ(2×2)=3\tau(2 \times 2) = 3τ(2×2)=3, but τ(2)τ(2)=4\tau(2)\tau(2) = 4τ(2)τ(2)=4.

Divisors come in pairs

If d∣nd \mid nd∣n, then nd∣n\tfrac{n}{d} \mid ndn​∣n as well. Pair each divisor with its partner. For n=36n = 36n=36: 111 with 363636, 222 with 181818, 333 with 121212, 444 with 999, and 666 with itself.

  • A divisor is its own partner only when d2=nd^2 = nd2=n. So τ(n)\tau(n)τ(n) is odd exactly when nnn is a perfect square. You can also see it from the formula: all the ai+1a_i + 1ai​+1 are odd exactly when all the aia_iai​ are even.
  • Multiplying each pair gives nnn. So the product of all the divisors of nnn is nτ(n)/2n^{\tau(n)/2}nτ(n)/2.
  • In each pair one divisor is at most n\sqrt{n}n​. So τ(n)≤2n\tau(n) \le 2\sqrt{n}τ(n)≤2n​.

Perfect numbers

The Greeks called a number perfect when it equals the sum of its divisors other than itself. For example 6=1+2+36 = 1 + 2 + 36=1+2+3 and 28=1+2+4+7+1428 = 1 + 2 + 4 + 7 + 1428=1+2+4+7+14. In symbols, σ(n)=2n\sigma(n) = 2nσ(n)=2n. The next ones are 496496496 and 812881288128.

Euclid's rule. If 2p−12^p - 12p−1 is prime, then n=2p−1(2p−1)n = 2^{p-1}(2^p - 1)n=2p−1(2p−1) is perfect.

Proof. Put q=2p−1q = 2^p - 1q=2p−1, a prime, so qqq is odd and coprime to 2p−12^{p-1}2p−1. Then

σ(n)=σ(2p−1) σ(q)=(2p−1)(q+1)=q⋅2p=2n.\displaystyle \sigma(n) = \sigma(2^{p-1})\,\sigma(q) = (2^p - 1)(q + 1) = q \cdot 2^p = 2n.σ(n)=σ(2p−1)σ(q)=(2p−1)(q+1)=q⋅2p=2n.

Proof complete. About two thousand years later Euler proved the converse: every even perfect number has this form. Nobody knows whether an odd perfect number exists. It is one of the oldest open questions in mathematics.

By the problem on Mersenne numbers in course 1, 2p−12^p - 12p−1 can be prime only when ppp is prime. The primes 2p−12^p - 12p−1 are the Mersenne primes, and each gives one even perfect number.

Practise with new numbers

Try it in Python

The program lists the divisors of 504504504 in pairs, compares the count and the sum with the formulas, and searches for perfect numbers below 100001000010000.

Read it first. Then run it. Do the formulas agree with the list?

1. Change n = 504 to a perfect square such as n = 900. Is the number of divisors odd?

2. Change the search to find numbers with sum(divisors(m)) == 3 * m. Which ones appear below 100001000010000?

Common mistakes

  • Multiplying the exponents. τ(23⋅32)=4×3=12\tau(2^3 \cdot 3^2) = 4 \times 3 = 12τ(23⋅32)=4×3=12, not 3×2=63 \times 2 = 63×2=6. Each exponent can also be 000.
  • Forgetting 1 and n. Both are divisors, and the formula counts them.
  • Using the multiplicative rule for numbers that share a prime.
  • Thinking every 2p−1(2p−1)2^{p-1}(2^p - 1)2p−1(2p−1) is perfect. It needs 2p−12^p - 12p−1 to be prime. For p=11p = 11p=11 it is not.

Remember these

  • τ(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​.
  • To count divisors with a property, restrict the exponents.
  • τ(n)\tau(n)τ(n) is odd exactly when nnn is a square.
  • The product of the divisors of nnn is nτ(n)/2n^{\tau(n)/2}nτ(n)/2.
  • 2p−1(2p−1)2^{p-1}(2^p - 1)2p−1(2p−1) is perfect when 2p−12^p - 12p−1 is prime, and every even perfect number has this form.

Check yourself

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

  1. How many divisors does 25⋅33⋅1122^5 \cdot 3^3 \cdot 11^225⋅33⋅112 have?
  1. Find the sum of the divisors of 392392392.
  1. How many divisors of 24⋅362^4 \cdot 3^624⋅36 are perfect cubes?
  1. Which whole numbers have exactly 333 divisors?
  1. Check that 28=22(23−1)28 = 2^2(2^3 - 1)28=22(23−1) is perfect with the formula for σ\sigmaσ.

References

  • David M. Burton, Elementary Number Theory, Chapter 6, section 6.1 on the number and the sum of the divisors, and Chapter 11 on perfect numbers.
  • Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory of Numbers, Chapter 4 on arithmetic functions.

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)

A designer wants to tile a rectangle of area 1800 square centimetres with a whole number of rows…Hard · High School (11–12) · by StemPy Lab
A school corridor has 1000 lockers, numbered 1 to 1000, all closed…Advanced · High School (11–12) · by StemPy Lab
A number is perfect when σ(n) = 2n. Prove that if 2ᵖ - 1 is prime, then 2ᵖ⁻¹(2ᵖ - 1) is perfect…Advanced · High School (11–12) · by StemPy Lab
That was the last lessonBack to the course: take the test
← Common Factors, the Euclidean Algorithm and Divisors
← The Euclidean algorithm and Bezout's identityNext →

Discussion (0)

Log in to join the discussion.

Loading…

, then
nnn
has
τ(n)=(a1+1)⋯(ak+1)\tau(n) = (a_1 + 1) \cdots (a_k + 1)τ(n)=(a1​+1)⋯(ak​+1)
positive divisors, and their sum is
σ(n)=∏piai+1−1pi−1\sigma(n) = \prod \dfrac{p_i^{a_i + 1} - 1}{p_i - 1}σ(n)=∏pi​−1piai​+1​−1​
. Divisors come in pairs
ddd
and
n/dn/dn/d
, so
τ(n)\tau(n)τ(n)
is odd exactly for squares. A number is perfect when
σ(n)=2n\sigma(n) = 2nσ(n)=2n
, and the even perfect numbers are the numbers
2p−1(2p−1)2^{p-1}(2^p - 1)2p−1(2p−1)
with
2p−12^p - 12p−1
prime.
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

Python Labs (1)

Counting and adding divisorsPython Lab · by StemPy Lab

Question Sets (1)

Common Factors and Divisors: Concept Check10 questions · by StemPy Lab

Notes (1)

Common Factors, the Euclidean Algorithm and Divisors: Quick RevisionNote · by StemPy Lab