0
$\begingroup$

Assuming a linear congruence:

$ax\equiv b \pmod m$

It's safe to say that one solution would be:

$x\equiv ba^{-1} \pmod m$

Now, the first condition i memorized for a number $a$ to have an inverse $mod(m)$ was:

$\gcd(a,m) = 1$

Which stems from the fact (and correct me here) that a linear congruence has solution if that gcd divides $b$. Since on an inverse calculation we have:

$ax\equiv 1 \pmod m$

The only number that divides one is one itself, so it makes sense.

Now comes the part that annoys me most:

"If the condition that tells us that there is an inverse $mod (m)$ for $a$ says that $\gcd(a,m)=1$, then how come linear congruences where the $\gcd(a,m) \ne 1$ have solution? Why do we say that a linear congruence where $\gcd(a,m) = d > 1$ has d solutions? If you can't invert $a$, then you can't do this:"

$ax\equiv b \pmod m \implies x\equiv ba^{-1} \pmod m $

Please help on this one. It's kinda tormenting me :(

$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

The long and the short of it is: $ax \equiv b \pmod m$ has solutions iff $\gcd(a,m)$ divides $b$.

As you said, if $\gcd(a,m) = 1$, then we can multiply by the inverse of $a$ to get our (unique!) solution.

But if $\gcd(a,m) = d > 1$, we still have a chance at finding solutions, even though there is no inverse of $a$ mod $m$.

Assume $d \mid b$.

Then there are integers $a', m', b'$ such that $a = da'$, $b = db'$, and $m = dm'$. $$ax \equiv b \pmod m \iff a'x \equiv b' \pmod{m'} $$

But since $d$ was the GCD of $a$ and $m$, we know $\gcd(a', m') = 1$, and we can construct a solution mod $m'$. For notation's sake, let $c$ be an integer such that $ca' \equiv 1 \pmod {m'}$. $$a'x \equiv b' \pmod{m'} \iff x \equiv b' c \pmod {m'}$$

Now we can "lift" our solution mod $m'$ to many solutions mod $m$.: $$ x \equiv b' c \pmod {m'} \iff \exists k \quad x \equiv b'c + km' \pmod m $$

Say there is a solution to the congruence. Then $ax \equiv b \pmod m$ implies that for some $k$, $ax + km = b$. But if $d$ divides $a$ and $m$, it must also divide $b$.

So it is a necessary and sufficient condition.

$\endgroup$
7
  • $\begingroup$ After $x\equiv b'c\pmod {m'}$, we can also use the Chinese Remainder Theorem. $x\equiv b'c\pmod {m'}\implies ax\equiv ab'c\pmod {m'}$ and we have the system of linear congruences $$\begin{cases}ax\equiv ab'c\pmod {m'}\\ ax\equiv 0\pmod {d}\end{cases}\implies ax\equiv ab'cd\cdot (d^{-1}\mod m')\pmod m$$ After checking this solution, we see it works. $\endgroup$
    – user26486
    Aug 19, 2014 at 21:03
  • $\begingroup$ thank you guys for the explanation. I am asking this question because i am studying cryptography. Modular arithmetic is kinda new to me so please bear with me.I am not sure if my main question has been answered. If you need an inverse to solve a linear congruence $x\equiv ba^{-1} \pmod m$, how can you solve it if $a$ is not invertible since $\gcd(a,m) \ne 1$?. I mean, it's like you telling me that a regular equation $a*x = b$ (no mod) has a solution but you can't invert $a$ $\endgroup$
    – BrunoMCBraga
    Aug 19, 2014 at 21:39
  • $\begingroup$ Are you asking "how can it have a solution" or "how can we find the solutions"? I answered the latter above, but as for the former: The point is that you don't need an inverse. For example, it's pretty easy to find a solution to $2x \equiv 4 \pmod {10}$, even though $2$ and $10$ are not coprime (note that there's another solution though: $7$). This is one of those intuitions that can easily be built by trying lots of examples. $\endgroup$
    – Henry Swanson
    Aug 19, 2014 at 21:46
  • 1
    $\begingroup$ But such an equation can have solutions. Let $a = 2$ and $b = 4$. You can't invert $2$ in the integers, but there's definitely a solution. (Admittedly, this is a bit unsatisfying as a response, because we can just pass to $\mathbb{Q}$, and find an inverse there. I'll have to think of a better example. How much do you like matrices?) $\endgroup$
    – Henry Swanson
    Aug 19, 2014 at 21:52
  • $\begingroup$ How can it have a solution? You tell me: You know, to get the inverse $(mod m)$ of a number $a$, you have to check that $GCD(a,m)=1$.To solve $x\equiv ba^{-1} \pmod m$ you have to check that $d = GCD(a,m)$ and $d | b$. If this checks, you have $d$ solutions. I say: But...how are you going to solve $x\equiv ba^{-1} \pmod m$ if the $GCD(a,m)=1$ rule for inverse existence fails?(assuming it fails) If there is no inverse, there is no solution. This is my problem $\endgroup$
    – BrunoMCBraga
    Aug 19, 2014 at 22:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .