# Linear congruence $8x\equiv 21\pmod{24}$

$$8x\equiv 21\pmod{24}$$

I am having problem solving this linear congruence because 8 is even and 21 is odd.

• Rewriting the congruence as a divisibility statement, it says $24$ divides $8x-21$, which implies $2$ divides $8x-21$, but $2$ divides $8$, so it divides $8x$, so it must divide $21$ – but it doesn't. So what you have found is that there is no solution. Sep 7, 2019 at 3:49
• Gerry, okay thanks! Sep 7, 2019 at 3:52
• Not a duplicate. The modulus and the terms are not co-prime and there is ultimately no solution. Sep 7, 2019 at 4:57
• I reopened it since the proposed dupe has little to do with this question. Please be more careful. Sep 7, 2019 at 13:06

Method 1:

Just do it.

$$8x \equiv 21 \pmod {24}$$ so there is an integer $$k$$ so that

$$8x = 21 + k24$$

$$x = \frac {21}8 + 3k$$.

But $$3k$$ is an integer and $$\frac {21}8$$ is not.

So there is no solution.

Method 2:

We may have trouble as $$8,21$$ and $$24$$ aren't coprime so we will use the chinese remainder theorem.

If $$a \equiv b \pmod {mn}$$ then $$a\equiv b \pmod m$$ and $$a \equiv b\pmod n$$ (that's a basic result: If $$mn|a-b$$ then $$m|a-b$$ and $$n|a-b$$).

So we know $$8x \equiv 21 \pmod 3$$

$$2x \equiv 0 \pmod 3$$ and $$x\equiv 0 \pmod 3$$.

And we know $$8x \equiv 21 \pmod 8$$ so $$0\equiv 5\pmod 8$$ and that just isn't true. There is no solution.

Method 3:

By Bezout we know that $$ax + by = c$$ will have solutions if and only if $$c$$ is a multiple of $$\gcd(a,b)$$.

Another way of putting that is $$ax \equiv c\pmod b$$ if and only if $$c$$ is a multiple of $$\gcd(a,b)$$.

So $$8x \equiv 21 \pmod{24}$$ will have solutions if and only if $$21$$ is a multiple of $$\gcd(8,24) = 8$$. It is not.

....

Conclusion:

If $$\gcd (a,n) = 1$$ then there is a unique (up to congruence $$\mod n$$) $$a^{-1}$$ so that $$a^{-1}\cdot a \equiv 1 \pmod n$$.

Therefore $$ax \equiv b \pmod n$$ will have a unique (up to congruence $$\mod n$$) solution $$x \equiv a^{-1}b \pmod n$$.

If $$\gcd(a,n) = d\ne 1$$ then and $$d|b$$ then $$ax \equiv b \pmod n$$ will have $$d$$ unique (up to congruence $$\mod n$$) solutions. If you let $$a=a'd$$ and $$n = n'd$$ and $$b=b'd$$ the $$a'x \equiv b' \pmod {n'}$$ will have a unique solution. Call it $$w$$. Then $$w + n'k; k=0,.....,(d-1)$$ will be the $$d$$ unique solutions to $$ax \equiv b \pmod n$$.

I'll leave the conclusion's proof to you as an exercise.

There is no solution. In general, the congruence $$ax \equiv b \pmod m$$ has an integer solution if and only if $$b$$ is an integer multiple of $$\gcd(a,m)$$ (for integer $$a$$ and integer $$m \ge 1$$).