1
$\begingroup$

Well I had come across a problem where I have to solve the below equation . Is there any direct relation like f(k,r) = n ? How to find n for given value of k and r ?

$ 7^{n}\equiv r \pmod{10^k} \,. $

2 Answers 2

1

This is a special case of the discrete logarithm problem. In general, it's hard to solve.

  • 0
    discrete logarithm(http://mathworld.wolfram.com/DiscreteLogarithm.html) can be applied to numbers having primitive roots. But $10^k$ does not have one if $k\ge 2$2012-11-22
1

EDIT: As Mod points out in the comments, the Lemma I cite is for polynomial, not exponential congruences. The technique of lifting iteratively to congruences modulo higher and higher powers of the modulus might still work, but I am not confident. I leave the answer, anyway, in the hope that someone will salvage something from it (or conclusively demolish it).

Given $k$ and $r$, first solve $7^n\equiv r\pmod{10}$ This will have solutions only if $r$ is $1$, $7$, $9$, or $3$, the solutions being $0$, $1$, $2$, $3$, respectively.

Then use Hensel's Lemma to lift to a solution of $7^n\equiv r\pmod{10^k}$. Hensel's Lemma is discussed in Number Theory texts, an undoubtedly on many websites. Usually, it is only presented for calculations modulo prime powers; you can make use of that by solving $7^n\equiv r\pmod{2^k}{\rm\ and\ }7^n\equiv r\pmod{5^k}$ and then applying the Chinese Remainder Theorem.

  • 1
    Is'nt Hensel Lemma defined for $f(x)$ where it is a polynomial but here we have $7^x$2012-11-22