Back to Contents

Chapter 1: Number Theory

Section 1.2 — Primes & Prime Factorisation | AIMO Training Programme
In this section:
  1. 1.1 Review — Guided Problem Walkthroughs
  2. Primes & the Fundamental Theorem of Arithmetic
  3. Finding Prime Factorisations
  4. Applications of Prime Factorisation
  5. Perfect Squares, Cubes & Higher Powers
  6. Competition Strategy: When to Factorise
  7. Worked Examples
  8. Practice Problems (12 problems, graded difficulty)

0. Section 1.1 Review — Guided Problem Walkthroughs

Before new content, let's revisit four problems from 1.1 that combine multiple ideas. For each one, we break the solution into small guided steps so you can see how the ideas connect.

How to Read These
Try each lettered step yourself first. Only open the hint/answer if you're stuck. The goal is to build the habit of asking yourself: "What tool fits here?"
Review 1 (1.1 P6)   Show that no perfect square ends in the digits $23$.

Key skills: divisibility test → modular thinking → contradiction
  1. Explore small cases. Compute $n^2 \bmod 100$ for $n = 0, 1, 2, \ldots, 9$. List all possible last two digits of a perfect square.
    Check
    $0^2 = 00,\; 1^2 = 01,\; 2^2 = 04,\; 3^2 = 09,\; 4^2 = 16,\; 5^2 = 25,\;$ $6^2 = 36,\; 7^2 = 49,\; 8^2 = 64,\; 9^2 = 81$.
    But this only covers one digit of $n$. The last two digits of $n^2$ depend on the last two digits of $n$, so you'd need $n = 0, \ldots, 49$ (by symmetry $n$ and $100-n$ give the same $n^2 \bmod 100$). That's a lot of cases!
  2. Find a shortcut. Instead of mod $100$, try a smaller modulus. What are the only possible values of $n^2 \bmod 4$?
    Check
    $n$ even $\Rightarrow n^2 \equiv 0 \pmod{4}$.   $n$ odd $\Rightarrow n^2 \equiv 1 \pmod{4}$.
    So $n^2 \bmod 4 \in \{0, 1\}$ — only two possibilities!
  3. Apply to the target. What is $23 \bmod 4$? Does it match any value from (b)?
    Check
    $23 = 5 \times 4 + 3$, so $23 \equiv 3 \pmod{4}$.
    Since $n^2$ can only be $0$ or $1 \pmod{4}$, it can never be $3 \pmod{4}$. Contradiction. ∎
  4. Write it up. Combine (b) and (c) into a clean two-line proof.
    Model proof
    For any integer $n$, $n^2 \equiv 0$ or $1 \pmod{4}$. But if $n^2$ ends in $23$, then $n^2 \equiv 23 \equiv 3 \pmod{4}$ — impossible. ∎
Takeaway: When a problem asks about specific digits of $n^2$, try reducing mod a small number (4, 8, or 9) first. You don't need to check all 100 endings — just find one modulus that gives a contradiction.
Review 2 (1.1 P7)   Find all positive integers $n$ such that both $n+3$ and $n^2+3n+3$ are perfect cubes.

Key skills: substitution → algebraic manipulation → bounding (squeeze)
  1. Introduce a variable. Let $n + 3 = k^3$ for some positive integer $k$. Express $n$ in terms of $k$.
    Check
    $n = k^3 - 3$.
  2. Substitute. Write $n^2 + 3n + 3$ in terms of $k$. Simplify.
    Check
    $n^2 + 3n + 3 = (k^3-3)^2 + 3(k^3-3) + 3$ $= k^6 - 6k^3 + 9 + 3k^3 - 9 + 3 = k^6 - 3k^3 + 3$.
  3. Squeeze between consecutive cubes. We need $k^6 - 3k^3 + 3$ to be a perfect cube. Note that $(k^2)^3 = k^6$. Compute $(k^2 - 1)^3$ and show: $$(k^2-1)^3 < k^6 - 3k^3 + 3 < (k^2)^3 \quad \text{for } k \ge 2.$$
    Check
    $(k^2-1)^3 = k^6 - 3k^4 + 3k^2 - 1$.
    We need $k^6 - 3k^4 + 3k^2 - 1 < k^6 - 3k^3 + 3$, i.e. $-3k^4 + 3k^2 - 1 < -3k^3 + 3$, i.e. $3k^4 - 3k^3 - 3k^2 + 4 > 0$.
    For $k \ge 2$: $3k^3(k-1) \ge 3 \cdot 8 \cdot 1 = 24$ and $3k^2 \le 3k^3$, so this is positive.
    And $k^6 - 3k^3 + 3 < k^6$ is obvious for $k \ge 2$.
  4. Conclude. If $k^6 - 3k^3 + 3$ is strictly between two consecutive cubes, it can't be a perfect cube. So what values of $k$ remain?
    Check
    Only $k = 1$: $n = 1 - 3 = -2$ (not positive) and $k = 0$: $n = -3$ (not positive).
    Check $k = 1$: $n^2+3n+3 = 4-6+3 = 1 = 1^3$ , but $n=-2$ is not a positive integer.
    So there are no positive integers $n$ satisfying both conditions. ∎
