Chinese Remainder Theorem with 0 mod n

Question

I'm trying to get the least x from a system of congruences by applying the Chinese Remainder Theorem. Keep running into issues.

System of congruences: $$ x \equiv 0 (_{mod} 7) \\ x \equiv 5 (_{mod} 6) \\ x \equiv 4 (_{mod} 5) \\ x \equiv 3 (_{mod} 4) \\ x \equiv 2 (_{mod} 3) \\ x \equiv 1 (_{mod} 2) $$

I made the moduli relatively prime by removing 2nd and 6th congruence:

$1(_{mod} 2)$ is just a special case of $3 (_{mod} 4)$

and the 6th congruence because

$5 (_{mod} 6)$ splits into $2 (_{mod} 3)$ and $1 (_{mod} 2)$, both of which are already represented in the system.

Product of moduli $m = 7 . 5 . 4 . 3 = 420$

Each respective $M_n$ $$ M_1 = 420/7 = 60 \\ M_2 = 420/5 = 84 \\ M_3 = 420/4 = 105 \\ M_3 = 420/3 = 140 \\ $$

Each respective modular inverse $y_n$ $$ y_1 = 0 \\ y_2 = 4 \\ y_3 = 3 \\ y_4 = 2 \\ $$

Trying to find solutions via CRT, I get

$x \equiv a_1 M_1 . y_1 + a_2 M_2 . y_2 + a_3 M_3 . y_3 + a_4 M_4 . y_4$

Plugging in the values:

$$ x \equiv 0 + 4 . 84 . 4 + 3 . 105 . 3 + 2 . 140 . 2 = 2849 \\ \equiv 329 (mod 42) $$

And the "least" value being #329$ .

However, 329 doesn't satisfy the equation $329 (_{mod} 4) \equiv 3$.

What / where am I messing up?

Answer 1

The first condition tells you that $x=7y$, so the system becomes \begin{align} 7y&\equiv 5\pmod{6} && (\textit{redundant})\\ 7y&\equiv 4\pmod{5}\\ 7y&\equiv 3\pmod{4}\\ 7y&\equiv 2\pmod{3}\\ 7y&\equiv 1\pmod{2} && (\textit{redundant}) \end{align}

There is no modular inverse of $0$. On the other hand, $7$ has a modular inverse modulo $k$, for $2\le k<7$.

I left the redundant equations just for completeness.

The three relations become then \begin{align} y&\equiv2\pmod{5}\\ y&\equiv1\pmod{3}\\ y&\equiv1\pmod{2} \end{align} that yields $y\equiv17\pmod{30}$.

Answer 2

$$ x+1 \equiv 1 (_{mod} 7) \\ x+1 \equiv 0 (_{mod} 6) \\ x+1 \equiv 0 (_{mod} 5) \\ x+1 \equiv 0 (_{mod} 4) \\ x+1 \equiv 0 (_{mod} 3) \\ x+1 \equiv 0 (_{mod} 2) $$ Hense $$ x+1 \equiv 1 (_{mod} 7) \\ x+1 \equiv 0 (_{mod} 60) $$ Then from 60, 120, 180, 240, 300 and 360 you can find $120 \equiv 1 (_{mod} 7)$ so $x=119+420k, k\in Z$ is a solution of system.

Answer 3

I know this is bad method, but the number you want must be multiple of 7, it should be odd number, last digit must end in 9(why?!!) quickly you will find that smallest such number is 119.

Answer 4

This is very similar to aid78's solution. \begin{align} x &\equiv 0 \pmod 7 \\ x &\equiv 5 \pmod 6 \\ x &\equiv 4 \pmod 5 \\ x &\equiv 3 \pmod 4 \\ x &\equiv 2 \pmod 3 \\ x &\equiv 1 \pmod 2 \end{align}

can be rewritten as

\begin{align} x &\equiv \phantom{-}0 \pmod 7 \\ x &\equiv -1 \pmod 6 \\ x &\equiv -1 \pmod 5 \\ x &\equiv -1 \pmod 4 \\ x &\equiv -1 \pmod 3 \\ x &\equiv -1 \pmod 2 \end{align}

Since $\operatorname{lcm}(2,3,4,5,6)=60$, then the last five congruences are equivalent to $x \equiv -1 \pmod{60}$ So now you have to solve

\begin{align} x &\equiv \phantom{-}0 \pmod 7 \\ x &\equiv -1 \pmod{60} \end{align}

$x \equiv -1 \pmod{60}$ is equivalent to saying $x = 60n -1$ for some integer $n$.

This is one way to finish the problem.

\begin{align} x &\equiv 0 \pmod{7} \\ 60n - 1 &\equiv 0 \pmod{7} &\text{(Note $60\equiv 4 \pmod 7$)} \\ 4n &\equiv 1 \pmod 7 \\ 8n &\equiv 2 \pmod 7 \\ n &\equiv 2 \pmod 7 \\ n &= 7m + 2 \\ x &= 60n - 1 \\ x &= 60(7m + 2) - 1 \\ x &= 420m + 119 \\ x &\equiv 119 \pmod{420} \end{align}