3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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)

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

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.

$\endgroup$
  • $\begingroup$ The way I solved it took me some time. How would you solve it? $\endgroup$ – hjg hjg May 2 '13 at 22:08
  • $\begingroup$ @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. $\endgroup$ – Hurkyl May 2 '13 at 22:12
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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