# Analytically controlling sizes in modular arithmetic to demonstrate Dirichlet pigeonhole application

Given $$a,b,c,d\in\mathbb Z$$ with $$ad+bc=p$$ a prime there is an $$m\in\mathbb Z$$ with $$-\lceil1+\sqrt{p}\rceil< r_1,r_2<\lceil1+\sqrt{p}\rceil$$ and $$r_1\equiv mac\bmod p$$ $$r_2\equiv mbd\bmod p$$ where $$r_1,r_2$$ are interpreted as in $$[-\frac p2,\frac p2]$$ by Dirichlet's pigeonhole principle.

1. Is there any closed form for such an $$m$$ and hence $$r_1$$ and $$r_2$$ as well?

2. Can we canonize an expression that provides an unique $$m$$ that works for a given $$a,b,c,d$$ at least under unimodular condition of $$ad-bc=1$$ (there may be multiple $$m$$'s however I am asking if we can isolate an expression that works always providing an unique $$m$$)?

3. Say if 1. and 2. fails then at least is there a $$\mathsf{polylog}(|a|+|b|+|c|+|d|)$$ time algorithm to find such an $$m$$ that does not involve linear integer programming (with linear integer programming there is Lenstra's method which is not very practical)?

• Doesn't e.g. $|r_1|\lt\lceil1+\sqrt{p}\rceil$ immediately subsume $r_1\in [-p/2, p/2]$? – Steven Stadnicki Oct 6 at 18:49
• The range is to stress that the modulus is not defined from $0$ to $p-1$. – 1.. Oct 6 at 19:36

For 3. one might use the $$LLL$$ algorithm to find the shortest vector to the row space of the equations $$\begin{bmatrix}bd&-ac&-p\\1&0&0\\0&1&0\end{bmatrix}\begin{bmatrix}r_1\\r_2\\k\end{bmatrix}=\begin{bmatrix}0\\r_1\\r_2\end{bmatrix}.$$