3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – Raffaele Aug 25 '17 at 9:49
  • 1
    $\begingroup$ @raffaele: if 10 is a primitive root mod p there are solutions, 10 is no primitive root mod 37. $\endgroup$ – gammatester Aug 25 '17 at 9:58
  • $\begingroup$ @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)... $\endgroup$ – Xi'an Aug 25 '17 at 12:19
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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