For teachers / Printable sets /Stage 8 · Number theory

Stage 8 · Number theory

10 problems · IMO Shortlist mid-range; USAMO P2/P5 · mathsolympiadprep.com

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

1. Each positive integer $a$ undergoes the following procedure in order to obtain the number $d = d\left(a\right)$:

   (i) move the last digit of $a$ to the first position to obtain the numb er $b$;
   (ii) square $b$ to obtain the number $c$;
   (iii) move the first digit of $c$ to the end to obtain the number $d$.

   (All the numbers in the problem are considered to be represented in base $10$.) For example, for $a=2003$, we get $b=3200$, $c=10240000$, and $d = 02400001 = 2400001 = d(2003)$.)

   Find all numbers $a$ for which $d\left( a\right) =a^2$.

   *

   IMO Shortlist

   Number theory Solution and answer checking →

2. Determine all integers $n\geq 2$ having the following property: for any integers $a_1,a_2,\ldots, a_n$ whose sum is not divisible by $n$, there exists an index $1 \leq i \leq n$ such that none of the numbers $$a_i,a_i+a_{i+1},\ldots,a_i+a_{i+1}+\ldots+a_{i+n-1}$$ is divisible by $n$. Here, we let $a_i=a_{i-n}$ when $i >n$.

   *

   IMO Shortlist

   Number theory Solution and answer checking →

3. Find all positive integers $a,b,c$ and prime $p$ satisfying that
   $$2^a p^b=(p+2)^c+1.$$

   China Team Selection Test

   Number theory Solution and answer checking →

4. Proof that
   $$\sum_{m=1}^n5^{\omega (m)} \le \sum_{k=1}^n\lfloor \frac{n}{k} \rfloor \tau (k)^2 \le \sum_{m=1}^n5^{\Omega (m)} .$$

   China Team Selection Test

   Number theory Solution and answer checking →

5. Does there exist a finite set $A$ of positive integers of at least two elements and an infinite set $B$ of positive integers, such that any two distinct elements in $A+B$ are coprime, and for any coprime positive integers $m,n$, there exists an element $x$ in $A+B$ satisfying $x\equiv n \pmod m$ ?

   Here $A+B=\{a+b|a\in A, b\in B\}$.

   China Team Selection Test

   Number theory Solution and answer checking →

6. Find all triplets of positive integers $(a,m,n)$ such that $\text{a m 1 (a 1) n}$.

   IMO Shortlist

   Number theory Solution and answer checking →

7. Given a positive integer $n \ge 2$. Find all $n$-tuples of positive integers $(a_1,a_2,\ldots,a_n)$, such that $1<a_1 \le a_2 \le a_3 \le \cdots \le a_n$, $a_1$ is odd, and
   (1) $M=\frac{1}{2^n}(a_1-1)a_2 a_3 \cdots a_n$ is a positive integer;
   (2) One can pick $n$-tuples of integers $(k_{i,1},k_{i,2},\ldots,k_{i,n})$ for $i=1,2,\ldots,M$ such that for any $1 \le i_1 <i_2 \le M$, there exists $j \in \{1,2,\ldots,n\}$ such that $k_{i_1,j}-k_{i_2,j} \not\equiv 0, \pm 1 \pmod{a_j}$.

   China Team Selection Test

   Number theory Solution and answer checking →

8. Given positive integer $n$ and $r$ pairwise distinct primes $p_1,p_2,\cdots,p_r.$ Initially, there are $(n+1)^r$ numbers written on the blackboard: $p_1^{i_1}p_2^{i_2}\cdots p_r^{i_r} (0 \le i_1,i_2,\cdots,i_r \le n).$

   Alice and Bob play a game by making a move by turns, with Alice going first. In Alice's round, she erases two numbers $a,b$ (not necessarily different) and write $\gcd(a,b)$. In Bob's round, he erases two numbers $a,b$ (not necessarily different) and write $\mathrm{lcm} (a,b)$. The game ends when only one number remains on the blackboard.

   Determine the minimal possible $M$ such that Alice could guarantee the remaining number no greater than $M$, regardless of Bob's move.

   China Team Selection Test

   Number theory Solution and answer checking →

9. Let $a,b$ be two integers such that their gcd has at least two prime factors. Let $S = \{ x \mid x \in \mathbb{N}, x \equiv a \pmod b \}$ and call $y \in S$ irreducible if it cannot be expressed as product of two or more elements of $S$ (not necessarily distinct). Show there exists $t$ such that any element of $S$ can be expressed as product of at most $t$ irreducible elements.

   China Team Selection Test

   Number theory Solution and answer checking →

10. Four integers are marked on a circle. On each step we simultaneously replace each number by the difference between this number and next number on the circle, moving in a clockwise direction; that is, the numbers $a,b,c,d$ are replaced by $\text{a b,b c,c d,d a.}$ Is it possible after 1996 such to have numbers $a,b,c,d$ such the numbers $\text{|bc ad|, |ac bd|, |ab cd|}$ are primes?

    IMO Shortlist

    Number theory Solution and answer checking →

Answer key — Stage 8 · Number theory

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

1. $a = \underbrace{2\dots2}_{n \ge 0}1, \qquad a = 2, \qquad a = 3.$ open
2. $\text{All prime numbers}$ open
3. $(1, 1, 1, 3)$ open
4. $\sum_{m=1}^n 5^{\omega(m)} \le \sum_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \tau(k)^2 \le \sum_{m=1}^n 5^{\Omega(m)}$ open
5. $\text{No}$ open
6. ${(a,1,n),(1,m,n)} \text{ and }{(2,3,n)\text{ where }n>1}$ open
7. $(a_1, a_2, \ldots, a_n) \text{ where } a_1 = k \cdot 2^n + 1 \text{ and } a_2, \ldots, a_n \text{ are odd integers such that } 1 < a_1 \le a_2 \le \cdots \le a_n$ open
8. $M^{\lfloor \frac{n}{2} \rfloor}$ open
9. $t = \max \{ 2q, q - 1 + 2M \}$ open
10. $\text{No}$ 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.

Apache-2.0