Track / Stage 8 / 111 of 180 #2451 of 2604

Problem 2451

IMO Shortlist mid-range; USAMO P2/P5

Number theory Difficulty 8.5 Prove it Chinese IMO National Team Selection Test · China · 2023

For positive integers $m, n$ , define
$S(m, n) = \{(a, b) \in \mathbb{Z}^2 \mid 1 \le a \le m, 1 \le b \le n, \gcd(a, b) = 1\}.$
Prove: for any positive integers $d, r$ , there exist integers $m, n$ not less than $d$ , such that $|S(m, n)| \equiv r \pmod{d}$ . Here, $|A|$ represents the number of elements in the finite set $A$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Let $n = d + r$ and $m = d \cdot (d+r) + 1$ . Then, for $1 \le b \le d+r$ , the number of integers in the range $1, 2, \dots, m$ that are coprime to $b$ is given by
$\frac{\varphi(b)}{b} \cdot d \cdot (d+r)! + 1.$
Note that $b$ divides $(d+r)!$ , so this number is congruent to $1$ modulo $b$ . Therefore,
$|S(m, n)| \equiv \sum_{b=1}^{d+r} 1 \equiv r \pmod{d}.$

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.