Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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} \,. $$

share|cite|improve this question

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

share|cite|improve this answer
discrete logarithm( can be applied to numbers having primitive roots. But $10^k$ does not have one if $k\ge 2$ – lab bhattacharjee Nov 22 '12 at 11:58

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.

share|cite|improve this answer
Is'nt Hensel Lemma defined for $f(x)$ where it is a polynomial but here we have $7^x$ – Mod Nov 22 '12 at 14:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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