Takeaway: When you need an expression to be a perfect power, squeeze it between consecutive powers. If it's strictly between $m^3$ and $(m+1)^3$, it can't be a cube. This "bounding" technique appears in ~20% of AIMO number theory problems.
Review 3 (1.1 P10)   Let $S$ be the set of positive divisors of $20^9$. Find the product of all elements of $S$.

Key skills: prime factorisation → $\tau$ formula → divisor product formula
  1. Factorise. Write $20^9$ as a product of prime powers.
    Check
    $20^9 = (2^2 \times 5)^9 = 2^{18} \times 5^9$.
  2. Count divisors. How many positive divisors does $20^9$ have?
    Check
    $\tau(20^9) = (18+1)(9+1) = 19 \times 10 = 190$.
  3. Apply the formula. Recall from 1.1: the product of all divisors of $n$ is $n^{\tau(n)/2}$. Compute this.
    Check
    Product $= (20^9)^{190/2} = (20^9)^{95} = 20^{855}$.
    Or equivalently: $2^{18 \times 95} \times 5^{9 \times 95} = 2^{1710} \times 5^{855}$.
Takeaway: This is a "three-formula chain": factorise → count divisors $\tau(n)$ → product formula $n^{\tau(n)/2}$. Each step feeds into the next. In competitions, recognise when a problem is asking you to chain two or three standard results.
Review 4 (1.1 P12)   Let $p > 5$ be prime and $a, b$ positive integers. Prove that $p \mid (a^5 + b^5 - ab(a^3 + b^3))$ if and only if $p \mid (a-b)$.

Key skills: algebraic factorisation → extracting common factors → using prime divisibility
  1. Simplify the expression. Expand and rearrange $a^5 + b^5 - a^4 b - ab^4$.
    Check
    $a^5 + b^5 - a^4 b - ab^4 = a^5 - a^4 b + b^5 - ab^4$ $= a^4(a - b) + b^4(b - a) = a^4(a-b) - b^4(a-b)$ $= (a-b)(a^4 - b^4)$.
  2. Factorise further. Factor $a^4 - b^4$ completely.
    Check
    $a^4 - b^4 = (a^2-b^2)(a^2+b^2) = (a-b)(a+b)(a^2+b^2)$.
    So the full expression is $(a-b)^2(a+b)(a^2+b^2)$.
  3. Prove ⇐. If $p \mid (a-b)$, explain why $p$ divides the whole expression.
    Check
    If $p \mid (a-b)$, then $p \mid (a-b)^2$, and since the expression equals $(a-b)^2 \cdot (a+b)(a^2+b^2)$, we get $p$ divides the expression.
  4. Prove ⇒. If $p$ divides $(a-b)^2(a+b)(a^2+b^2)$, why must $p \mid (a-b)$?
    Hint: $p$ is prime, so it must divide one of the factors. Show that if $p \nmid (a-b)$, then $p \mid (a+b)$ leads to $p \mid 2b$, and consider $p > 5$...
    Check
    Since $p$ is prime, $p \mid (a-b)^2$ or $p \mid (a+b)$ or $p \mid (a^2+b^2)$.
    Case 1: $p \mid (a-b)^2 \Rightarrow p \mid (a-b)$. Done.
    Case 2: $p \nmid (a-b)$ but $p \mid (a+b)$. Then $p \mid [(a+b)-(a-b)] = 2b$ and $p \mid [(a+b)+(a-b)] = 2a$. Since $p > 5 > 2$, $\gcd(p,2)=1$, so $p \mid a$ and $p \mid b$, giving $p \mid (a-b)$. Contradiction.
    Case 3: $p \nmid (a-b)$, $p \nmid (a+b)$, but $p \mid (a^2+b^2)$. Then $p \mid [(a^2+b^2) + (a+b)(a-b)] = 2a^2$. Since $p > 2$, $p \mid a^2$, so $p \mid a$ (prime), hence $p \mid b^2$ so $p \mid b$, giving $p \mid (a-b)$. Contradiction. ∎
