Chapter 1: Number Theory
Section 1.1 — Divisibility, Factors & Integer Equations | AIMO Training Programme
Number theory makes up ~32% of all AIMO questions — the single largest topic. This section covers divisibility: the language you need before everything else in number theory.
1. Divisibility Basics
Definition. We say $a$ divides $b$, written $a \mid b$, if there exists an integer $k$ such that $b = ak$.
Equivalently: $b$ is a multiple of $a$, and $a$ is a factor (or divisor) of $b$.
Quick examples: $3 \mid 12$ ($12 = 3 \times 4$), $7 \mid 0$ ($0 = 7 \times 0$), $4 \nmid 10$ .
Theorem (Linear Combination). If $a \mid b$ and $a \mid c$, then for any integers $x, y$:
$$a \mid (bx + cy)$$
Proof: $b = ak_1$, $c = ak_2 \Rightarrow bx + cy = a(k_1 x + k_2 y)$. ∎
Important consequences (use these constantly):
- $a \mid b$ and $a \mid c$ $\Rightarrow$ $a \mid (b \pm c)$
- $a \mid b$ $\Rightarrow$ $a \mid bc$ for any $c$
- $a \mid b$ and $b \mid c$ $\Rightarrow$ $a \mid c$ (transitivity)
- $a \mid b$ and $b \neq 0$ $\Rightarrow$ $|a| \le |b|$
The last point is powerful for bounding. If you know $d \mid n$ and $n \neq 0$, then $d$ can't be bigger than $|n|$. This lets you turn infinite searches into finite ones.
Theorem (Division Algorithm). For any integers $a$ and $b$ with $b > 0$, there exist unique $q$ (quotient) and $r$ (remainder):
$$a = bq + r, \quad 0 \le r < b$$
We write $r = a \bmod b$ or $a \equiv r \pmod{b}$. Modular arithmetic will be covered in depth in Section 1.5.
2. Divisibility Tests
You should know all of these instantly — competition speed matters.
| $n$ | Test | Why it works |
|---|
| 2 | Last digit even | $10 \equiv 0 \pmod{2}$ |
| 3 | Digit sum $\equiv 0 \pmod{3}$ | $10 \equiv 1 \pmod{3}$, so $10^k \equiv 1$ |
| 4 | Last two digits $\equiv 0 \pmod{4}$ | $100 \equiv 0 \pmod{4}$ |
| 5 | Last digit is 0 or 5 | $10 \equiv 0 \pmod{5}$ |
| 6 | Divisible by both 2 and 3 | $6 = 2 \times 3$, coprime |
| 7 | Double last digit, subtract from rest | $21 \equiv 0 \pmod{7}$; uses $10a + b \equiv 0$ |
| 8 | Last three digits $\equiv 0 \pmod{8}$ | $1000 \equiv 0 \pmod{8}$ |
| 9 | Digit sum $\equiv 0 \pmod{9}$ | $10 \equiv 1 \pmod{9}$ |
| 10 | Last digit is 0 | Obvious |
| 11 | Alternating digit sum $\equiv 0 \pmod{11}$ | $10 \equiv -1 \pmod{11}$ |
Example 1 (Quick application). Is $31{,}824$ divisible by 11?
Alternating sum: $3 - 1 + 8 - 2 + 4 = 12$. Since $11 \nmid 12$, no.
What about $31{,}834$? Alternating sum: $3 - 1 + 8 - 3 + 4 = 11$. Yes!
3. Counting & Summing Factors
Theorem. If $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, then:
- Number of divisors: $\tau(n) = (a_1+1)(a_2+1)\cdots(a_k+1)$
- Sum of divisors: $\sigma(n) = \displaystyle\prod_{i=1}^{k} \frac{p_i^{a_i+1}-1}{p_i-1}$
- Product of divisors: $\displaystyle\prod_{d \mid n} d = n^{\tau(n)/2}$
Why $\tau(n)$? Each divisor of $n$ is $p_1^{b_1}\cdots p_k^{b_k}$ with $0 \le b_i \le a_i$. That's $(a_i+1)$ choices per prime.
Example 2. $360 = 2^3 \times 3^2 \times 5$.
$\tau(360) = 4 \times 3 \times 2 = 24$ divisors.
$\sigma(360) = \frac{15}{1} \times \frac{26}{2} \times \frac{24}{4} = 15 \times 13 \times 6 = 1170$.
Example 3. $n = 2^a \times 3^b$ has exactly 12 positive divisors and $a > b > 0$. Find all $n$.
$(a+1)(b+1) = 12$. Since $a > b > 0$: $b \ge 1$ so $b+1 \ge 2$; $a > b$ so $a+1 > b+1$.
Factor pairs of 12 with first > second $\ge 2$: $(6,2)$ and $(4,3)$.
$(a,b) = (5,1) \Rightarrow n = 96$, or $(a,b) = (3,2) \Rightarrow n = 72$.
Competition shortcut: "How many divisors?" questions always reduce to factoring, then multiplying $(a_i+1)$'s. But the reverse — "which numbers have exactly $k$ divisors?" — is more interesting and appears in AIMO. You need to enumerate all ways to write $k$ as an ordered product.
4. Parity Arguments
Parity (odd/even) is the simplest form of divisibility — working mod 2. But it's shockingly powerful in proofs and impossible-to-exist arguments.
Key Facts.
- even ± even = even, odd ± odd = even, even ± odd = odd
- even × anything = even, odd × odd = odd
- $n^2$ is even $\Leftrightarrow$ $n$ is even (contrapositive: $n$ odd $\Rightarrow$ $n^2$ odd)
- If $a + b + c$ is odd, at least one of $a, b, c$ is odd
Example 4. Prove that $\sqrt{2}$ is irrational.
Proof by contradiction. Suppose $\sqrt{2} = p/q$ where $\gcd(p,q) = 1$.
Then $2q^2 = p^2$, so $p^2$ is even, so $p$ is even. Write $p = 2k$.
Then $2q^2 = 4k^2$, so $q^2 = 2k^2$, so $q$ is even.
Both $p$ and $q$ even contradicts $\gcd(p,q) = 1$. ∎
What to notice: The entire proof rests on "$n^2$ even $\Rightarrow$ $n$ even." That's a parity argument.
Example 5. Prove that $n^2 - n$ is always even.
$n^2 - n = n(n-1)$. Among consecutive integers $n$ and $n-1$, one is even. ∎
Extension: $n(n-1)(n-2)$ is always divisible by 6. (Three consecutive integers: one is $\equiv 0 \pmod{2}$, one is $\equiv 0 \pmod{3}$.)
When to use parity.
- Asked "is it possible?" → Check parity first. Many configurations are impossible because the parity doesn't work out.
- Diophantine equations with sums of squares → check whether all terms can match mod 2.
- Tiling/colouring problems → parity is often the key invariant.
5. Simon's Favourite Factoring Trick (SFFT)
Competition Must-Know. Given an equation like $xy + ax + by = c$, add $ab$ to both sides:
$$xy + ax + by + ab = c + ab$$
$$(x+b)(y+a) = c + ab$$
Now you have a product of two factors equal to a constant, and you can enumerate factor pairs.
This trick converts a "hard" two-variable equation into a systematic enumeration. AIMO loves this.
Example 6 (AIMO 2014 Q5 style). Find all pairs of positive integers $(a, b)$ with $\dfrac{1}{a} + \dfrac{1}{b} = \dfrac{1}{20}$.
Multiply through by $20ab$:
$$20b + 20a = ab$$
$$ab - 20a - 20b = 0$$
Add 400 to both sides (SFFT: $(-20)(-20) = 400$):
$$ab - 20a - 20b + 400 = 400$$
$$(a - 20)(b - 20) = 400$$
Now factor $400 = 2^4 \times 5^2$. It has $(4+1)(2+1) = 15$ positive divisors.
We need $a - 20 > 0$ and $b - 20 > 0$ (since $a, b > 0$ and $1/a + 1/b = 1/20$ forces $a, b > 20$).
Factor pairs of 400: $(1,400), (2,200), (4,100), (5,80), (8,50), (10,40), (16,25), (20,20), (25,16), \ldots$
$(a,b)$: $(21, 420), (22, 220), (24, 120), (25, 100), (28, 70), (30, 60), (36, 45), (40, 40)$ and their reverses.
8 unordered pairs (15 ordered pairs if $a \neq b$ counts separately).
Example 7 (AIMO 2016 Q7 adapted). Find all positive integers $n$ such that $n^2 + 2016n$ is a perfect square.
Let $n^2 + 2016n = m^2$ for some non-negative integer $m$.
$$m^2 - n^2 = 2016n$$
$$(m-n)(m+n) = 2016n$$
Since $m > n$ (as $n^2 + 2016n > n^2$), both $m - n$ and $m + n$ are positive.
Let $m - n = d$, so $m = n + d$, and:
$$d(2n + d) = 2016n$$
$$2dn + d^2 = 2016n$$
$$d^2 = n(2016 - 2d)$$
$$n = \frac{d^2}{2016 - 2d}$$
For $n$ to be a positive integer, we need:
- $2016 - 2d > 0 \Rightarrow d < 1008$
- $(2016 - 2d) \mid d^2$
Simplify: $2016 - 2d = 2(1008 - d)$. So $n = \frac{d^2}{2(1008 - d)}$. Need $d$ even (for numerator to be even) or $1008 - d$ to absorb the 2.
Key insight: Factor $2016 = 2^5 \times 3^2 \times 7$. Systematically check divisors of $2016$ for $d$, or use the substitution $k = 1008 - d$:
$$n = \frac{(1008 - k)^2}{2k}$$
$n$ is a positive integer when $2k \mid (1008 - k)^2$. Since $1008 = 2^4 \times 3^2 \times 7$, this becomes a divisor enumeration problem. The solutions include $n = 9, 48, 160, 2016, \ldots$ depending on the exact constraint.
Lesson: "Is $f(n)$ a perfect square?" → Set $f(n) = m^2$, factor the difference, then use divisibility.
SFFT Recognition Checklist.
- See $xy + ax + by = c$ → Add $ab$, factor.
- See $\frac{1}{a} + \frac{1}{b} = \frac{1}{n}$ → Multiply out, then SFFT.
- See "$n^2 + kn$ is a perfect square" → Difference of squares → divisor enumeration.
- Any equation with mixed $xy, x, y$ terms → try SFFT.
6. Perfect Square Detection
Many AIMO problems ask "find $n$ such that $f(n)$ is a perfect square." Here's your toolkit:
Facts about Perfect Squares.
- $n^2 \equiv 0$ or $1 \pmod{4}$ (never 2 or 3)
- $n^2 \equiv 0, 1, 4, 5, 6,$ or $9 \pmod{10}$ (last digits: 0,1,4,5,6,9)
- $n^2 \equiv 0$ or $1 \pmod{3}$ (never 2)
- If $p$ is prime and $p \mid n^2$, then $p^2 \mid n^2$ (i.e., prime appears to even power)
- Squeeze: If $k^2 < N < (k+1)^2$, then $N$ is not a perfect square. The gap between consecutive squares is $2k+1$.
Example 8 (AIMO 2015 Q5 style). Find all non-negative integers $x$ such that $2^{13} + 2^{10} + 2^x$ is a perfect square.
$2^{13} + 2^{10} + 2^x = 8192 + 1024 + 2^x = 9216 + 2^x$.
Note $9216 = 96^2$. So we need $96^2 + 2^x = m^2$, i.e. $m^2 - 96^2 = 2^x$.
$$(m - 96)(m + 96) = 2^x$$
Both factors must be powers of 2. Let $m - 96 = 2^a$, $m + 96 = 2^b$ with $a + b = x$ and $b > a$.
$$2^b - 2^a = 192 = 2^6 \times 3$$
$$2^a(2^{b-a} - 1) = 2^6 \times 3$$
So $a = 6$ and $2^{b-a} - 1 = 3$, giving $b - a = 2$, $b = 8$.
$m = 96 + 64 = 160$, $x = a + b = 14$.
Check: $2^{13} + 2^{10} + 2^{14} = 8192 + 1024 + 16384 = 25600 = 160^2$.
But wait — what if $x \le 10$? Then factor out $2^x$:
$2^x(2^{13-x} + 2^{10-x} + 1)$. For this to be a perfect square, $2^x$ must have $x$ even, and the bracket must be a perfect square. Checking small cases: $x = 1$ gives odd factor $2^{12}+2^9+1 = 4608+1 = 4609$... $67^2 = 4489, 68^2 = 4624$. Not a square. Systematic check yields $x = \mathbf{14}$ as the only solution.
7. Competition Strategy Toolkit
Strategy 1: Consecutive Integer Products.
The product of $k$ consecutive integers is always divisible by $k!$.
$$\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!} \in \mathbb{Z}$$
Use: "Prove $6 \mid n(n+1)(n+2)$" → it's $3! \times \binom{n+2}{3}$. Done.
Strategy 2: Factor Pair Enumeration.
If you reach "$AB = N$" where $N$ is known, list all factor pairs of $N$ (including negative ones if relevant). Typical flow:
- Get equation into the form "product = constant"
- List all factor pairs $(d_1, d_2)$ with $d_1 d_2 = N$, $d_1 \le d_2$
- For each pair, solve back for the original variables
- Check constraints (positive, integer, etc.)
Strategy 3: Bounding + Squeeze.
When you have $f(n) = m^2$, find which consecutive squares $f(n)$ falls between:
$$k^2 \le f(n) \le (k+1)^2$$
If $f(n)$ is always strictly between two consecutive squares (for large enough $n$), then no solution exists beyond some bound. Then check small cases by hand.
Strategy 4: Modular Obstruction.
To show "no solution exists": compute both sides modulo a well-chosen $m$. If the LHS can never match the RHS mod $m$, there's no solution. Common choices: mod 2, 3, 4, 8, 9.
8. AIMO & AIME Worked Examples
AIMO 2022 Q1. A three-digit number $\overline{abc}$ satisfies $\overline{abc} \times 3 = \overline{c0ba}$ (a four-digit number with 0 as the hundreds digit). Find $\overline{abc}$.
Expand: $3(100a + 10b + c) = 1000c + 10b + a$.
$$300a + 30b + 3c = 1000c + 10b + a$$
$$299a + 20b = 997c \quad \cdots (*)$$
Bound $a$ and $c$: $\overline{abc} \ge 100$ so $\overline{c0ba} \ge 300$, meaning $c \ge 1$. Also $\overline{abc} \le 333$ (else $3 \times \overline{abc} \ge 1002$ which breaks the $\overline{c0ba}$ format... actually $\overline{c0ba}$ can go up to 9099).
From $(*)$: $997c = 299a + 20b$. Max RHS: $299 \times 9 + 20 \times 9 = 2691 + 180 = 2871$. So $c \le 2$.
$c = 1$: $299a + 20b = 997$. Try $a = 3$: $20b = 997 - 897 = 100$, $b = 5$.
Check: $351 \times 3 = 1053$. That's $\overline{1053}$ = digits $c=1, 0, b=5, a=3$.
$c = 2$: $299a + 20b = 1994$. $a = 6$: $20b = 1994 - 1794 = 200$, $b = 10$. But $b$ must be a single digit. No solution.
Answer: $\overline{abc} = 351$.
AIMO 2018 Q7. Find all pairs $(a, b)$ of positive integers such that $a^2 - b^2 = 2018 - 2a$.
Rearrange: $a^2 + 2a - b^2 = 2018$.
$$(a+1)^2 - 1 - b^2 = 2018$$
$$(a+1)^2 - b^2 = 2019$$
$$(a+1-b)(a+1+b) = 2019$$
Factor $2019 = 3 \times 673$. Factor pairs with both factors positive and same parity (since $(a+1-b) + (a+1+b) = 2(a+1)$ is even, both factors must be odd — and $2019 = 3 \times 673$, both odd ):
| $a+1-b$ | $a+1+b$ | $a$ | $b$ |
|---|
| 1 | 2019 | $\frac{2020}{2}-1 = 1009$ | $\frac{2018}{2} = 1009$ |
| 3 | 673 | $\frac{676}{2}-1 = 337$ | $\frac{670}{2} = 335$ |
Check: $1009^2 - 1009^2 = 0$ and $2018 - 2(1009) = 0$.
Check: $337^2 - 335^2 = (337-335)(337+335) = 2 \times 672 = 1344$ and $2018 - 674 = 1344$.
Answer: $(a,b) = (1009, 1009)$ and $(337, 335)$.
AIME 2019 I, Problem 1 (adapted). Let $N = 2^{31} \times 3^{19}$. How many positive divisors of $N^2$ are less than $N$ but do not divide $N$?
$N^2 = 2^{62} \times 3^{38}$.
$\tau(N^2) = 63 \times 39 = 2457$.
$\tau(N) = 32 \times 20 = 640$.
Key idea: Divisors of $N^2$ pair up: $d \leftrightarrow N^2/d$. If $d < N$ then $N^2/d > N$. So:
- Divisors of $N^2$ that are $< N$: $\frac{2457 - 1}{2} = 1228$ (subtract 1 for $d = N$ itself)
- Divisors of $N$ that are $< N$: $640 - 1 = 639$
Answer: $1228 - 639 = \mathbf{589}$.
AIMO 2023 Q1. Positive integers $a$ and $b$ satisfy $\frac{a}{b} + \frac{b}{a} = \frac{25}{12}$ and $(a+b)(a-b) = 2023$. Find $a + b$.
From the second equation: $a^2 - b^2 = 2023$, so $(a-b)(a+b) = 2023$.
$2023 = 7 \times 17^2$. Factor pairs: $(1, 2023), (7, 289), (17, 119)$.
Since $a + b > a - b > 0$ and $(a+b) + (a-b) = 2a$ is even, both must be odd (which they are).
From $\frac{a}{b} + \frac{b}{a} = \frac{a^2 + b^2}{ab} = \frac{25}{12}$.
Also $a^2 - b^2 = 2023$, so $a^2 + b^2 = 2b^2 + 2023$.
Test $(a-b, a+b) = (7, 289)$: $a = 148, b = 141$.
$\frac{148^2 + 141^2}{148 \times 141} = \frac{21904 + 19881}{20868} = \frac{41785}{20868}$. Is this $\frac{25}{12}$? $\frac{25}{12} = \frac{43475}{20868}$. No.
Test $(17, 119)$: $a = 68, b = 51$.
$\frac{68^2 + 51^2}{68 \times 51} = \frac{4624 + 2601}{3468} = \frac{7225}{3468}$. Simplify: $7225 = 25 \times 289$, $3468 = 12 \times 289$. So $\frac{25}{12}$.
Answer: $a + b = 68 + 51 = 119$.
9. Practice Problems
= Basic = Medium = AIMO level = AIME level
P1 Prove that $n^3 - n$ is divisible by 6 for every integer $n$.
Solution
$n^3 - n = n(n-1)(n+1)$ — product of 3 consecutive integers. Divisible by $3! = 6$. ∎
P2 Find the number of positive divisors of $10! = 3{,}628{,}800$.
Answer
$10! = 2^8 \times 3^4 \times 5^2 \times 7$. Divisors: $9 \times 5 \times 3 \times 2 = \mathbf{270}$.
P3 Find the sum of all positive divisors of $2025$.
Answer
$2025 = 3^4 \times 5^2$. $\sigma = \frac{3^5-1}{2} \times \frac{5^3-1}{4} = 121 \times 31 = \mathbf{3751}$.
P4 Prove that if $n$ is a positive integer not divisible by 3, then $n^2 \equiv 1 \pmod{3}$.
Solution
If $3 \nmid n$, then $n \equiv 1$ or $2 \pmod{3}$. In either case $n^2 \equiv 1 \pmod{3}$. ∎
P5 Find all pairs of positive integers $(x, y)$ with $\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{12}$.
Solution
SFFT: $(x-12)(y-12) = 144$. Factor pairs of $144 = 2^4 \times 3^2$: $(1,144), (2,72), (3,48), (4,36), (6,24), (8,18), (9,16), (12,12)$ and reverses.
$(x,y)$: $(13,156), (14,84), (15,60), (16,48), (18,36), (20,30), (21,28), (24,24)$. 8 unordered pairs.
P6 Show that no perfect square ends in the digits $23$ (i.e., $n^2 \not\equiv 23 \pmod{100}$ for any integer $n$).
Hint
Check $n^2 \pmod{4}$. Since $23 \equiv 3 \pmod{4}$ and $n^2 \equiv 0$ or $1 \pmod{4}$, it's impossible. ∎
P7 (AIMO style) Find all positive integers $n$ such that both $n+3$ and $n^2 + 3n + 3$ are perfect cubes.
Hint
Let $n + 3 = k^3$. Then $n^2 + 3n + 3 = (k^3 - 3)^2 + 3(k^3-3)+3 = k^6 - 3k^3 + 3$. Need this to be a perfect cube. For large $k$: $(k^2)^3 = k^6$ and $(k^2-1)^3 = k^6 - 3k^4 + 3k^2 - 1$. The gap analysis gives only finitely many solutions. Check small $k$.
P8 (AIMO 2014 Q8 adapted) Find the largest three-digit number $n$ such that $n \equiv n^2 \pmod{100}$.
Solution
$n^2 \equiv n \pmod{100} \Rightarrow n(n-1) \equiv 0 \pmod{100}$. Since $\gcd(n, n-1) = 1$, either: $25 \mid n$ and $4 \mid (n-1)$, or $4 \mid n$ and $25 \mid (n-1)$, or $100 \mid n$, or $100 \mid (n-1)$.
Three-digit solutions: $n \equiv 0, 1, 25, 76 \pmod{100}$.
Largest three-digit: $n = 976$ ($n \equiv 76$) or $n = 1000$ (not 3-digit). Check: $976^2 = 952576$, last two digits $76 = 976 \bmod 100$.
Answer: 976.
P9 Find all positive integers $n$ such that $n^2 + 12n$ is a perfect square.
Solution
$n^2 + 12n = m^2 \Rightarrow m^2 - n^2 = 12n \Rightarrow (m-n)(m+n) = 12n$. Let $m-n = d$, then $d(2n+d) = 12n$, so $d^2 = n(12-2d)$, giving $n = \frac{d^2}{12-2d}$. Need $d < 6$. Check $d = 1,2,3,4,5$:
$d=2$: $n = 4/8$ — no. $d=3$: $n = 9/6$ — no. $d=4$: $n = 16/4 = 4$ . ($4^2+48 = 64 = 8^2$.)
Answer: $n = 4$.
P10 (AIME) Let $S$ be the set of positive divisors of $20^9$. What is the product of all elements of $S$?
Solution
$20^9 = 2^{18} \times 5^9$. $\tau(20^9) = 19 \times 10 = 190$.
Product of divisors = $(20^9)^{190/2} = 20^{855}$ or equivalently $2^{18 \times 95} \times 5^{9 \times 95} = 2^{1710} \times 5^{855}$.
P11 Prove: for every positive integer $n$, the number $\displaystyle\frac{(2n)!}{n! \cdot n!}$ is an integer. (That is, prove $\binom{2n}{n} \in \mathbb{Z}$ from first principles, without using the combinatorial interpretation.)
Hint
Use Legendre's formula: for every prime $p$, show $v_p((2n)!) \ge 2 \cdot v_p(n!)$, where $v_p(m!) = \sum_{i=1}^{\infty} \lfloor m/p^i \rfloor$. This follows from $\lfloor 2x \rfloor \ge 2\lfloor x \rfloor$ for all real $x$.
P12 (AIMO 2019 Q8 style) Let $p > 5$ be prime and let $a, b$ be positive integers. Prove that $\gcd(a^5 + b^5 - ab(a^3 + b^3),\; p) = p$ if and only if $p \mid (a - b)$.
Hint
Factor: $a^5 + b^5 - a^4 b - ab^4 = a^5 - a^4 b + b^5 - ab^4 = a^4(a-b) - b(a^4 - b^4) = a^4(a-b) - b(a-b)(a+b)(a^2+b^2) = (a-b)[a^4 - b(a+b)(a^2+b^2)]$. So $(a-b)$ is a factor. Show the other factor is not divisible by $p$ when $p \nmid (a-b)$.