Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
1  
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
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.