Takeaway: The "factor everything, then use $p$ prime" strategy is extremely common. Steps: (1) factor the expression as far as possible, (2) since $p$ is prime, it must divide at least one factor, (3) chase what happens in each case.
Pattern Summary from 1.1 Review
Problem TypeFirst MoveKey Tool
Prove something about digits of $n^2$Try small modulus (4, 8, 9)Quadratic residues
Expression must be a perfect powerSqueeze between consecutive powersBounding / inequalities
Divisor products/sumsPrime factorise first$\tau$, $\sigma$, product formula chain
"Prove $p$ divides..." with $p$ primeFactor the expression$p$ divides a product $\Rightarrow$ $p$ divides a factor

1. Primes & the Fundamental Theorem of Arithmetic

Definition. An integer $p \ge 2$ is prime if its only positive divisors are $1$ and $p$. An integer $n \ge 2$ that is not prime is called composite.

Convention: $1$ is neither prime nor composite.
Theorem (Fundamental Theorem of Arithmetic — FTA). Every integer $n \ge 2$ can be written as a product of primes in exactly one way (up to order): $$n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$$ where $p_1 < p_2 < \cdots < p_k$ are primes and each $a_i \ge 1$.

This is arguably the most important theorem in number theory. It says every positive integer has a unique "DNA" — its prime factorisation.

