Solving for Modular arithmetic Solve the equation $38z\equiv 21 \pmod {71}$ for z.
Little confused by the questions. My attempt is: $38 \odot z = 21.$ Then find the inverse of 38 from mod 71 and multiply both sides. Lastly, take the mod of RHS and solve for z. I could find the inverse of 38 by solving for the following: $gcd(38,21)=38x+21y=1.$ But this is somewhat a long process. First of all, am I thinking of computing the problem the write way? If so, is there a shorter algorithm for computing for the inverse of 38 instead of solving for $38x+21y=1?.$
 A: Just for a bit of variety, here is my "ad hoc" method for dealing with this sort of situation, especially when not near a computer or calculator:
Double both sides of 
$$ 38z \equiv 21 \pmod{71}$$
to get 
$$76z \equiv 42 \pmod{71}$$
i.e. 
$$5z \equiv 42 \pmod{71}$$
add $3\times 71$ to both sides (to get a multiple of 5 on the right):
$$5z \equiv 255 \pmod{71}$$
Divivde by 5, to get
$$z \equiv 51 \pmod{71}$$
(Note my "method" relies on the fact that 71 is prime)
A: What you describe is the standard approach. You're using the extended Euclidean algorithm to compute the $\gcd(38,71)$ to get the inverse of 38, right?
There are some ad-hoc things you can do to help a little bit; e.g. if you replaced $21$ with an even number that it's equivalent to, you could cancel a factor of $2$ from both sides. Or if you multiply the equation through by $2$ (and reducing), the problem becomes easier.
But at some point searching for ad-hoc techniques becomes more work than just computing things directly.
I don't see how solving $38x+21y=1$ will help at all, though.
A: What might be more helpful is to solve $38z+71x=1$. The algorithm I use is an extension of Euclid's algorithm: the Euclid-Wallis Algorithm:
$$
\begin{array}{r}
&&1&1&6&1&1&2\\\hline
1&0&1&-1&7&-8&15&-38\\
0&1&-1&2&-13&15&-28&71\\
71&38&33&5&3&2&1&0\\
\end{array}
$$
This says that
$$
\begin{align}
15\cdot71-28\cdot38&=1&\text{second to last column}\\
315\cdot71-588\cdot38&=21&\text{$21$ times line $1$}\\
-38\cdot71+71\cdot38&=0&\text{last column}\\
-27\cdot71+51\cdot38&=21&\text{$9\times$ line $3+$ line $2$}
\end{align}
$$
Thus, $51\cdot38\equiv21\pmod{71}$
A: mod $\,71\!:\ \dfrac{21}{38}\equiv \dfrac{42}{76}\equiv \dfrac{7\cdot \color{#c00}{6}}{5}\equiv \dfrac{7(\color{#c00}{-65})}{5}\equiv{7(-13)}\equiv -91\equiv -20$ 
