How many positive integers less than or equal to $6\cdot7\cdot8\cdot9$ solve the system of congruences?

Question

How many positive integers less than or equal to $6\cdot7\cdot8\cdot9$ solve the system of congruences \begin{align*} m &\equiv 5 \pmod{6}, \\ m &\equiv 4 \pmod{7}, \\ m &\equiv 3 \pmod{8}, \\ m &\equiv 3 \pmod{9}? \end{align*}

So I just solved this step-by-step, I guess — from the first two congruences, we have $6a+5 = 7b + 4$, and dividing by $6$ on both sides (for mod $6$), we have $b + 4\equiv 5 \mod 6$, so $b\equiv 1 \pmod 6$, which gets us $m\equiv 7(1)+4 \mod (6\cdot 7)\equiv 11 \mod 42$. Then continuing in the same vein I worked on $m\equiv 11 \mod 42$ and $m\equiv 3 \mod 8$: $8c+3 = 42d+11$. Using mod $8$, I have $2d + 3\equiv 3 \mod 8$, which means $d=0$. So $m\equiv 11 \mod 168$ and also $3\mod 9$. Using equations, $168p+11 = 9q+3$. Using mod $9$, this is equal to $6p+2\equiv 3\mod 9$, so $6p\equiv 1 \mod 9$. However, at this point I don't think $p$ has any solutions...

Answer 1

You are correct in your reasoning - so there are no solutions. However, there is a simpler way to realize this:

You know that, if $\gcd(a,b)=1$, the congruences $x\equiv c\bmod a$, $x\equiv d\bmod b$ always have simultaneous solutions. So, you want to look for places where these are not satisfied. This brings you to the congruences with moduli $(6,8)$ and $(6,9)$. Specifically, with the $(6,9)$ case we have

$$m\equiv 5\bmod 6 \implies m\equiv 2\bmod 3$$

as well as

$$m\equiv 3\bmod 9 \implies m\equiv 0\bmod 3.$$

These cannot both be true, and thus there are no solutions.

Answer 2

The system

• $m \equiv 5 \pmod{2 \cdot 3}$
• $m \equiv 4 \pmod{7}$
• $m \equiv 3 \pmod{2^3}$
• $m \equiv 3 \pmod{3^2}$

implies that

• $m \equiv 1 \pmod{2}$
• $\color{red}{m \equiv 2 \pmod{3}}$
• $m \equiv 4 \pmod{7}$
• $m \equiv 1 \pmod{2}$
• $\color{red}{m \equiv 0 \pmod{3}}$

Since we obtain a contradiction for the second and the last equation, the system has not solutions.

Answer 3

$7,8,9$ are mutually relatively prime so by the chinese remainder theorem there will be a unique solution modulo $7*8*9$.

$6$ is neither relatively prime to $8$ nor to $9$ so either this will be incompatible or redundant.

If $a \equiv b \mod mn$ then $a \equiv b \mod m$ and $a \equiv b \mod n$. (Easily varified $a = b + kmn = b + (km)*n = b +(kn)*m$.

$m \equiv 5 \mod 6$ means $m \equiv 5\equiv 1 \mod 2$ and $m\equiv 5\equiv 2 \mod 3$. This are compatible with $m \equiv 3 \mod 8$ so $m \equiv 1 \mod 2$ but not with $m \equiv 3 \mod 9$ would imply that $m \equiv 3 \equiv 0 \not \equiv 2 \mod 3$.

So there are no solutions.

But if we left out the equation $m \equiv 3\mod 9$ we'd have a unique solution to mod $6*7*8$ or if we left ot $m \equiv 5 \mod 6$ we'd have a unique solution to $7*8*9$.

Or if we replaced $m \equiv 2, 5, 8 \mod 9$ (or $m \equiv 3 \mod 6$) we'd have a unique solution modulo $7*8*9$ but $6$ solutions modulo $6*7*8*9$.