Short Primitive Vectors in a Lattice in $\mathbb{Z}^2$ 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$.
 A: Edit: this answer inorrectly conflates multiplication and divison tables mod n so be warned that the proofs of the claims are wrong.  I will edit when time permits.
For now, let me rephrase the problem in terms of a well known series of investigations in analytic number theory.  I will show why $n^\frac{1}{2}$ cannot work and why I believe $n^{\frac{1}{2}+\epsilon}$ can.
Reduction:
Since we are asking for coprime $x,y$ satisfying $ax\equiv y\pmod{n}$, we must also demand $(x,n)=(y,n)=1$.  The reason is the following:
By Bezout, $kx+ly=1$.  From the congruence, we get $$alx = 1-kx\pmod{n}$$ so $$(al+k)x\equiv 1\pmod{n} $$ so $x$ necessarily has to be invertible, same with $y$.
So the problem reduces to finding the smallest $N$ such that for every $a<n$ with $(a,n)=1$ we can find a pair $x,y$ coprime to each other and $n$, between $1$ and $N$, such that $$ax\equiv y\pmod{n} $$ or equivalently, such that $$a \equiv x^{-1}y\pmod{n}. $$
Definition: The multiplication table of size $N$, denoted $\mathcal{M}(N)$ is the $N\times N$ array with $(i,j)$ entry equal to $ij$.  The mod n multiplication table $\mathcal{M}_n(N)$ is the array with $(i,j)$ entry equal to $ij\mod{n}$.
Claim: The optimal $N$ for the problem is the smallest $N$ for which $\mathcal{M}_n(N)$ has at least $\phi(n)$ distinct entries coprime to $n$.
Proof: If $a\equiv x^{-1}y$ has a solution for all $a$ coprime to $n$ then there are at least $\phi(n)$ distinct ratios and thus $\phi(n)$ distinct products coprime to $n$.  Vice versa, if there are $\phi(n)$ distinct products coprime to $n$, then $a \equiv yz$ so $az^{-1}\equiv y\pmod{n}$ and if $z^{-1}$ and $y$ share common factors, we can just drop them since these factors will not be factors of $n$.
$\square$
Claim: $N$ cannot be as small as $\sqrt{n}$.
Proof: Look at the $N\times N$ multiplication table.  Its invertible entries are all smaller than $n$ so we can identify $\mathcal{M}_n(\sqrt{n})=\mathcal{M}(\sqrt{n})$, the integer multiplication table.  The result follows now from the following two facts:
Proposition: There exists $C>0$ such that for every $n>2$, $$\phi(n) \geq C \frac{n}{\log\log{n}}.$$  This is a well known estimate for the Euler function.
Proposition: The number of distinct entries in $\mathcal{M}(\sqrt{n})$ is smaller than $\frac{n}{\log^c{n}}$ for appropriate $c>0$.  This is a fairly recent result that follows from a sharper estimate of Kevin Ford's.
Combining the two theorems we see that the number of distinct entries, $\frac{n}{\log^c{n}}$, is beaten by the number of elements we demand to be distinct ($C \frac{n}{\log\log{n}}.$).
$\square$
Conjecture (bold conjecture!): for every $\epsilon>0$ there exists $n_0$ such that for all $n>n_0$, the number of distinct elements in $\mathcal{M}_n(n^{\frac{1}{2}+\epsilon})$ is sufficient to beat the demands for $a$.  From the reductions above we see that the conjecture is actually equivalent to your problem.  
I think it is true: if we had $\mathcal{M}(n^{\frac{1}{2}+\epsilon})$ rather than the mod n version, we know there are sufficiently many entries, even coprime to $n$.  Now I just need to think about the mod n reduced problem, but maybe you or some other answerer can beat me!  After all, the reduction mod n does not create too many overlaps for $N$ still near $\sqrt{n}$, we just need exact control.
I need to write and prepare a midterm now, so I may take some time to update.
