Solve $x\equiv 1\pmod2$, $x\equiv 2\pmod3$, $x\equiv 3\pmod4$, $x\equiv 4\pmod5$, $x\equiv 5\pmod6$ and $x\equiv 0\pmod7$

Question

$$\begin{align*} x&\equiv 1\pmod2\\ x&\equiv 2\pmod3\\ x&\equiv 3\pmod4\\ x& \equiv 4\pmod5\\ x&\equiv 5\pmod6\\ x&\equiv 0\pmod7\\ \end{align*}$$

So the solution says we can eliminate $x\equiv 5(\bmod6)$ because the first two cases cover it, but I don't really know how it does. How do we solve it in cases like this where the moduli are not mutually relatively prime.

Answer 1

Yes we can eliminate it indeed

• $x\equiv 1 \pmod 2 \implies x=2k+1$
• $x\equiv 2 \pmod 3 \implies 2k+1\equiv 2 \pmod 3\implies k\equiv 2 \pmod 3\implies k=3h+2$

that is

$$x=6k+5 \implies x\equiv 5\pmod 6$$

Note that we can also eliminate $x\equiv 1 \pmod 2$ since we have that $x\equiv 3 \pmod 4$.

Then we can use CRT to solve the system:

• $x\equiv 2 \pmod 3$
• $x\equiv 3 \pmod 4$
• $x\equiv 4 \pmod 5$
• $x\equiv 0 \pmod 7$

Answer 2

Using the reduced equations , we get

$$ \color{ red} {x = 3k+2 \quad \quad {\text(1)}}$$

Substituting it into the next gives us :

$$\color {#F0A}{3k+2\equiv 3\mod 4 \implies k \equiv 3 \mod 4 \implies k = 4j +3 \quad \quad \text { (2)}}$$

From $(1)$ and $(2)$ we get :

$$\color{ blue}{x = 12j + 11}$$

Substituting it into the next gives us : $$\color {#50F}{12j +11 \equiv 4 \mod 5 \implies j\equiv 4 \mod 5 \implies j = 5l +4 \quad \quad \text { (3)}}$$

From $(1)$ and $(3)$ we get : $$\color{ green}{x = 60l +59 \quad \quad \text{ (4)}}$$

And finally from the last equation , we get :

$$\color {orange}{60l +59 \equiv 0 \mod 7 \implies l \equiv1 \mod 7 \implies l = 7y+1 \quad \quad \text{ (5)} }$$

And we get :

$$\boxed{\color{navy}{x = 60 (7y+1) +59 \implies x = 420y + 119}}$$

Hence all values of form $420y + 119$ is the solution starting from $119,539...$

Answer 3

Because of the special case $$x\equiv -1\pmod {2,3,4,5,6}$$ we have a shortcut for handling these. $$x+1\equiv 0\pmod {2,3,4,5,6}$$ It is way easier to work with $x+1$ here. This gives us $$x+1 \equiv 0 \pmod {LCM(2,3,4,5,6)=60}$$

Now we need to incorporate $$x+1 \equiv 1 \pmod 7 $$ Which is easy, as $7$ is prime. List out the first 6 multiples of $60$.

$$\begin{align} 1 \cdot 60 \equiv 4 \pmod 7 \\\\ 2 \cdot 60 \equiv \color{red}1 \pmod 7 \\\\ 3 \cdot 60 \equiv 5 \pmod 7 \\\\ 4 \cdot 60 \equiv 2 \pmod 7 \\\\ 5 \cdot 60 \equiv 6 \pmod 7 \\\\ 6 \cdot 60 \equiv 3 \pmod 7 \\\\ \end{align}$$

So our answer is $$ x +1 \equiv 2 \cdot 60 \pmod{ 7 \cdot 60}$$ or $$ x \equiv 2 \cdot 60 -1 \pmod {7 \cdot 60}$$

Answer 4

Since $\,m_i-1\equiv \color{#c00}{-1}\pmod{\!m_i}\,$ we can apply $ $ CCRT = $\rm\color{#c00}{constant}$ case optimization of CRT

$\qquad\qquad\ \ \ \begin{align} x &\equiv \color{#c00}{-1}\!\!\!\pmod{\!m_1}\\ &\ \ \vdots\\ x &\equiv \color{#c00}{-1}\!\!\!\pmod{\!m_k}\end{align} \!\iff\ x\equiv \color{#c00}{-1}\pmod{\!{\rm lcm}\{m_1,\ldots,m_k)}$

$\ \ \ \ \ \text{or, without CRT:}\ \ \ {\rm all}\ \ m_i \mid x+1 \iff {\rm lcm}\{{\rm all}\ m_i\}\mid x+1$

The latter equivalence is by the Universal Property of LCM (= definition of LCM in general)

Therefore $\, x\equiv -1\pmod{2,3,4,5,6}\iff x\equiv\color{#0a0}{-1}\pmod{\color{#0a0}{\!60} = {\rm lcm}(2,3,4,5,6})$

So $\bmod 7\!:\,\ 0\equiv x\equiv \color{#0a0}{60k-1}\equiv 4k-1\iff 4k\equiv 1\equiv 8\iff k\equiv 2\iff \color{#90f}{k = 2\!+\!7n}$

Combining yields $\ x = 60\color{#90f}k-1 = 60(\color{#90f}{2\!+\!7n})-1 = 119 + 420n$

Remark $ $ To compute the lcm we can either use prime factorizations or else use distributivity and factor deletion: $\,[a,ab,c,\ldots] = [ab,c,\ldots]\,$ since $\,a,ab\mid m\iff ab\mid m.\,$ Applied to OP

$$[\color{#0a0}2,\color{#c00}3,\color{#0a0}4,5,\color{#c00}6] = [4,5,6] = [5,2[2,3]] = [5,12] = 60\qquad $$

since $\,[a,b] = ab\ $ for $a,b$ coprime (we also used associativity and commutativity of lcm).

Generally, for congruence systems with noncoprime moduli we can factor the moduli to split the congruences into an equivalent system with pair-coprime modulu (e.g distinct prime powers) e.g here and here or we can solve it $2$ congruences at a time while cancelling common moduli factors.

---

More generally this idea works for linearly related values & moduli: $ $ if $\,(a,b) = 1\,$ then

$$\left\{\,x\equiv d\!-\!ck\!\!\!\pmod{b\!-\!ak}\,\right\}_{k=0}^{n}\!\!\iff\! x\equiv \dfrac{ad\!-\!bc}a\!\!\!\pmod{{\rm lcm}\{b\!-\!ak\}_{k=0}^n}\quad \ $$

$ $ e.g. here $\,\ \underbrace{\left\{\,x \equiv 3-k\pmod{7-k}\,\right\}_{k=0}^2}_{\textstyle{x\equiv 3,2,1\pmod{\!7,6,5}}}\!\!\iff\! x\equiv \dfrac{1(3)-7(1)}1\equiv -4\pmod{210}$