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