solving simultaneous linear congruences and simplifying the mod

Question

I wanted to solve the following:

$x\equiv2 (\text{mod 3})$

$x\equiv5 (\text{mod 6})$

$x\equiv7 (\text{mod 8})$

I rewrote the first congruence as $x=2+3a$ and in (mod 6), this can be written $2+3a\equiv5(\text{mod 6})$, which has solution $a\equiv1 (\text{mod 6})$, which implies $a=1+6k$.

Substituting this in for our first expression for $x$ gives $x=5+18k$ which can be written as $x\equiv5 (\text{mod 18})$.

I repeated this process with new expression for $x$ and the expression mod 8 and found that $x\equiv23 (\text{mod 144})$, however apparently the answer is $x\equiv23 (\text{mod 24})$. I am confused about how they simplified the mod?

Answer 1

As lulu explained in a comment, when moduli are not relatively prime, simultaneous congruences could be redundant or contradictory. In your case, $\color{blue}3$ and $\color{blue}8$ are relatively prime, but $6$ is not, and as long as $x\equiv2\pmod3$ and $x\equiv7\pmod8$, then $x\equiv-1\pmod3$ and $x\equiv-1\pmod2$, so $x\equiv-1\pmod6$, and $x\equiv5\pmod6$ is redundant. That is how the answer became modulo $\color{blue}3\times\color{blue}8=24$.

Answer 2

Chinese remainder thereom says we can solve a system uniquely for the product of the moduli if the moduli are relatively prime. In this case the are not relatively prime. But, if the equations are consistent, we can solve them uniquely for the least common multiple of the moduli... if the equations are consistent.

We can solve this for $\pmod {\operatorname{lcm}(3*6*8)= 24}$. but breaking $24$ into relatively prime components $3*8$.

The thing to keep in mind is that if $a\equiv k \pmod {mn}$ then $a\equiv k \pmod n$ (because $mn|a-k$ so $n|a-k).

So $x \equiv 2 \pmod 3$

And $x \equiv 5\pmod 6$ so $x\equiv 5\equiv 2\pmod 3$. (Two things to note: 1) this is why the equations must be consistent. if we had $x \equiv 2\pmod 3$ and $x \equiv 4\pmod 6$ we'd have $x \equiv 4\equiv 1 \pmod 3$ and that would not be consistent. $x\equiv 2 \pmod 3$ and $x\equiv 4 \pmod 6$ is not possible. 2) We also have $x\equiv 5\equiv 1\pmod 2$. But we don't need that.)

So $x \equiv 2\pmod 3$.

And $x \equiv 7\pmod 8$.

so we can solve those to and get a unique solution $x \equiv 23\pmod {24}$.

.... oh, I get what they were getting at....

Tangential aside:

$x \equiv 2\equiv -1\pmod 3$ and $x \equiv 5\equiv -1 \pmod 6$ and $x\equiv 7\equiv -1 \pmod 8$

So we have $x \equiv -1 \pmod{ 3,6,8}$.

And if $x\equiv k \pmod m$ and $x\equiv k \pmod n$ and we want to know a (not necessarily unique solution) to $x \equiv ???? \pmod {W}$ then $x\equiv k\pmod W$ is always one solution. (Although and $k + am + bn\pmod{W}$ will also be a solution.

So $x \equiv -1\pmod 24$ will be a solution. And as $\gcd(3,8)=1$ that solution will be unique $\mod 24$.

=====

Your error was in solving

$2+3a = x\equiv 5\pmod 6$ so $2+3a \equiv 5\pmod 6$ so $3a \equiv 3\pmod 6$ does NOT mean $a \equiv 1 \pmod 6$. Modular arithmetic does not hold for divisiong if the moduli are not relatively prime.

$3*1 \equiv 3 \pmod 6$ but $3*3=9\equiv 3 \pmod 6$ and $3*5\equiv 15 \equiv 3\pmod 6$. so $a \equiv 1,3,5 \pmod 6$.

Note if $ma \equiv mb \equiv W$ then $W|ma-mb=m(a-b)$ but that does not mean $W|a-b$. It's possible that $W$ and $m$ have a factor in common.

But if $\gcd(m,W)=1$ then $W$ and $m$ don't have a factor in common and you can divide But not if they do have a factor in common.

So instead of getting $x = 5+18k$ we should have gotten $x = 5,11,17 + 18k$. Three possibible results, not just one.

ANd this way of doing it would eventually have ended with $x \equiv 23,47,71,95,119,143 \pmod{144}$.