If $\gcd(a,n)=1$ then there exist integers $x,y$ such that $0<|x|,|y|<\sqrt{n}$ and $ax\equiv y \pmod n$

Question

If $a$ is integer and $n$ is positive integer such that $\gcd(a,n)=1$ then there exist integers $x,y$ for which $0<|x|,|y|<\sqrt{n}$ and $ax\equiv y\pmod n$.

By Dirichlet's principle I could found that $|x|,|y|\le \sqrt n $ but how to rule out $|x|=\sqrt n $ or $|y|=\sqrt n$?

Answer 1

You can use the pigeonhole principle. There are $2\lceil \sqrt n \rceil-2$ choices for each of $x,y$, so $(2\lceil \sqrt n \rceil-2)^2 \gt n$ ways to try to match them up. At least one will match.

Answer 2

If you're assuming that $x$ and $y$ are positive, then the problem statement is false for $a=3$, $n=4$.

But the absolute value signs suggest that we should also consider negative integers. This fixes the problem, because it gives us enough freedom to guarantee a pair $(x,y)$ in the appropriate range using the pigeonhole argument.