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