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. Given an integer $n > 1$ and an integer $a$ that is coprime with $n$. There is a country consisting of $n$ islands $D_1, D_2, \dots, D_n$. For any two different islands $D_i$ and $D_j$, there is a one-way ferry from $D_i$ to $D_j$ if and only if $ij \equiv ia \pmod{n}$. A tourist hopes to visit as many islands as possible. He can first fly to any island he chooses to start the tour, and afterwards can only use the one-way ferry to tour freely between islands in this country. Find the maximum possible number of different islands that the tourist can visit.

   Number theory Solution and answer checking →

2. Let $n$ be a positive integer. We say that a polynomial $P$ with integer coefficients is $n$-good if there exists a polynomial $Q$ of degree 2 with integer coefficients such that $Q(k)(P(k)+Q(k))$ is never divisible by $n$ for any integer $k$.
   Determine all integers $n$ such that every polynomial with integer coefficients is an $n$-good polynomial.

   Number theory Solution and answer checking →

3. Given a positive integer $n$, let $D$ be the set of positive divisors of $n$, and let $f: D \to \mathbb{Z}$ be a function. Prove that the following are equivalent:
   (A) for any positive divisor $m$ of $n$,
   $$n \mid \sum_{d|m} f(d) \binom{n/d}{m/d};$$
   (B) for any positive divisor $k$ of $n$,
   $$k \mid \sum_{d|k} f(d).$$

   Number theory Solution and answer checking →

4. Fix an integer $n \ge 2$. Find all $n$-tuples $(a_1, a_2, \dots, a_n)$ of integers satisfying the following two conditions:
   (1) $a_1$ is odd, $1 < a_1 \le a_2 \le \dots \le a_n$, and $M = \frac{1}{2^n}(a_1 - 1)a_2 \dots a_n$ is an integer; and
   (2) there exist $M$ different $n$-tuples $(c_{i,1}, c_{i,2}, \dots, c_{i,n})$ with $i = 1, 2, \dots, M$, such that for all $1 \le i < j \le M$, there exists $k \in \{1, 2, \dots, n\}$ such that
   $$c_{i,k} - c_{j,k} \not\equiv -1, 0, 1 \pmod{a_k}.$$

   Number theory Solution and answer checking →

5. 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}$.

   Number theory Solution and answer checking →

6. 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 .$$

   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$?

   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.

   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 and are reproduced from open datasets under their licences; every problem page names its source. Free to copy for classroom use.