# finite field to rational fraction

Suppose I have a number $n\in\mathbb F_p$, i.e. an element of the finite field obtained by arithmetic modulo some (odd) prime $p$. I'm looking for a way to find a simple description of $n$ as a fraction $\frac ab$. In other words, I'd like a way to obtain integers $a,b$ with

$$bn = a \pmod p$$

Obviously $a=n, b=1$ is one solution, but I'd like to find the pair which minimizes $\lvert ab\rvert$, which roughly corresponds to minimizing the number of digits involved in writing this down. $b$ must not be a multiple of $p$, though, as that would represent a division by zero in $\mathbb F_p$. I'd expect every result to satisfy the following constraints, which simply boils down to choosing signs reasonably, and canceling common factors:

\begin{gather*} \tfrac{1-p}{2} \leq a \leq \tfrac{p-1}{2} \\ 0 < b \leq \tfrac{p-1}{2} \\ \gcd(a, b) = 1 \end{gather*}

One possible way is enumerating all fractions satisfying the above conditions, and building a dictionary from these where $n$ can be looked up. But that becomes unfeasible for larger $p$.

Is there some better algorithm to find $a$ and $b$?

-
Interesting question! By the way, I think you should also add to your requirements that $\gcd(a,p)=\gcd(b,p)=1$, because otherwise $a=0$ and $b=p$ is a solution, and $|ab|=0$ in that case. –  Zev Chonoles Mar 8 '13 at 7:42
I think there's a result of Thue that says you can get $|ab|\le cp$ for some small constant $c$ like $2$ or $4$, but it would take some searching to track it down. It may be in Nagell's Number Theory textbook. Sorry, don't have my references handy. –  Gerry Myerson Mar 8 '13 at 12:39

There's a paper here which says Thue proved if $a$, $b$ and $m$ are relatively prime, then $$ax-by\equiv0\pmod m$$ can be solved by integers $x$ and $y$ such that $|x|\le\sqrt m$, $|y|\le\sqrt m$.
$a=1$, $b=n$ reduces to your congruence. The result's not exactly what you want, but surely Thue's method of proof will get you what you want.