Whats the fastest way of solving $85x=12\pmod{19}$. I can solve it but I want a quick way. I can use facts like $0=\pm19\pmod{19}$ but I am not that fast using that method.
Fastest way to solve linear congruent equation
4 Answers
$85x=12 \mod 19$ is the same as $9x=12 \mod 19$. Multiply by 2 to get $18x=24 \mod 19$ or $x=-24=14 \mod 19$
-
0$-24=-24+2*19=14 \mod 19$. – 2012-10-25
Hint $\displaystyle\rm\ mod\ 19\!:\ x\equiv \frac{12}{85}\equiv\frac{12}{17\cdot 5}\equiv\frac{12}{-2\cdot 5}\equiv\frac{-6}5\equiv \frac{-25}{5}\equiv \frac{-5}1$
Or: $\displaystyle\rm\ \ \,mod\ 19\!:\ x\equiv \frac{12}{85}\equiv\frac{12}{9}\equiv\frac{24}{18}\equiv\frac{5}{-1}\ \ $ (this is Gauss' algorithm)
Note that $85=9\ (\rm{mod}\ 19)$. So you're solving $9x=12\ (\rm{mod}\ 19)$. The fastest way would be to know an inverse of $9$ modulo $19$ (for example $17$) and multiply through by this inverse to get $x=12\cdot 17=14\ (\rm{mod}\ 19)$. Alternatively, expand the definition of a congruence to get $9x=12+19n,\ n\in\Bbb{Z}$, rewrite that as $9x-19n=12$, and solve it as you would solve a normal linear Diophantine equation.