China-TST-2023B

Proof. Let the solutions to the congruence equation $kx\equiv y(\mathrm{mod}p)$ in $S\times T$ be $(x_1,y_1),\dots ,(x_n,y_n)$, where $n\ge 1+\lambda s\ge 1$. Hence, we know that $S$ and $T$ are both non-empty, implying that $n\ge 2$. Since $T$ is contained in a complete residue system modulo $p$, we know that the $x_i$'s are distinct. Without loss of generality, let's assume $x_1<x_2<\cdots <x_n$. Let $u_i=x_i-x_1$ and $v_i=y_i-y_1$. Then we have $$k{u}_i\equiv v_i(\mathrm{mod}p),0\le u_i\le s,|v_i|\le t.$$ Let $a=\frac{u_2}{\gcd (u_2,v_2)}$ and $b=\frac{v_2}{\gcd (u_2,v_2)}$. Thus, $\gcd (a,b)=1$, and we have $$0<a\le s,|b|\le t,ka\equiv b(\mathrm{mod}p).$$ Combining with $k{u}_i\equiv v_i(\mathrm{mod}p)$, we obtain $$b{u}_i\equiv ka{u}_i\equiv a{v}_i(\mathrm{mod}p).$$ Let $b{u}_i=a{v}_i+p{w}_i$. Then we have $$|w_i|\le \frac{|b|s+at}{p}.$$ Let $L=\frac{|b|s+at}{p}$.

(1) If $L<1$, then $w_i=0$ for all $i$, and hence $b{u}_i=a{v}_i$. Since $\gcd (a,b)=1$, it follows that $u_i$ must be multiples of $a$. Combining with the fact that $u_i\in [0,s]$ are distinct non-negative integers, we have $$s\ge \max u_i\ge a(n-1)\ge a\lambda s,$$ which implies $a\le \frac{1}{\lambda }$. Furthermore, from $$at\ge \max |a{v}_i|=\max |b{u}_i|\ge |b|\cdot (a\lambda s),$$ we have $|b|\le \frac{t}{\lambda s}$.

(2) If $L\ge 1$, then $w_i$ can take at most $2L+1\le 3L$ integer values in the range $[-L,L]$. By the pigeonhole principle, at least $\frac{n}{3L}$ of the $w_i$'s take the same value. Let $E$ be the set of indices $i$ where $w_i$ takes the same value, and let $u_{i_0}$ be the smallest value in $\{u_i:i\in E\}$. From $$b(u_i-u_{i_0})=a(v_i-v_{i_0})+p(w_i-w_{i_0})=a(v_i-v_{i_0}),\forall i\in E,$$ we obtain $a\mid u_i-u_{i_0}$. Combining $0\le u_i-u_{i_0}=x_i-x_{i_0}\le s$, we have $$s\ge \underset{i\in E}{\max }(u_i-u_{i_0})\ge a(|E|-1).$$ Also, from $|v_i-v_{i_0}|=|y_i-y_{i_0}|\le t$, we have $$at\ge \max (a|v_i-v_{i_0}|)=|b|\underset{i\in E}{\max }(u_i-u_{i_0})\ge |b|(a(|E|-1)).$$ Note that $$L=\frac{|b|s+at}{p}\le \frac{2st}{p}<\frac{\lambda s}{6},$$ which implies $1<\frac{\lambda s}{6L}$. Thus, we have $$|E|-1\ge \frac{\lambda s}{3L}-\frac{\lambda s}{6L}=\frac{\lambda s}{6L}.$$ Substituting back into the previous inequalities, we obtain $$\lambda a\le 6L,\lambda |b|s\le 6Lt,$$ which leads to $$\lambda p=\frac{\lambda |b|s+\lambda at}{L}\le 12t,$$ contradicting the condition $t<\frac{\lambda p}{12}$!

Thus, we have shown that $L\ge 1$ is not possible, and only $L<1$ holds true in this case. $\square$