# How to solve for multiple congruence's what aren't relatively prime.

How could I go about solving $$x\equiv 1\mod 2$$ $$x\equiv 1\mod 3$$ $$x\equiv 1\mod 4$$ $$x\equiv 1\mod 5$$ $$x\equiv 1\mod 6$$ $$x\equiv 0\mod 7$$

I know that if I want to use the Chinese Remainder Theorem then I have to find a way for all the mod's to be relatively prime to each other but I am unsure which ones I can get rid of. Any suggestions?

-
If $x \equiv 1 \mod {12}$ then $x \equiv 1 \mod {2,3,4,6}$. So $x \equiv 1 \mod {60}$ and $x \equiv 0 \mod {7}$ does the trick. –  k.stm Feb 16 '13 at 20:43

$x\equiv1\pmod4$ implies $x\equiv1\pmod2$, while $x\equiv1\pmod6$ is equivalent to the two congruences $x\equiv1\pmod2$ and $x\equiv1\pmod3$. So you should be okay keeping only the congruences modulo $3$, $4$, $5$, and $7$.

-

In this case, the system is equivalent to the following: $$\begin{array}{rcl} x & \equiv & 1 \qquad \mod \mathrm{lcm}(2,3,4,5,6) \\ x & \equiv & 0 \qquad \mod 7 \end{array}$$ This way the Chinese remainder theorem is applicable.

-

Hint $\rm\ 2,3,4,5,6\mid x-1\iff 60 = lcm(2,3,4,5,6)\mid x-1\$ so, by Easy CRT, we have

$$\begin{array}{ll}\rm x\equiv 0\ \ (mod\ 7)\\ \rm x\equiv 1\ \ (mod\ 60)\end{array}\rm \!\iff x\equiv 1 + 60 \left[\frac{-1}{60}\ mod\ 7\right]\equiv -119,\ \ by\ \ mod\ 7\!:\, \frac{-1}{60}\equiv \frac{6}{-3}\equiv -2$$

Theorem (Easy CRT) $\rm\ \$ If $\rm\ m,n\:$ are coprime integers then $\rm\ n^{-1}\$ exists $\rm\ (mod\ m)\ \$ and

$\rm\displaystyle\quad \begin{eqnarray}\rm x&\equiv&\rm\ a\ \ (mod\ m) \\ \rm x&\equiv&\rm\ b\ \ (mod\ n)\end{eqnarray} \iff x\ \equiv\ b + n\ \bigg[\frac{a\!-\!b}{n}\ mod\ m\:\bigg]\ \ (mod\ mn)$

Proof $\rm\ (\Leftarrow)\ \ \ mod\ n\!:\,\ x\equiv b + n\ [\cdots]\equiv b\:,\$ and $\rm\ mod\ m\!:\,\ x\equiv b + (a-b)\ n/n\: \equiv\: a\:.$

$\rm\ (\Rightarrow)\ \$ The solution is unique $\rm\ (mod\ mn)\$ since if $\rm\ x',x\$ are solutions then $\rm\ x'\equiv x\$ mod $\rm\:m,n\:$ therefore $\rm\ m,n\ |\ x'-x\ \Rightarrow\ mn\ |\ x'-x\ \$ since $\rm\ \:m,n\:$ coprime $\rm\:\Rightarrow\ lcm(m,n) = mn\:.\ \$ QED

Remark $\$ The optimization used above to combine the moduli where $\rm\,x\,$ takes the same (constant) value $\rm\:x\equiv 1,\:$ is know as the constant case of CRT = Chinese Remainder theorem. It proves quite handy in practice. See here for more on this.

-
As a general comment, @user62015, a system of congruences with moduli that are not relatively prime can still have solutions. Take $$\begin{cases} x \equiv a \pmod{m}\\ x \equiv b \pmod{n} \end{cases}$$ with $m,n$ not both zero. If this has a solution $x$, then there are $s, t$ such that $a + ms = x = b + n t$, or $$b-a = ms - nt,$$ so for a solution to exist we need $(m, n) \mid b - a$. Conversely, if $(m, n) \mid b - a$, use Euclid to find $u, v$ such that $$(m,n) = m u - n v,$$ and multiply by the integer $(b-a)/(m,n)$ to get $$b-a = m (u (b-a)/(m,n)) - n (v (b-a)/(m,n)),$$ so that $$x = a + m (u (b-a)/(m,n)) = b + n (v (b-a)/(m,n))$$ is indeed a solution.