The specific problem at hand is $$34x \equiv 60 \bmod{98}$$ I reduced to get $$17x \equiv 30 \bmod{49}$$ and from this I have $$17x \equiv 30 \bmod{7}$$ which is easy to solve and yields $x \equiv 3 \bmod{7}$. How can I use this fact to help me solve the more complex equation? I know the solution will be of the form $7k + 3$, but how can I utilize this fact?
2 Answers
You can use your fact directly: plug in $7k+3$ for $x$ and continue solving!
More precisely, you can take $x=7k+3$ as the definition of the new variable $k$, and your calculation shows that $k$ is an integer. So you can continue solving congruences to determine the complete solution for $k$, which in turn gives you the complete solution for $x$.
-
$\begingroup$ So $17(7k+3) \equiv 30 \bmod{49}$. But that gives $k \equiv 5 \bmod{49}$. So I have $x = 7(49k_2 + 5) +3$ now, except I don't want the +3 anymore since the 45 is the solution... what am I doing wrong? $\endgroup$– AddisonMay 13, 2013 at 20:25
-
$\begingroup$ @Addison: you would just expand it. However, your calculation is wrong. I'm guessing what your work is, and I expect that in your "reduce" step you forgot to divide everything relevant by 7. $\endgroup$– user14972May 13, 2013 at 21:07
-
$\begingroup$ Ahh, I see. $k \equiv 6 \bmod{7}$. It works, thanks a lot! $\endgroup$– AddisonMay 14, 2013 at 1:19
This may be more than you need to know, but Hensel's Lemma is the big tool here. You have $f(x)=17x-30$, which you solved modulo 7, i.e. $f(3)\equiv 0\pmod{7}$. Because $f'(3)=17\not\equiv 0\pmod{7}$, there will be a unique solution modulo $7^2$. That solution will be $3+t7$, where $t$ is the unique solution to $f(3)/7+f'(3)t\equiv 0\pmod{7}$. In your case, $f(3)=21$ and $f'(3)=17$ so you want to solve $3+17t\equiv 0\pmod{7}$. This has solution $t=6$, so $3+6\cdot 7=45$ is the unique solution mod $49$.
If you wanted to solve it modulo $7^3$, you will again get a unique solution because $17$ remains nonzero modulo $7$. The answer will be $45+t49$, where $t$ is the unique solution to $f(45)/49+17t\equiv 0\pmod{7}$. That is, $15+17t\equiv 0\pmod{7}$, which has solution $t=2$. Hence $45+2\cdot 49=143$ is the unique solution mod $7^3=343$.
-
$\begingroup$ I'm in an upper level undergraduate course in number theory. While I'm sure it's an excellent solution, unfortunately my teacher wouldn't approve of the machinery used to arrive at it :( $\endgroup$– AddisonMay 13, 2013 at 20:13
-
$\begingroup$ You could ask; when I teach number theory to undergraduates I cover Hensel's lemma. $\endgroup$– vadim123May 13, 2013 at 20:20