Skip to main content
1 of 2
Roland Bacher
  • 17.9k
  • 3
  • 45
  • 113

Reconstructing elements of $\mathbb Q$ in $\mathbb Z_p$

Can a rational number $a/b$ (with $b$ coprime to a prime number $p$) be recovered efficiently from a $p$-adic expansion of the form $$\frac{a}{b}=\sum_{j=0}^\infty x_jp^j,\ x_j\in\{0,\ldots,p-1\}\ ?$$

(The prime $p$ is typically fairly small.)

Suppose I have an approximation $\sum_{j=0}^Nx_jp^j$ congruent to $a/b\pmod{p^{N+1}}$ such that $N\log p>\log a+\log b$ (where the inequality is not too sharp, say the difference is at least equal to some not too small constant $C=C(p)$), can I recover $a$ and $b$ easily from its first $(N+1)$ $p$-adic digits $x_0,\ldots,x_n$ in $\{0,\ldots,p-1\}$?

In a perfect world this would be done by an analogue of the continued fraction expansion. I am ignorant if such a thing survived the Big-Bang.

This would be useful in some circonstances where $p$-adic computations are much easier than computations with real (or rational) numbers.

Roland Bacher
  • 17.9k
  • 3
  • 45
  • 113