For teachers / Printable sets /Stage 10 · Number theory

Stage 10 · Number theory

8 problems · Hardest shortlist tier · mathsolympiadprep.com

Print or save as PDF The answer key prints on its own page at the end.

1. Let $c \geqslant 1$ be an integer. Define a sequence of positive integers by $a_{1}=c$ and
   $$a_{n+1}=a_{n}^{3}-4 c \cdot a_{n}^{2}+5 c^{2} \cdot a_{n}+c$$
   for all $n \geqslant 1$. Prove that for each integer $n \geqslant 2$ there exists a prime number $p$ dividing $a_{n}$ but none of the numbers $a_{1}, \ldots, a_{n-1}$.

   IMO Shortlist

   Number theory Solution and answer checking →

2. For every $n \in \mathbb{N}$ let $d(n)$ denote the number of (positive) divisors of $n$. Find all functions $f: \mathbb{N} \rightarrow \mathbb{N}$ with the following properties:
   (i) $d(f(x))=x$ for all $x \in \mathbb{N}$;
   (ii) $f(x y)$ divides $(x-1) y^{x y-1} f(x)$ for all $x, y \in \mathbb{N}$.

   International Mathematical Olympiad Spain

   Number theory Solution and answer checking →

3. Define the sequence $a_1, a_2, a_3, \dots$ by $a_1 = 1$ and
   $$a_n = a_{\lfloor n/2 \rfloor} + a_{\lfloor n/3 \rfloor} + \dots + a_{\lfloor n/n \rfloor} + 1$$
   for $n > 1$. Prove that there are infinitely many $n$ such that
   $$a_n \equiv n \pmod{2^{2010}}.$$
   (This problem was suggested by Gabriel Carroll.)

   United States — Team Selection Test 2010

   Number theory Solution and answer checking →

4. For every positive integer $n$ with prime factorization $n=\prod_{i=1}^{k} p_{i}^{\alpha_{i}}$, define
   $$\mho(n)=\sum_{i: p_{i}>10^{100}} \alpha_{i}$$
   That is, $\mho(n)$ is the number of prime factors of $n$ greater than $10^{100}$, counted with multiplicity.
   Find all strictly increasing functions $f: \mathbb{Z} \rightarrow \mathbb{Z}$ such that
   $$\mho(f(a)-f(b)) \leqslant \mho(a-b) \quad \text{ for all integers } a \text{ and } b \text{ with } a>b .$$

   IMO Shortlist

   Number theory Solution and answer checking →

5. Let $\mathbb{Z}/n\mathbb{Z}$ denote the set of integers considered modulo $n$ (hence $\mathbb{Z}/n\mathbb{Z}$ has $n$ elements). Find all positive integers $n$ for which there exists a bijective function $g: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$, such that the 101 functions
   $$g(x),\ g(x) + x,\ g(x) + 2x,\ \dots,\ g(x) + 100x$$
   are all bijections on $\mathbb{Z}/n\mathbb{Z}$.

   USA IMO TST

   Number theory Solution and answer checking →

6. Determine all integers $n \geqslant 2$ with the following property: every $n$ pairwise distinct integers whose sum is not divisible by $n$ can be arranged in some order $a_{1}, a_{2}, \ldots, a_{n}$ so that $n$ divides $1 \cdot a_{1}+2 \cdot a_{2}+\cdots+n \cdot a_{n}$.

   IMO Shortlist 2021

   Number theory Solution and answer checking →

7. A hare and a tortoise run in the same direction, at constant but different speeds, around the base of a tall square tower. They start together at the same vertex, and the run ends when both return to the initial vertex simultaneously for the first time. Suppose the hare runs with speed $1$, and the tortoise with speed less than $1$. For what rational numbers $x$ is it true that, if the tortoise runs with speed $x$, the fraction of the entire run for which the tortoise can see the hare is also $x$?

   BMO Shortlist 2022

   Number theory Solution and answer checking →

8. Let $n$ be a positive integer. The integers $1, 2, 3, \ldots, n^{2}$ are to be written in the cells of an $n \times n$ board such that each integer is written in exactly one cell and each cell contains exactly one integer. For every integer $d$ with $d \mid n$, the $d$-division of the board is the division of the board into $(n / d)^{2}$ nonoverlapping sub-boards, each of size $d \times d$, such that each cell is contained in exactly one $d \times d$ sub-board.

   We say that $n$ is a cool number if the integers can be written on the $n \times n$ board such that, for each integer $d$ with $d \mid n$ and $1 < d < n$, in the $d$-division of the board, the sum of the integers written in each $d \times d$ sub-board is not a multiple of $d$.

   Determine all even cool numbers.

   IMO Shortlist

   Number theory Solution and answer checking →

Answer key — Stage 10 · Number theory

Worked solutions for every problem are on the site, one page per problem.

1. Prove it — see the worked solution open
2. Prove it — see the worked solution open
3. Prove it — see the worked solution open
4. Prove it — see the worked solution open
5. Prove it — see the worked solution open
6. Prove it — see the worked solution open
7. Prove it — see the worked solution open
8. Prove it — see the worked solution open

Problems belong to the competitions that set them. Each question on this sheet names the competition it came from, and the licences the material is used under are listed below. Free to copy for classroom use.

CC-BY-4.0