Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

4 Answers

$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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.