Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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$.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.