### Solving a^{x}=b, where x is a p-adic integer and a >1, c > 0 are integers

This algorithm is due to Victor Scharaschkin.

One possible use is for creating good abc triples by virtue of the equation
(a^{x}-b)+b=a^{x}.

Let N=ord_{p}a and a^{N}=1+ep^{g}, where p does not divide e.

Then with a suitable definition of a^{x}, the equation a^{x}=b is soluble in the p-adic integers if and only if it is soluble in Z/p^{g} Z, in which case the solution is unique.

In the case of solubility, we find integer p-adic approximations n_{g}, n_{g+1}, ..., n_{g+k} to x.

The n_{i} satisfy for i ≥ g:
- a
^{ni} b (mod p^{i} )
- n
_{i+1} n_{i} (mod p^{i-g} ).

We have to restrict p to be less than 2^{32} – 2^{16}=4294901760 for the Shanks baby step/giant step algorithm to work.

*Last modified 25th March 2005*

Return to main page