Assuming a linear congruence:
ax≡b(modm)
It's safe to say that one solution would be:
x≡ba−1(modm)
Now, the first condition i memorized for a number a to have an inverse mod(m) was:
gcd
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