Saturday, June 10, 2017

elementary number theory - How do I solve $32x equiv 12 pmod {82}$?




I am able to solve simpler linear congruences, for example $3x \equiv 2 \pmod 5$. What I would do in this case is use that $0 \equiv 10 \pmod 5$ and then utilising a theorem: $3x \equiv 12 \pmod 5$. Then I can divide by $3$ leaving me $x \equiv 4 \: \left( \mathrm{mod} \: {\frac{5}{\mathrm{GCD}(5,3)}} \right) \quad \Longleftrightarrow x \equiv 4 \pmod{5}$ which means the solution is $x = 4k + 5$ where $k \in \mathbb{Z}$.



But I cannot apply the same method to this congruence:
$$ 32x \equiv 12 \pmod {82} $$
This is how far I got:
$$ 8x \equiv 3 \: \left( \mathrm{mod} \: \frac{82}{\mathrm{GCD}(82, 4)} \right) $$
$$ \Updownarrow $$
$$ 8x \equiv 3 \pmod {41} $$




What could I do next? Please provide solutions without the Euclidean algorithm.



EDIT:



What I found later is that I can say that
$$ 0 \equiv 205 \pmod {41} $$
And then I can add it to the congruence in question and divide by $8$.
So I guess my question is essentially 'How can I find a number that is a multiple of $41$ (the modulus) and which, if added to $3$ gives a number that is divisible by $8$?'



I reckon the Euclidean algorithm is something which gives an answer to these kinds of questions?!



Answer



Hint :you can do like this $$\quad{8x \equiv 3 \pmod {41}\\
8x \equiv 3+41 \pmod {41}\\8x \equiv 44 \pmod {41} \div4 \\
2x \equiv 11 \pmod {41}\\2x \equiv 11+41 \pmod {41}\\2x \equiv 52 \pmod {41}\div 2\\x \equiv 26 \pmod {41}\\x=41q+26}$$


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...