I am able to solve simpler linear congruences, for example 3x≡2(mod5). What I would do in this case is use that 0≡10(mod5) and then utilising a theorem: 3x≡12(mod5). Then I can divide by 3 leaving me x≡4(mod5GCD(5,3))⟺x≡4(mod5) which means the solution is x=4k+5 where k∈Z.
But I cannot apply the same method to this congruence:
32x≡12(mod82)
This is how far I got:
8x≡3(mod82GCD(82,4))
⇕
8x≡3(mod41)
What could I do next? Please provide solutions without the Euclidean algorithm.
EDIT:
What I found later is that I can say that
0≡205(mod41)
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 8x≡3(mod41)8x≡3+41(mod41)8x≡44(mod41)÷42x≡11(mod41)2x≡11+41(mod41)2x≡52(mod41)÷2x≡26(mod41)x=41q+26
No comments:
Post a Comment