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 :(
Answer
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.
No comments:
Post a Comment