# 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?.$

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)

• Nice and well explained +1 – DonAntonio May 2 '13 at 22:32

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.

• The way I solved it took me some time. How would you solve it? – hjg hjg May 2 '13 at 22:08
• @hjg: I would solve it just the way you describe: do the $\gcd(38,71)$ calculation to solve $38x + 71y = 1$, then multiply through by $x$. I have more practice using the extended Euclidean algorithm, I suppose; it becomes pretty quick once you're used to it. – Hurkyl May 2 '13 at 22:12

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

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$