# Fastest way to solve linear congruent equation

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.

-

$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$

-
why is $x=−24=14\pmod{19}$?, are you dividing? – Vaolter Oct 25 '12 at 18:35
$-24=-24+2*19=14 \mod 19$. – i. m. soloveichik Oct 25 '12 at 19:30

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.

-