# Computing linear congruence - Euclidean algorithm

I have the following linear congruence:

$$5037x \equiv 8 (mod 79)$$

how could I find the value of x?

If I were to use the Euclidean algorithm, wouldn't I find the multiplicative inverse of $5037 (mod 79)$? The algorithm though works for $5037x (mod 79) = 1$, is it the same for $8 (mod 79)$?

• You do not need the inverse of $8$ because you multiply both sides of the congruence with $5037^{-1} \pmod{79}$ and get $x\equiv 5037^{-1}\cdot 8\pmod{79}$. – gammatester May 27 '18 at 18:34

First, since we are working modulo $79$, we can reduce everything modulo $79$. $$5037 x \cong 8 \pmod{79}$$ becomes $$60 x \cong 8 \pmod{79} \text{.}$$ Now I'll describe the intention and plan of what we are doing because you seem a little muddled on these things. We wish we could divide $60$ from both sides of the congruence, but division isn't straightforward in modular arithmetic. In fact, it is more useful to talk in terms of multiplication and to say: We want a $u$ such that $u \cdot 60 \cong 1 \pmod{79}$ so that we may multiple both sides of our congruence by it to clear the coefficient on $x$, leaving $x$ alone on its side of the congruence. Notice that this $u$ is playing the role of "$1/60$" in the system of residues modulo $79$.
How do we find this $u$? We want a $u$ such that $$u \cdot 60 \cong 1 \pmod{79}$$ which is the same thing as we want a $u$ such that $$u \cdot 60 + k \cdot 79 = 1$$ for some integer $k$. This should look like the results of the extended Euclidean algorithm. One thing to check immediately: Is this equation satisfiable? We check this by computing $\gcd(60, 79) = 1$ and ensuring that it divides the right-hand side, which it does. If we are smart, we kept the coefficients in the GCD computation so we could immediately write $$-25 \cdot 60 + 19 \cdot 79 = 1 \text{.}$$ This means we also get a solution when we check that a solution exists (if we do the extra side work for the extended Euclidean algorithm). This equation says $$-25 \cdot 60 \cong 1 \pmod{79} \text{,}$$ so $u = -25 \cong 54$ is the $u$ we need.
So $$54 \cdot 60 x \cong x \pmod{79}$$ and using this in the original equation, $$x \cong 54 \cdot 60 x \cong 54 \cdot 5037 x \cong 54 \cdot 8 \cong 37 \pmod{79} \text{.}$$
• Thank you! Just a question – before applying the Euclidean algorithm to $60x \equiv 8 (mod 79)$, can I simplify the linear congruence first and apply the algorithm to $15x = 2 (mod 79)$? I did, and got -15 instead of -25, it also appears to be correct. – Johnny Bueti May 27 '18 at 20:25
• Also, if I were to multiply the inverse ($-15 \equiv 64 (mod 79)$) by $15$ in $15x \equiv 2 (mod 79)$ I would get $12$ instead of the $2$ that I expected. Is there something I'm (clearly) missing? – Johnny Bueti May 27 '18 at 20:30
• The reduction you describe is valid when $\gcd(4,79) = 1$, which it is. – Eric Towers May 28 '18 at 0:56
• By using the extended Euclidean algorithm, we find $-21 \cdot 15 + 4 \cdot 79 = 1$, so the multiplicative inverse of $15$ is $-21 \cong 58 \pmod{79}$. Beyond that, I don't understand the operation you are describing. "Multiply the inverse": additive or multiplicative inverse? inverse of what? It sounds as if you compute $15 \cdot -15 \cong 12 \pmod{79}$, but I don't know why you would do that, $-15$ isn't the multiplicative inverse of anything in sight... – Eric Towers May 28 '18 at 0:59
• The last step of Euclid's algorithm: $(4 \times 79) - (15 \times 21) = 1 \equiv 1 (mod 79)$ I considered $-15$ instead of $-21$... how do I recognise the one I need to use? Pretty sure this sounds beyond stupid. Also, I multiplied the "inverse" by $15$ and computed $mod 79$ of the result attempting to obtain the second term of the congruence as a further verification layer, is this what I should expect? – Johnny Bueti May 28 '18 at 9:22