0
$\begingroup$

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

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

$\endgroup$
4
  • 4
    $\begingroup$ 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. $\endgroup$ Sep 7, 2019 at 3:49
  • $\begingroup$ Gerry, okay thanks! $\endgroup$
    – Peter Wang
    Sep 7, 2019 at 3:52
  • $\begingroup$ Not a duplicate. The modulus and the terms are not co-prime and there is ultimately no solution. $\endgroup$
    – fleablood
    Sep 7, 2019 at 4:57
  • $\begingroup$ I reopened it since the proposed dupe has little to do with this question. Please be more careful. $\endgroup$ Sep 7, 2019 at 13:06

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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