I was trying to solve this congruence equation: $2ax+b\equiv 0 \pmod 5$. Here, $b$ is any integer and $a$ is an integer not divisible by $5$. Does a solution always exist? I don't understand why they have set the condition above on $a$. As should be clear from my other question on elementary number theory, I am not very good at it, and I have no idea where to begin when solving congruences. Any help would be much appreciated.
3
$\begingroup$
$\endgroup$
4
$\begingroup$
$\endgroup$
Perhaps you've come across the following theorem in your studies?
If $gcd(a,m)=1$, then there is an $x$ such that $ax\equiv 1\pmod{m}$, and any two such $x$ are congruent $\pmod{m}$. If $gcd(a,m)>1$, then there is no such $x$.
Essentially, this means an integer $a$ has a multiplicative inverse modulo $m$ if and only if it $a$ is relatively prime to the modulus $m$. This nice thing about primes is that if an integer $a$ is not divisible by a prime $p$, then it is relatively prime to that prime, as the only other common factor can be $1$.
So since $5\nmid a$, you know $gcd(a,5)=1$, and so there is some $x$, let's call it $\bar{a}$, such that $\bar{a}a\equiv 1\pmod{5}$. This allows you to solve for $x$ in this linear congruence. Note
$$2ax+b\equiv 0\Rightarrow 2ax\equiv -b\Rightarrow \bar{2}2ax\equiv -\bar{2}b\Rightarrow \bar{a}ax\equiv -\bar{a}\bar{2}b\Rightarrow x\equiv -\bar{2}\bar{a}b\equiv -3\bar{a}b\pmod{5}$$
Since $gcd(2,5)=1$, you also know that $2$ has a multiplicative inverse modulo $5$, namely $3$. This is the same reason why there is such a condition on $a$.
3
$\begingroup$
$\endgroup$
If $\ a\equiv 0\ $ then $\ b\equiv 0\:,\ $ so it wouldn't be solvable for $b\not\equiv 0$. Conversely, if $\ a\not\equiv 0 \ $ then $\ 1/a \equiv a^3\ $ since $\ a^4\equiv 1 \ $ by Fermat's little theorem, so you can cancel the leading coefficient and solve for $x$.
1
$\begingroup$
$\endgroup$
Solving the congruence in this particular example means, we need to get solution for $x$ as $x \equiv m (\bmod 5)$, where $m$ depends on $a$ and $b$.
Note that when $5|a$, we have $2ax \equiv 0 (\bmod 5)$. Hence, for arbitrary integer $b$, $2ax + b \equiv b (\bmod 5)$.
Hence, if we want a solution to exist for $2ax + b \equiv 0 (\bmod 5)$, then this forces $b$ to be $0 (\bmod 5)$, which is not necessarily true since $b$ is an arbitrary integer.
If you are getting started on Number Theory, then you could argue by cases. This will be a good exercise when you try to generalize this to other numbers.
Case 1:
Consider $a \equiv 1 (\bmod 5)$.
Then $ax \equiv x (\bmod 5)$, $2ax \equiv 2x (\bmod 5)$ and hence $2ax + b \equiv 2x+b (\bmod 5)$. And now we want this to be $0 (\bmod 5)$. So we need $2x + b \equiv 0 (\bmod 5)$.
Multiply the equation by $3$ and we get $6x + 3b \equiv 0 (\bmod 5)$. Now observe that $5x \equiv 0 (\bmod 5)$. Hence, we get $x + 3b \equiv 0 (\bmod 5)$.
(The reason you multiply by $3$ is $3 \times 2 \equiv 1 (\bmod 5)$. So $3$ is the inverse of $2$, when you are working in $(\bmod 5)$ setting. Also note that this gives you the reason why you couldn't do when $5|a$, since $5$ doesn't have an inverse in the $(\bmod 5)$ setting.)
So the solution is $x \equiv -3b (\bmod 5)$, when $a \equiv 1 (\bmod 5)$.Proceed via the same idea for other cases as well viz $a \equiv 2 (\bmod 5)$, $a \equiv 3 (\bmod 5)$, $a \equiv 4 (\bmod 5)$.You could then generalize this once you observe what is happening. Note that here since $5$ is a prime all the other elements will have inverses. Think what will happen when $5$ is replaced by '$n$' where '$n$' is a composite number.
