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
    $\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$ – Gerry Myerson Sep 7 '19 at 3:49
  • $\begingroup$ Gerry, okay thanks! $\endgroup$ – Peter Wang Sep 7 '19 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 '19 at 4:57
  • $\begingroup$ I reopened it since the proposed dupe has little to do with this question. Please be more careful. $\endgroup$ – Bill Dubuque Sep 7 '19 at 13:06
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.