0
$\begingroup$

I want to calculate the value of $a$, given the equation:

$-8a\equiv 12 \mod26$

I know that i have to find the multiplicative inverse of $-8$, but since $\gcd(-8,26) \neq 1$, I suspect there can be 0 or many multiplicative inverses. Is this true ? I read the wiki page, but it only says that if $\gcd(-8,26) = 1$ then I have a unique modular inverse, but it doesn't explain what happens in the general case...

$\endgroup$
4
$\begingroup$

Note that$$-8a\equiv12\pmod{26}\iff-4a\equiv6\pmod{13}.$$Can you take it from here?

$\endgroup$
  • $\begingroup$ $a=5$ satisfy the congruence, however i calculated it by hand... $\endgroup$ – AleQuercia May 2 at 11:24
  • 1
    $\begingroup$ When the numbers are so small, that's quite natural. $\endgroup$ – José Carlos Santos May 2 at 12:02
  • $\begingroup$ Thanks so much, it's clear. I have only one doubt , if i have $ax \equiv 12 \space mod26$ , why at prior i know that x must range from [0,..,25] ? $\endgroup$ – AleQuercia May 2 at 14:00
  • $\begingroup$ If $ax\equiv12\pmod{26}$ and if $x'\in\{0,1,\ldots,25\}$ is such that $x\equiv x'\pmod{26}$, then $ax'\equiv ax\equiv12\pmod{26}$. $\endgroup$ – José Carlos Santos May 2 at 14:03
  • $\begingroup$ Mhm this is not clear, do you know a theorem about this ? $\endgroup$ – AleQuercia May 2 at 14:16
1
$\begingroup$

Well, the elements of the residue class ring ${\Bbb Z}_n$, $n\geq 2$, are the zero, the units, and the zero divisors. Units are not zero divisors and are given by the elements $a$ with $\gcd(a,n)=1$. So in your case, the element is a zero divisor and thus has no inverse.

$\endgroup$
  • $\begingroup$ However, $-8*5\equiv 12 \mod26$ ... $\endgroup$ – AleQuercia May 2 at 9:54
1
$\begingroup$

$$-8a\equiv 12\bmod 26\iff-4a\equiv 6\bmod 13\iff-2a\equiv3\equiv -10\bmod 13\\\iff -a\equiv-5\bmod 13\iff a\equiv 5\bmod 13$$

Therefore, a is 5 mod 13. Which is then either 5 or 18 mod 26.

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