Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

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

share|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.