Example 1. $360 = 2^3 \times 3^2 \times 5$.   $1001 = 7 \times 11 \times 13$.   $2025 = 3^4 \times 5^2$.
You should be able to factorise any number up to 1000 within 30 seconds in competition. Primes up to 50 should be memorised: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Theorem (Euclid's Lemma). If $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.

This is exactly what makes primes special — and what fails for composite numbers. For example, $6 \mid (4 \times 3)$ but $6 \nmid 4$ and $6 \nmid 3$.

Theorem (Infinitude of Primes). There are infinitely many primes.

Proof sketch (Euclid): Suppose there are only finitely many primes $p_1, \ldots, p_k$. Consider $N = p_1 p_2 \cdots p_k + 1$. None of $p_1, \ldots, p_k$ divides $N$ (each gives remainder 1). So $N$ has a prime factor not on our list — contradiction. ∎

2. Finding Prime Factorisations

Trial Division

To factorise $n$, try dividing by primes $p = 2, 3, 5, 7, 11, \ldots$ up to $\sqrt{n}$. If none divides $n$, then $n$ is prime.

Why $\sqrt{n}$? If $n = ab$ with $a \le b$, then $a \le \sqrt{n}$. So every composite $n$ has a prime factor $\le \sqrt{n}$.
Example 2. Is $221$ prime?
$\sqrt{221} \approx 14.9$, so check primes up to 14: $2, 3, 5, 7, 11, 13$.
$221 / 13 = 17$. So $221 = 13 \times 17$. Not prime.
Example 3. Is $223$ prime?
$\sqrt{223} \approx 14.9$. Check $2, 3, 5, 7, 11, 13$: none divides $223$. So $223$ is prime.

Factoring Shortcuts for Competitions

PatternFactorisationExample
$a^2 - b^2$$(a-b)(a+b)$$9991 = 10000-9 = 100^2-3^2 = 97 \times 103$
$a^3 \pm b^3$$(a \pm b)(a^2 \mp ab + b^2)$$1001 = 10^3+1 = 7 \times 11 \times 13$
$a^n - 1$$(a-1)(a^{n-1}+\cdots+1)$$2^{10}-1 = 1023 = 3 \times 11 \times 31$
Recognise near-squares$n = m^2 \pm k$$899 = 900-1 = 30^2-1 = 29 \times 31$
In AIMO, numbers like $1001$, $111$, $10^n \pm 1$ appear often. Know their factorisations:
$111 = 3 \times 37$,   $1001 = 7 \times 11 \times 13$,   $10001 = 73 \times 137$,   $1111 = 11 \times 101$.

3. Applications of Prime Factorisation

GCD and LCM via Prime Factorisation

Theorem. If $a = \prod p_i^{a_i}$ and $b = \prod p_i^{b_i}$ (using all primes, with $a_i$ or $b_i = 0$ if needed), then: $$\gcd(a,b) = \prod p_i^{\min(a_i, b_i)}, \qquad \text{lcm}(a,b) = \prod p_i^{\max(a_i, b_i)}$$
Example 4. $\gcd(360, 2025)$.
$360 = 2^3 \times 3^2 \times 5^1$,   $2025 = 3^4 \times 5^2$.
$\gcd = 2^0 \times 3^2 \times 5^1 = 45$.
$\text{lcm} = 2^3 \times 3^4 \times 5^2 = 8 \times 81 \times 25 = 16200$.
Check: $45 \times 16200 = 729000 = 360 \times 2025$.

Divisibility Conditions

Key Fact. $a \mid b$ if and only if every prime power in the factorisation of $a$ also appears (with $\le$ exponent) in $b$.
That is: if $a = \prod p_i^{a_i}$ and $b = \prod p_i^{b_i}$, then $a \mid b \iff a_i \le b_i$ for all $i$.
Example 5 (AIMO style). How many positive integers $n$ satisfy $n \mid 360$ and $\gcd(n, 100) = 1$?
Solution: $360 = 2^3 \times 3^2 \times 5$.   $100 = 2^2 \times 5^2$.
$\gcd(n, 100) = 1$ means $n$ has no factors of $2$ or $5$. So $n$ divides $360$ and uses only the prime $3$.
$n \in \{1, 3, 9\}$. Answer: $\boxed{3}$.

4. Perfect Squares, Cubes & Higher Powers

Theorem. $n$ is a perfect square $\iff$ every exponent in its prime factorisation is even.
$n$ is a perfect cube $\iff$ every exponent is divisible by $3$.
$n$ is a perfect $k$-th power $\iff$ every exponent is divisible by $k$.
Example 6. What is the smallest positive integer $k$ such that $360k$ is a perfect square?
$360 = 2^3 \times 3^2 \times 5$. Need all exponents even.
$2^3 \to$ need $2^1$ more.   $3^2 \to$ already even.   $5^1 \to$ need $5^1$ more.
$k = 2 \times 5 = 10$. Check: $3600 = 60^2$.
Example 7 (Classic competition). Find the smallest $n > 1$ such that $n!$ is a perfect square.
This is trickier! $n!$ is a perfect square $\iff$ every prime $p \le n$ appears to an even power in $n!$.

By Legendre's formula, the exponent of $p$ in $n!$ is $\sum_{i=1}^{\infty} \lfloor n/p^i \rfloor$.
The largest prime $\le n$ appears exactly once (to the power 1) if it's between $n/2$ and $n$. So we need no such prime — by Bertrand's postulate, there's always a prime between $n/2$ and $n$ for $n \ge 2$.
So $n!$ is never a perfect square for $n \ge 2$! The answer is: no such $n$ exists.
Legendre's formula — the exponent of prime $p$ in $n!$ is: $$v_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots$$ This is extremely useful for competition problems involving factorials.

5. Competition Strategy: When to Factorise

Decision Flowchart
  1. "How many divisors / find all divisors" → Prime factorise immediately.
  2. "Is $n$ a perfect square/cube?" → Prime factorise, check exponents.
  3. "Find $\gcd$ or $\text{lcm}$" → If numbers are large, try Euclidean algorithm first. If the problem is structural (like "for all $n$..."), use prime factorisation.
  4. "Prove $p \mid \text{expression}$" → Factor the expression algebraically, then use Euclid's lemma.
  5. "Product of divisors / sum of divisors" → Use $\tau$, $\sigma$ formulas (need prime factorisation).

6. Worked Examples

Worked Example 1. (AIMO 2016 Q1) Find the largest four-digit number that is divisible by $63$ and whose digits are all different.
$63 = 7 \times 9$. So we need divisibility by both $7$ and $9$.
Start from $9999$ and work down: $9999 / 63 = 158.7...$, so $63 \times 158 = 9954$. Digits: $9,9,5,4$ — repeated $9$! Next: $63 \times 157 = 9891$. Digits: $9,8,9,1$ — repeated. $63 \times 156 = 9828$ — repeated. Continue...
$63 \times 154 = 9702$. Digits: $9,7,0,2$ — all different!
Answer: $\boxed{9702}$.
Worked Example 2. Find all primes $p$ such that $p^2 + 2$ is also prime.
Check small primes: $p=2 \Rightarrow p^2+2 = 6$ (not prime). $p=3 \Rightarrow p^2+2 = 11$ . $p=5 \Rightarrow 27$ (not prime). $p=7 \Rightarrow 51 = 3 \times 17$ (not prime).

Pattern: For $p > 3$, $p$ is not divisible by $3$, so $p \equiv 1$ or $2 \pmod{3}$.
If $p \equiv 1 \pmod{3}$: $p^2 \equiv 1 \pmod{3}$, so $p^2 + 2 \equiv 0 \pmod{3}$. Not prime (since $> 3$).
If $p \equiv 2 \pmod{3}$: $p^2 \equiv 4 \equiv 1 \pmod{3}$, so $p^2 + 2 \equiv 0 \pmod{3}$. Not prime.

So the only answer is $p = \boxed{3}$.
Worked Example 3. How many positive integers $n \le 1000$ satisfy $\gcd(n, 1000) = 1$?
This is Euler's totient: $\varphi(1000)$.
$1000 = 2^3 \times 5^3$.
$\varphi(1000) = 1000 \times (1 - \tfrac{1}{2})(1 - \tfrac{1}{5}) = 1000 \times \tfrac{1}{2} \times \tfrac{4}{5} = \boxed{400}$.

Euler's formula: $\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$ where the product is over distinct prime factors of $n$.
This counts integers in $\{1, \ldots, n\}$ coprime to $n$. We'll use this more in Section 1.5 (modular arithmetic).

7. Practice Problems

Problems are graded (warm-up) to (competition hard). Try each one before reading the hint.

P1 Factorise $111{,}111$ into primes.
Hint & Solution
$111111 = 111 \times 1001 = (3 \times 37)(7 \times 11 \times 13) = 3 \times 7 \times 11 \times 13 \times 37$.
P2 Find the smallest positive integer $n$ such that $2n$ is a perfect square and $3n$ is a perfect cube.
Hint & Solution
Let $n = 2^a \times 3^b \times m$ where $\gcd(m, 6) = 1$.
$2n = 2^{a+1} \times 3^b \times m$ is a perfect square: $a+1, b$ even, and $m$ is a perfect square.
$3n = 2^a \times 3^{b+1} \times m$ is a perfect cube: $a, b+1$ divisible by 3, and $m$ is a perfect cube.
From $a+1$ even and $a \equiv 0 \pmod{3}$: smallest $a = 3$. (Check: $a+1=4$ even , $a=3$ div by 3 .)
From $b$ even and $b+1 \equiv 0 \pmod{3}$: $b$ even and $b \equiv 2 \pmod{3}$. Smallest: $b = 2$. (Check: even , $b+1=3$ .)
Smallest $m$ that's both a perfect square and cube is $m = 1$.
$n = 2^3 \times 3^2 = \boxed{72}$.
P3 How many positive divisors of $10!$ are perfect squares?
Hint & Solution
$10! = 2^8 \times 3^4 \times 5^2 \times 7$.
(Using Legendre: $v_2(10!) = 5+2+1 = 8$, $v_3 = 3+1 = 4$, $v_5 = 2$, $v_7 = 1$.)
A divisor $d = 2^a \times 3^b \times 5^c \times 7^e$ is a perfect square iff $a, b, c, e$ all even.
$a \in \{0,2,4,6,8\}$: 5 choices. $b \in \{0,2,4\}$: 3 choices. $c \in \{0,2\}$: 2 choices. $e \in \{0\}$: 1 choice.
Total: $5 \times 3 \times 2 \times 1 = \boxed{30}$.
P4 Find all primes $p$ such that $p + 10$ and $p + 14$ are both prime.
Hint & Solution
Think mod 3. Among any three consecutive integers, one is divisible by 3.
Consider $p, p+10, p+14$ modulo 3. Note $p+10 \equiv p+1$ and $p+14 \equiv p+2 \pmod{3}$.
So $\{p, p+1, p+2\} \pmod{3} = \{0, 1, 2\}$, meaning one of $p$, $p+10$, $p+14$ is divisible by 3.
Wait — it's $p$, $p+10$, $p+14$, not $p, p+1, p+2$. Let's redo:
$p \bmod 3$: if $p \equiv 0$, then $p = 3$. Check: $13, 17$ both prime.
If $p \equiv 1$: $p+14 \equiv 0 \pmod 3$, so $p+14$ is divisible by 3. For it to be prime, $p+14=3 \Rightarrow p = -11$. No.
If $p \equiv 2$: $p+10 \equiv 0 \pmod 3$, so $p+10 = 3 \Rightarrow p = -7$. No.
Answer: $p = \boxed{3}$.
P5 Prove: if $a^2 \mid b^2$, then $a \mid b$ (where $a, b$ are positive integers).
[Hint: Use the exponent of each prime.]
Solution
Let $p$ be any prime. Let $v_p(a) = \alpha$ and $v_p(b) = \beta$.
$a^2 \mid b^2 \Rightarrow 2\alpha \le 2\beta \Rightarrow \alpha \le \beta$.
This holds for every prime $p$, so $a \mid b$. ∎

Bonus challenge: Is the stronger claim "$a^2 \mid b^3 \Rightarrow a \mid b$" true? Try $a = 8, b = 4$.
$a^2 = 64, b^3 = 64$, so $a^2 \mid b^3$ . But $8 \nmid 4$. So the stronger claim is false!
Finding counterexamples is an important competition skill.
P6 (AIMO style) The number $2^{2025} \times 5^{2026}$ is written out in full. How many digits does it have?
Hint & Solution
$2^{2025} \times 5^{2026} = 2^{2025} \times 5^{2025} \times 5 = 10^{2025} \times 5 = 5 \times 10^{2025}$.
This is the digit $5$ followed by $2025$ zeros. It has $\boxed{2026}$ digits.
P7 Find the number of positive integers $n$ such that $n \mid 2^6 \times 3^4 \times 5^2$ and $n$ is not a perfect square.
Hint & Solution
Total divisors: $(6+1)(4+1)(2+1) = 7 \times 5 \times 3 = 105$.
Perfect square divisors: exponents must be even. $a \in \{0,2,4,6\}$: 4. $b \in \{0,2,4\}$: 3. $c \in \{0,2\}$: 2.
Square divisors: $4 \times 3 \times 2 = 24$.
Non-square divisors: $105 - 24 = \boxed{81}$.
P8 Find the largest power of $12$ that divides $30!$.
Hint & Solution
$12 = 2^2 \times 3$. So $12^k = 2^{2k} \times 3^k$.
Need $v_2(30!) \ge 2k$ and $v_3(30!) \ge k$.
$v_2(30!) = 15 + 7 + 3 + 1 = 26$. So $k \le 13$.
$v_3(30!) = 10 + 3 + 1 = 14$. So $k \le 14$.
The binding constraint is $k \le 13$. Answer: $12^{\boxed{13}}$.
P9 (Scaffolded) The number $n = 2^a \times 3^b$ has exactly $10$ positive divisors and $\sigma(n) = 363$ (sum of divisors). Find $n$.
  1. $(a+1)(b+1) = 10$. List all possible $(a,b)$ pairs with $a,b \ge 1$.
  2. For each pair, compute $\sigma(n) = \frac{2^{a+1}-1}{1} \times \frac{3^{b+1}-1}{2}$ and check if it equals $363$.
Solution
$(a+1)(b+1) = 10$. With $a,b \ge 1$: $(a,b) \in \{(1,4), (4,1)\}$.

$(a,b) = (1,4)$: $n = 2 \times 81 = 162$. $\sigma = (1+2) \times (1+3+9+27+81) = 3 \times 121 = 363$.
$(a,b) = (4,1)$: $n = 16 \times 3 = 48$. $\sigma = (1+2+4+8+16)(1+3) = 31 \times 4 = 124$.

Answer: $n = \boxed{162}$.
P10 (AIME 2003) How many positive integers $n$ satisfy $\lfloor \sqrt{n} \rfloor = 5$ and $n$ has exactly $5$ positive divisors?
Hint & Solution
$\lfloor\sqrt{n}\rfloor = 5 \Rightarrow 25 \le n \le 35$.
$n$ has exactly 5 divisors $\Rightarrow$ $\tau(n) = 5$. Since $5$ is prime, either $n = p^4$ (one prime to the 4th) or... that's the only way ($5 = 5 \times 1$).
$n = p^4$: $2^4 = 16$ (too small), $3^4 = 81$ (too big). No $p^4$ in $[25, 35]$.
Answer: $\boxed{0}$.
P11 (Scaffolded) Prove that if $p$ and $8p^2 + 1$ are both prime, then $p = 3$.
  1. Check $p = 2$: is $8(4)+1 = 33$ prime?
  2. Check $p = 3$: is $8(9)+1 = 73$ prime?
  3. For $p > 3$: what are the possible values of $p \bmod 3$? (Remember $p$ is prime and $p > 3$.)
  4. For each case in (c), compute $8p^2 + 1 \bmod 3$. What do you conclude?
Solution
(a) $33 = 3 \times 11$, not prime.
(b) $73$ is prime.
(c) $p > 3$ and prime $\Rightarrow p \equiv 1$ or $2 \pmod{3}$.
(d) In both cases, $p^2 \equiv 1 \pmod{3}$, so $8p^2 + 1 \equiv 8 + 1 \equiv 0 \pmod{3}$.
Since $8p^2 + 1 > 3$ for $p > 3$, it's divisible by 3 but greater than 3, so not prime.
Therefore $p = \boxed{3}$. ∎
P12 (AIMO style, scaffolded) Find all pairs $(a, b)$ of positive integers such that $a^2 b + a = b^3 + b$.
  1. Rearrange: move all terms to one side and factor.
  2. You should get $(b - a)(\_\_\_) = a$. What fills the blank?
  3. Since $a > 0$, what does this tell you about the sign of $b - a$?
  4. Let $b - a = d > 0$. Then $a = d \cdot (\_\_\_)$. Since $d \mid a$ and both factors are positive, what are the constraints?
  5. Try small values of $d$ to find all solutions.
Solution
(a) $a^2 b + a - b^3 - b = 0$. Factor: $a(a b + 1) - b(b^2 + 1) = 0$... Let's try differently.
$a^2 b - b^3 = b - a \Rightarrow b(a^2 - b^2) = b - a \Rightarrow b(a-b)(a+b) = -(a-b)$.
If $a \neq b$: divide by $(a - b)$: $b(a+b) = -1$. Since $a, b > 0$, LHS $> 0$ but RHS $= -1$. Contradiction.
So $a = b$. Check: $a^2 \cdot a + a = a^3 + a$ and $b^3 + b = a^3 + a$. for all $a$.

All solutions: $(a, b) = (n, n)$ for any positive integer $n$. $\boxed{a = b}$.

Note: The scaffolding hints suggested a different factorisation path — that's okay! In competitions, sometimes your first approach leads to a cleaner solution than the one hinted at. The key insight was factoring out $(a-b)$.
Section 1.2 Summary — Key Tools
ToolWhen to Use
Fundamental Theorem of ArithmeticAny problem about divisors, multiples, GCD, LCM
Trial division up to $\sqrt{n}$Checking primality / factorising specific numbers
Euclid's Lemma ($p \mid ab \Rightarrow p \mid a$ or $p \mid b$)Proofs involving prime divisibility
Legendre's formula $v_p(n!)$Factorials, binomial coefficients
Perfect power ↔ exponents check"Is $n$ a perfect square/cube?"
Algebraic factorisation ($a^2-b^2$, $a^3 \pm b^3$, etc.)Factoring large numbers or expressions
Mod 3 (or small mod) elimination"Find all primes $p$ such that..."
← Section 1.1: Divisibility & Factors Section 1.3: GCD & LCM →