Cross-posted from M.SE.

Given $a,n$ coprime positive integers, let $L = \{(x,y)\in \mathbb{Z}^2, ax=y(n)\}$ be the lattice of all points satisfying $ax=y\pmod{n}$.

I want to find an order-of-magnitude bound on the shortest (minimizing say $\max(|x|,|y|)$) vector in $L$ with $x,y$ coprime. If you restrict to merely finding a nonzero vector an easy pigeonhole argument gives a bound of the form $|x|,|y|\ll\sqrt{n}$. Is this still true if we require additionally that $x,y$ are coprime? In particular note that just because $(x,y)$ is in the lattice doesn't mean $(x/g,y/g)$ is, where $g$ is their greatest common divisor - problems can occur if $g$ has common factors with $n$.

Explicitly can anyone prove the existence of a primitive point $|x|,|y|\ll n^{1/2+\varepsilon}$?

Note that if $a\ll \sqrt{n}$ then the problem is trivial by picking $(x,y)=(1,a)$. I am interested in bounds for generic $a\in (\mathbb{Z}/n\mathbb{Z})^\times$.

Here are my ideas so far to reduce to a character sums bound.

We want to show that the number $S(a)=\#\{ax\equiv y (n): |x|, |y| \le N, x,y$ coprime to n$\}$ is nonzero; then $N$ is an upper bound for the primitive point's size. By discrete Fourier analysis against the Dirichlet characters mod $n$,

$$S(a)=\frac{\phi(N,n)^2}{\phi(n)} + \frac{1}{\phi(n)}\sum_{\chi \ne \chi_1} \Big |\sum_{|y| \le N} \chi(y)\Big|^2 \chi(a)^{-1}.$$

Here $\phi(N,n)$ is the number of $|y|\le N$ coprime to $n$.

Applying Polya-Vinogradov to the inner sums just misses a nontrivial bound - is there any bound on these short character sums on average, twisted by $\chi(a)^{-1}$? This method seems doomed to fail because the choice of $a=1$ gives a large (positive) error term.