Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

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

share|improve this answer
    
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.

share|improve this answer
1  
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

Your Answer

 
discard

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.