Tuesday, 16 February 2016

elementary number theory - Problem with congruence equation 893xequiv266pmod2432

I'm trying to solve 893x \equiv 266 \pmod{2432}.



Firstly, I find the \operatorname{gcd}(893, 2432) using the extended Euclidean Algorithm. When I calculate this, I receive that the gcd is (correctly) 19, and that 19 = 17(2432) -49(893). From this, I know that there are 19 distinct solutions.




I then divide my above, initial congruence by the gcd, obtaining 47x \equiv 14 \pmod{128}.
I know that \operatorname{gcd}(129, 47) = 1 and that 1 = 18(128) - 49(47).
Therefore 14 = 14(18)(128) -14(49)(47).



This implies that a solution to the congruence 47x \equiv 14 \pmod{128} is x = -14(49) = -686.
-686 ≡ 82 \pmod{128}, so I substitute x = -14(49) for x = 82.



From this, I gather then that the solution to the congruence is 82 + 128t, where t is one of 0,1,2,...,18. However, I believe this is not correct.



Where did I go wrong, and how might I go about fixing this?




Thank you so much!

No comments:

Post a Comment

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

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