Library / /2 of 10

, 2023

Number theory Difficulty 8.5 Shortlist Prove it China

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

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.