Tuesday 16 February 2016

elementary number theory - Problem with congruence equation $893x equiv 266 pmod{2432}$

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}...