Finding unknown in modulo operation

Question

I have this question on a test

1) find d=gcd(77,50) using euclidean alg.

2)find s and t such that 77s+50t=d

3) use these results to find x such that 50x=4(mod77) Note:the qual sign should have 3 lines

For the first part i found d=1 no problem there, for 2nd part at took me some twinking but i found s=13 and t=-20. my question is first is there a shortcut to doing 2nd part fast without trying to plug in random numbers and two for the third part how do i find x using my previous results.

Answer 1

The general answer to your second part is that you use the Extended Euclidian Algorithm instead of the simple EA. From your result $s=13$ and $t=-20$ you know that the multipication modular inverse of 50 exist $$50\times (-20) + 77\times 13 = 1 \quad \Longrightarrow 50\times (-20) \equiv 50\times 57 \equiv 1 \pmod {77}$$ and is $57 \pmod {77}$. To solve the the third part you simply multiply with this inverse $$50x \equiv 4 \pmod {77}$$ $$\Longrightarrow 50^{-1}\times50 x\equiv 50^{-1}\times 4 \pmod {77}$$ $$\Longrightarrow x \equiv 50^{-1}\times 4 \equiv 57\times 4 \equiv 228 \equiv 74 \pmod {77}.$$ And as a check you verify that $$74\times 50 \equiv 3700 \equiv 4 \pmod {77}.$$

Answer 2

To answer your question about the second part, there isn't really a fast way to do this. There is an algorithm that will give you the answer, no guessing involved. As the other answer mentions, it's called the extended Euclidean algorithm. On Wikipedia, they give the "distilled" version, which is well-suited to running on a computer, but I seem to mess it up by hand every time I try. (Side note: A number theory course was one of the first times I wrote computer to do things that were relevant to me, and I would highly recommend doing this, if you're interested).

The idea is that you save your work from the standard Euclidean algorithm, and back-substitute like crazy. I'll show you the relevant, rewritten Euclidean algorithm, and some of the arithmetic for finding those coefficients.

\begin{align} 77 - 50 &=27 \\ 50 - 27 &=23 \\ 27 - 23 &= 4 \\ 23 - 5 \cdot 4&= 3 \\ 4 - 3 &= 1 \end{align}

It's definitely a lot of work, any way you slice it. We're going to climb up the list, so first, we'd replace the $3$ with $23-4\cdot5$, in our last equation:

$$ 4 - (23 - 4\cdot 5) =1. $$ Now, we have to replaced all instances of $4$ with $27 - 23$:

$$ 27 - 23 - (23 - (27 - 23)\cdot 5) =6\cdot 27 -7 \cdot 23 = 1. $$

We'd continue climbing up, next replacing the $23$, and so forth. Hopefully that's enough for you to get the gist of what we need to do. I can certainly provide the rest of the details, if you're interested. That's the idea behind finding those coefficients.