Number theory path · N06

Before this lesson: Unique prime factorisation, Basic counting principles

Your goal: Translate divisor questions into independent choices of prime exponents.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Names you may know: divisor-counting function; sum-of-divisors function.

Number and Sum of Divisors: the key idea

If n=p1e1⋯pkekn=p_{1}^{e_{1}}\cdots p_{k}^{e_{k}}, each positive divisor independently chooses the exponent of pᵢ from 0 to eᵢ. Thus τ(n)=∏(ei+1)\tau (n)=\prod (e_{i}+1). Summing the same choices gives σ(n)=∏(1+pi+⋯+piei)\sigma (n)=\prod (1+p_{i}+\cdots +p_{i}^{e_{i}}). Divisors pair as d and n/d, giving product nτ(n)/2n^{\tau(n)/2}; when n is a square its central divisor n\sqrt{n} pairs with itself. An integer is perfect when the sum of its positive proper divisors equals itself, equivalently σ(n)=2n. These formulas work for n=1 with the empty-product convention τ(1)=σ(1)=1.

A worked example

Find the number and sum of positive divisors of 12.

12=2²·3. The number is (2+1)(1+1)=6. The sum is (1+2+4)(1+3)=7·4=28. The divisors 1,2,3,4,6,12 confirm both results.

Your turn: change one thing

How many positive divisors does 360 have?

Try this on paper before opening the explanation.

Compare your reasoning

360=2³3²5, so τ(360)=4·3·2=24.

Pause and check

A trap to avoid: Omitting the exponent-zero choice or double-counting the square-root divisor.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Prove an integer has an odd number of positive divisors exactly when it is a square.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

The formula τ(n)=∏(ei+1)\tau (n)=\prod (e_{i}+1) is odd exactly when every factor eᵢ+1 is odd, or equivalently every exponent eᵢ is even. Unique prime factorisation identifies this condition with n being a square. The case n=1 also satisfies both properties.

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. For n=paqbn=p^{a}q^{b} with distinct primes, τ(n) equals what?

Foundation

  1. (a+1)(b+1)
  2. ab
  3. a+b
  4. p+q
Hint

Choose each exponent independently.

Answer and reasoning

(a+1)(b+1). There are a+1 choices for p and b+1 for q.

2. A perfect number satisfies which equation?

Foundation

  1. σ(n)=n
  2. n is prime
  3. σ(n)=2n
  4. τ(n)=n
Hint

Include n itself in the divisor sum.

Answer and reasoning

σ(n)=2n. Proper divisors sum to n, so all positive divisors sum to 2n.

3. How many positive divisors does 12 have?

Core

  1. 5
  2. 12
  3. 6
  4. 4
Hint

12=2²3.

Answer and reasoning

6. (2+1)(1+1)=6.

4. What is σ(12)?

Core

  1. 16
  2. 24
  3. 28
  4. 12
Hint

Multiply geometric sums.

Answer and reasoning

28. (1+2+4)(1+3)=28.

5. An odd divisor count characterises what?

Stretch

  1. Perfect numbers
  2. Perfect squares
  3. Primes
  4. Even numbers
Hint

Each eᵢ+1 must be odd.

Answer and reasoning

Perfect squares. All prime exponents are even exactly for squares.

6. Why is 6 perfect?

Stretch

  1. It is prime
  2. σ(6)=6
  3. 1+2+3=6
  4. It has six divisors
Hint

List the proper positive divisors.

Answer and reasoning

1+2+3=6. The proper divisors are 1,2,3 and they sum to 6.

7. What is τ(1)?

Foundation

  1. 0
  2. 2
  3. Undefined
  4. 1
Hint

List the positive divisors of 1.

Answer and reasoning

1. Only 1 divides 1 positively.

8. How many positive divisors does 72 have?

Core

  1. 12
  2. 9
  3. 10
  4. 18
Hint

72=2³3².

Answer and reasoning

12. (3+1)(2+1)=12.

9. Why do divisors pair as d and n/d?

Stretch

  1. They must always be distinct
  2. Both must be prime
  3. Their sum is n
  4. Both are integer divisors and their product is n
Hint

Use the defining divisibility relation.

Answer and reasoning

Both are integer divisors and their product is n. The map d↦n/d is an involution on positive divisors; only n\sqrt{n} can pair with itself.

Choose your next step

Continue to Modular arithmetic and congruences. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.