Number Theory for Olympiads — IOQM, RMO and INMO

Weightage: Number theory is one of the four olympiad areas (with algebra, combinatorics and geometry) and routinely supplies one or two problems in every stage from the IOQM to the INMO. The tools below are short, but a problem is solved by choosing the right one, so each section ends with a worked example.

1. Divisibility and the Euclidean algorithm

Write $a\mid b$ when $b=ka$ for an integer $k$. The greatest common divisor satisfies $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$, which is the Euclidean algorithm. Its reverse gives Bezout's identity: integers $x,y$ exist with $ax+by=\gcd (a,b)$.

Two consequences recur constantly:

• $\gcd (a,b)=1$ and $a\mid bc$ imply $a\mid c$.
• $ax+by=c$ has an integer solution exactly when $\gcd (a,b)\mid c$.

Also $\gcd (a,b)\cdot \mathrm{lcm}(a,b)=ab$, and $\gcd (2^m-1,2^n-1)=2^{\gcd (m,n)}-1$.

2. Modular arithmetic

Congruence $a\equiv b(\mathrm{mod}n)$ means $n\mid a-b$, and it respects addition, multiplication and powers. Division needs care: you may cancel a factor $c$ only if $\gcd (c,n)=1$.

Squares are restricted. A square is $0$ or $1(\mathrm{mod}4)$, $0,1$ or $4(\mathrm{mod}8)$, and $0$ or $1(\mathrm{mod}3)$. A cube is $0,\pm 1(\mathrm{mod}9)$. These facts kill many equations at once.

Worked example. The last two digits of $7^{2025}$: since $7^4=2401\equiv 1(\mathrm{mod}100)$ and $2025\equiv 1(\mathrm{mod}4)$, we get $7^{2025}\equiv 7(\mathrm{mod}100)$, so the last two digits are $07$.

3. Fermat, Euler and Wilson

For a prime $p$ and $p\nmid a$:

$a^{p-1}\equiv 1(\mathrm{mod}p)$

Euler's theorem generalises it: if $\gcd (a,n)=1$ then $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$, where

$\phi (n)=n{\prod }_{p\mid n}\left(1-\frac{1}{p}\right).$

Wilson's theorem: $(p-1)!\equiv -1(\mathrm{mod}p)$ for a prime $p$.

The order of $a$ modulo $n$ is the smallest $d$ with $a^d\equiv 1$, and it divides $\phi (n)$. Whenever $a^k\equiv 1$, the order divides $k$. This single fact solves most "find the smallest exponent" questions.

Worked example. Prove $30\mid n^5-n$. Factor as $n(n-1)(n+1)(n^2+1)$. It is even (consecutive integers), divisible by 3 (three consecutive integers), and by 5 because $n^5\equiv n(\mathrm{mod}5)$ by Fermat. Since 2, 3 and 5 are coprime, $30$ divides it.

4. The Chinese remainder theorem

If the moduli $m_1,\dots ,m_k$ are pairwise coprime, the system $x\equiv a_i(\mathrm{mod}{m}_i)$ has a unique solution modulo $m_1\cdots m_k$.

Worked example. Solve $x\equiv 2(\mathrm{mod}3)$, $x\equiv 3(\mathrm{mod}5)$, $x\equiv 2(\mathrm{mod}7)$. From the first and third, $x\equiv 2(\mathrm{mod}21)$, so $x=2,23,44,\dots$. Testing $23$: $23\equiv 3(\mathrm{mod}5)$. So $x\equiv 23(\mathrm{mod}105)$.

CRT also lets you prove statements prime by prime and combine them.

5. Valuations and lifting the exponent

Let $v_p(n)$ be the exponent of the prime $p$ in $n$. Legendre's formula gives:

$v_p(n!)=\lfloor \frac{n}{p}\rfloor +\lfloor \frac{n}{p^2}\rfloor +\cdots$

The lifting the exponent (LTE) lemma: for an odd prime $p$ with $p\mid x-y$ and $p\nmid xy$,

$v_p(x^n-y^n)=v_p(x-y)+v_p(n).$

For $p=2$ with $n$ even, $v_2(x^n-y^n)=v_2(x-y)+v_2(x+y)+v_2(n)-1$.

Worked example. Find $v_3(4^n-1)$. Here $3\mid 4-1$, so the lemma gives $v_3(4^n-1)=1+v_3(n)$. For $n=9$ the answer is 3.

6. Diophantine equations: the toolkit

Try these in order.

1. Factor. $x^2-y^2=45$ becomes $(x-y)(x+y)=45$. The positive pairs $(1,45),(3,15),(5,9)$ give $(x,y)=(23,22),(9,6),(7,2)$.
2. Parity and residues. Reduce modulo a small number to show there is no solution, such as $x^2+y^2=4k+3$.
3. Bounding. Show the sides are close for large variables, then check the few remaining cases.
4. Descent and Vieta jumping. For $a^2+b^2=k(ab+1)$ with positive integers, assume a minimal pair $a\ge b$, treat the equation as a quadratic in $a$, and replace $a$ by its other root $a^{\prime }=kb-a$. Minimality forces $b=0$ eventually, and that makes $k$ a perfect square.

Pythagorean triples are all of the form $(m^2-n^2,2mn,m^2+n^2)$ up to scaling, with $m>n$ coprime and of opposite parity.

7. Number theory in the IOQM

The IOQM asks for integer answers from 00 to 99, so these problems often end with a reduction modulo 100 or a count. Work out the structure, then compute carefully. In a count, test small cases first to confirm the pattern before generalising.

Common traps

• Cancelling a factor that shares a divisor with the modulus. $2x\equiv 2y(\mathrm{mod}6)$ gives $x\equiv y(\mathrm{mod}3)$ only.
• Applying Euler's theorem when $\gcd (a,n)\ne 1$.
• Using LTE without the condition $p\nmid xy$.
• Concluding from small cases. A pattern for $n\le 5$ is not a proof.
• Forgetting negative factor pairs in a factoring argument.

Memory aids

• "Order divides every exponent that gives 1": the order lemma.
• "Factor, reduce, bound, descend": the Diophantine checklist.
• "Squares: 0 or 1 mod 4": the most used residue fact.

Summary

Number theory rests on divisibility and gcd, congruences with Fermat and Euler, CRT for combining moduli, valuations with Legendre and LTE, and a Diophantine toolkit.

The skill is selection: look at the equation, pick the modulus or factorisation that exposes its structure, and prove every case.

Exam protocol

• Test small values to guess the structure before proving.
• State which theorem you use and check its conditions.
• Handle negative integers and zero explicitly.
• In the IOQM, double-check the final reduction modulo 100.