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?.$
$\begingroup$ $\endgroup$
Add a comment |
4 Answers
$\begingroup$ $\endgroup$
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)
- 1$\begingroup$ Nice and well explained +1 $\endgroup$DonAntonio– DonAntonio2013-05-02 22:32:31 +00:00Commented May 2, 2013 at 22:32
$\begingroup$ $\endgroup$
2 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.
- $\begingroup$ The way I solved it took me some time. How would you solve it? $\endgroup$hjg hjg– hjg hjg2013-05-02 22:08:34 +00:00Commented May 2, 2013 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$user14972– user149722013-05-02 22:12:37 +00:00Commented May 2, 2013 at 22:12
$\begingroup$ $\endgroup$
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}$
$\begingroup$ $\endgroup$
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$
