Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

share|cite|improve this answer
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)

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.