# power of ten modulo prime

In a mathematical quiz (that I solved by computational means), I came across the problem of finding powers k of ten with a given congruence to a given prime number, $$10^k \equiv q \text{ mod } (p)$$ as eg $$10^k \equiv 46 \text{ mod } (47)$$ and I wonder if there is a generic approach to this problem.

• Just for the record $\min k=23$ Other $k$ values $23,69,115,161,207,253,299,345,391,437,483,529,575,621,667,713,759,805,851,897,943,989,\ldots$ In general $k=23 (2 n-1)\forall k\in\mathbb{N}$. Quite interesting $10^k \equiv 96 \text{ mod } (97)$ has a similar set of solutions $k=48 (2 n-1)\forall n\in\mathbb{N}$. But this is not general for primes or composites integers. For the moment results seem quite random. I mean that they exist for $47$ and $97$ but not for 37. Doesn't depend on $4n+1$ or $4n+3$ primes. It's intriguing, anyway... – Raffaele Aug 25 '17 at 9:49
• @raffaele: if 10 is a primitive root mod p there are solutions, 10 is no primitive root mod 37. – gammatester Aug 25 '17 at 9:58
• @Raffaele: thank you for the example. Is there any generic result for 23=(47-2)/2 to be the solution or any link with Fermat's little theorem? For instance, when using 89 as the basis, 10⁴⁴≡1 (89) and 10²²≡-1 (89)... – Xi'an Aug 25 '17 at 12:19

## 1 Answer

This is discrete logarithm poblem. In your case there is another simple solution: You have $46 \equiv -1 \bmod {47}$. If $10$ would be a primitive root, you would have $10^{23} \equiv -1 \bmod {10},$ and $k=23$ is indeed a solution. For a general prime $p$ you would check $10^{(p-1)/2}.$

If you change your problem to $10^k \equiv 45 \bmod {47}$ a few iterations of Pollard's rho algorithm give $k=7$.

• Thanks for the $(p-1)/2$ solution, it works indeed. I had not thought of (-1)^2=1...! – Xi'an Aug 25 '17 at 10:54