Give a prime number $p>2023$. Let $r(x)$ be the remainder of $x$ modulo $p$. Let $p_1<p_2< \ldots <p_m$ be all prime numbers less that $\sqrt[4]{\frac{1}{2}p}$. Let $q_1, q_2, \ldots, q_n$ be the inverses modulo $p$ of $p_1, p_2, \ldots p_n$. Prove that for every integers $0 < a,b < p$, the sets $$\{r(q_1), r(q_2), \ldots, r(q_m)\}, ~~ \{r(aq_1+b), r(aq_2+b), \ldots, r(aq_m+b)\}$$have at most $3$ common elements.
Problem
Source: Polish MO Finals P5 2023
Tags: number theory, modular congruences, Modular inverse
TheMathBob
01.04.2023 22:13
It is easy to see that $q_i$ are different and for given $a,b$ there exists at most one index $i$ such that $q_i \equiv aq_i + b$ ($q_i \equiv b(a-1)^{-1}$ if $a > 1$). Now suppose that the sets have at least $4$ common elements. Then there exists indices $i_1,i_2,i_3$ and $j_1,j_2,j_3$ st. $q_{i_k} \equiv aq_{j_k}+b$ and $i_k \neq i_k$ for $k=1,2,3$. So we get
$$a \equiv \frac{q_{i_1} - q_{i_2}}{q_{j_1} - q_{j_2}} \equiv \frac{q_{i_1} - q_{i_3}}{q_{j_1} - q_{j_3}} \pmod p.$$Which gives us $(q_{i_1} - q_{i_2})(q_{j_1} - q_{j_3}) \equiv (q_{i_1} - q_{i_3})(q_{j_1} - q_{j_2}) \pmod p$.
Multiplying both sides with $p_{i_1}p_{i_2}p_{i_3}p_{j_1}p_{j_2}p_{j_3}$: $$p_{i_3}p_{j_2}(p_{i_2} - p_{i_1})(p_{j_3} - p_{j_1}) \equiv p_{i_2}p_{j_3}(p_{i_3} - p_{i_1})(p_{j_2}-p_{j_1}) \pmod p.$$Both numbers in absolute value is smaller than $\frac{1}{2}p$, because $p_i < \sqrt[4]{\frac{1}{2}p}$ for all these primes. That means we have equality between those numbers: $$p_{i_3}p_{j_2}(p_{i_2} - p_{i_1})(p_{j_3} - p_{j_1}) = p_{i_2}p_{j_3}(p_{i_3} - p_{i_1})(p_{j_2}-p_{j_1}).$$But now $p_{i_3}$ does not divide any of these numbers: $p_{j_2}$, $p_{j_3}$ and $p_{i_3} - p_{i_1}$, so $p_{i_3} ~ | ~ p_{j_2} - p_{j_1}$, so
$$p_{i_3} \leq |p_{j_2} - p_{j_1}| < \max\{p_{j_2},p_{j_1}\} \leq \max \{p_{i_1},p_{i_2},p_{i_3},p_{j_1},p_{j_2},p_{j_3}\}.$$Analogues we can prove for rest of primes, but this gives us a contradiction, because there is some $p$ which is the maximum.