# Solve the Congruence equation

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

-
add comment

## 2 Answers

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

-
discrete logarithm(mathworld.wolfram.com/DiscreteLogarithm.html) 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
add comment

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.

-
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
add comment