For teachers / Printable sets /Stage 9 · Number theory

Stage 9 · Number theory

10 problems · IMO P2/P5; hard shortlist · mathsolympiadprep.com

The answer key prints on its own page at the end.

Let $\mathcal{S}$ be a finite nonempty set of prime numbers. Let $1 = b_{1} < b_{2} < \cdots$ be the sequence of all positive integers whose prime divisors all belong to $\mathcal{S}$ . Prove that, for all but finitely many positive integers $n$ , there exist positive integers $a_{1}, a_{2}, \ldots, a_{n}$ such that
$\frac{a_{1}}{b_{1}} + \frac{a_{2}}{b_{2}} + \cdots + \frac{a_{n}}{b_{n}} = \left\lceil \frac{1}{b_{1}} + \frac{1}{b_{2}} + \cdots + \frac{1}{b_{n}} \right\rceil.$

Number theory Solution and answer checking →
Let $n$ be a positive integer with $b$ digits and $l, r$ be non-negative integers satisfying $l + r < b$ . We say that a positive integer number is a sub-divisor of $n$ , if it divides the number obtained by erasing the first $l$ and last $r$ digits of $n$ . (For example, sub-divisors of $143$ are $1$ , $2$ , $3$ , $4$ , $7$ , $11$ , $13$ , $14$ , $43$ and $143$ .) For any positive integer $d$ , let $A_d$ be the set of positive integers for which $d$ is not a sub-divisor. Find all positive integers $d$ for which the set $A_d$ is finite.

Number theory Solution and answer checking →
Let a simple polynomial function be a polynomial function $P(x)$ whose coefficients belong to the set $\{-1, 0, 1\}$ . Let $n$ be a positive integer, $n > 1$ . Find the smallest possible number of non-zero coefficients in a simple polynomial function of $n$ th order whose values at all integral arguments are divisible by $n$ .
Answer: 2.

Number theory Solution and answer checking →
Find all positive integers $a_0$ , $a_1$ , $a_2$ , $b_0$ , $b_1$ , $b_2$ such that
$a_2 b_2 n^2 + a_1 b_1 n + a_0 b_0$ divides $(a_2^{2017n} + b_2)n^2 + (a_1^{2017n} + b_1)n + (a_0^{2017n} + b_0)$ for any positive integer $n$ .

Number theory Solution and answer checking →
We call a positive integer $n$ whose all digits are distinct bright, if either $n$ is a one-digit number or there exists a divisor of $n$ which can be obtained by omitting one digit of $n$ and which is bright itself. Find the largest bright positive integer. (We assume that numbers do not start with zero.)

Number theory Solution and answer checking →
Given any $n$ ( $> 1$ ) coprime positive integers $a_1, a_2, \dots, a_n$ , denote $A = a_1 + a_2 + \dots + a_n$ . Let $d_i = (A, a_i)$ (the greatest common divisor), $i = 1, 2, \dots, n$ .
Let $D_i$ be the greatest common divisor of $\{a_1, a_2, \dots, a_n\} \setminus \{a_i\}$ , $i = 1, 2, \dots, n$ . Find the minimum of $\prod_{i=1}^n \frac{A - a_i}{d_i D_i}$ .
(posed by Zhang Sihui)

Number theory Solution and answer checking →
Let $m > 1$ be an integer. It is known that there exists a prime number in the interval $[2m - \sqrt{m} + 1, 2m]$ . Prove that among any $m$ pairwise distinct positive integers $a_1, a_2, \dots, a_m$ , there exist two numbers $a_i$ and $a_j$ ( $1 \le i, j \le m$ ) such that
$\frac{a_i}{(a_i, a_j)} \ge m,$
where $(a_i, a_j)$ denotes the greatest common divisor of the positive integers $a_i$ and $a_j$ .

Number theory Solution and answer checking →
Let $n$ be a positive integer. In this problem, we consider labellings of the squares of a chessboard of size $n \times n$ with the natural numbers from $1$ to $n^2$ such that every number is used exactly once. Given such a labelling, we say a positive integer is a rook product if it is the product of the labels of $n$ squares which have the property that if you place a rook on each of them, no two rooks will attack each other.
(Two rooks are attacking each other, if and only if they are in the same row or column.)
a. Let $n = 8$ . Determine whether there exists a labelling of an $8 \times 8$ chessboard such that the following condition is fulfilled: The difference of any two rook products is always divisible by $65$ .
b. Let $n = 10$ . Determine whether there exists a labelling of a $10 \times 10$ chessboard such that the following condition is fulfilled: The difference of any two rook products is always divisible by $101$ .

Number theory Solution and answer checking →
Let $a, b$ be integers, and let $P(x) = a x^{3} + b x$ . For any positive integer $n$ we say that the pair $(a, b)$ is $n$ -good if $n \mid P(m) - P(k)$ implies $n \mid m - k$ for all integers $m, k$ . We say that $(a, b)$ is very good if $(a, b)$ is $n$ -good for infinitely many positive integers $n$ .
a. Find a pair $(a, b)$ which is $51$ -good, but not very good.
b. Show that all $2010$ -good pairs are very good.
(Turkey)

Number theory Solution and answer checking →
Let $S \subset \{1, \dots, n\}$ be a nonempty set, where $n$ is a positive integer. We denote by $s$ the greatest common divisor of the elements of the set $S$ . We assume that $s \neq 1$ and let $d$ be its smallest divisor greater than $1$ . Let $T \subset \{1, \dots, n\}$ be a set such that $S \subset T$ and $|T| \geq 1 + \lfloor \frac{n}{d} \rfloor$ . Prove that the greatest common divisor of the elements in $T$ is $1$ .
Let $n$ ( $n \geq 1$ ) be a positive integer and $U = \{1, \dots, n\}$ . Let $S$ be a nonempty subset of $U$ and let $d$ ( $d \neq 1$ ) be the smallest common divisor of all elements of the set $S$ . Find the smallest positive integer $k$ such that for any subset $T$ of $U$ , consisting of $k$ elements, with $S \subset T$ , the greatest common divisor of all elements of $T$ is equal to $1$ .

Number theory Solution and answer checking →

Answer key — Stage 9 · Number theory

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

Prove it — see the worked solution open
Prove it — see the worked solution open
Prove it — see the worked solution open
Prove it — see the worked solution open
Prove it — see the worked solution open
Prove it — see the worked solution open
Prove it — see the worked solution open
Prove it — see the worked solution open
Prove it — see the worked solution open
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.