0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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}$. $\endgroup$ – gammatester May 27 '18 at 18:34
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Johnny Bueti May 27 '18 at 20:25
  • $\begingroup$ 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? $\endgroup$ – Johnny Bueti May 27 '18 at 20:30
  • $\begingroup$ The reduction you describe is valid when $\gcd(4,79) = 1$, which it is. $\endgroup$ – Eric Towers May 28 '18 at 0:56
  • $\begingroup$ 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... $\endgroup$ – Eric Towers May 28 '18 at 0:59
  • $\begingroup$ 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? $\endgroup$ – Johnny Bueti May 28 '18 at 9:22

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.