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