Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
    
That was really easy to follow. Thanks. –  Derek Scavo Nov 26 '10 at 2:54

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.