Friday, 7 November 2014

elementary number theory - How do I solve 32xequiv12pmod82?



I am able to solve simpler linear congruences, for example 3x2(mod5). What I would do in this case is use that 010(mod5) and then utilising a theorem: 3x12(mod5). Then I can divide by 3 leaving me x4(mod5GCD(5,3))x4(mod5) which means the solution is x=4k+5 where kZ.




But I cannot apply the same method to this congruence:
32x12(mod82)


This is how far I got:
8x3(mod82GCD(82,4))


8x3(mod41)



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



EDIT:




What I found later is that I can say that
0205(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 8x3(mod41)8x3+41(mod41)8x44(mod41)÷42x11(mod41)2x11+41(mod41)2x52(mod41)÷2x26(mod41)x=41q+26


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...