2
$\begingroup$

I've been trying to solve a Chinese remainder theorem problem using modulo arithmetic. The example on wikipedia is a case where there is only 3 equations (and therefore 3 unknowns). In the wikipedia example, it seems as though I am expressing the 1st unknown in terms of the 2nd unknown, and then plug this into the 1st equation to get 2 equations (old and new) for the 2nd unknown. Equate equations 2 and 3 to get 3rd unknown in terms of equation 2, then substituting this into the 2nd new equation. I'm sorry if that seems quite confusing, but that's how I feel currently (confused).

In my case, there are 6 unknowns,

(i) $x = 1$ (mod $2$) = $1 + 2.p_{1}$ (mod $2$)

(ii) $x = 2$ (mod $3$) = $2+3.p_{2}$ (mod $3$)

(iii) $x = 3$ (mod $4$) = $3 + 4.p_{3}$ (mod $4$)

(iv) $x = 4$ (mod $5$) = $4+5.p_{4}$ (mod $5$)

(v) $x = 5$ (mod $6$) = $5 + 6.p_{5}$ (mod $6$)

(vi) $x = 0$ (mod $7$) = $7.p_{6}$ (mod $7$)

I have been able to get $x = 5 + 6_p{2}$ (mod $2$), but have been unable progress further. Any pointers in the right direction would be much appreciated! THanks

  • 1
    I'd say the problem is not non-uniqueness but non-existence. If there's a solution, it's unique, modulo not the product but the least common multiple of the moduli. But if the moduli are not pairwise coprime, there may not be any solution at all. For this particular problem, there is a solution.2012-08-18

2 Answers 2

8

For your particular problem, there's an easy way: note that the first five congruences amount to saying that $x+1$ is a multiple of 2, 3, 4, 5, and 6, hence, of 60. So, $x$ is a multiple of 7, and $x+1$ is a multiple of 60. Looking at the first few multiples of 60, you find 119 is a multiple of 7, and 120 is a multiple of 60, so the answer is $x\equiv119\pmod{420}$.

2

Hint $\ $ By the constant-case optimization of CRT we have

$\rm\ x\equiv -1\,\ (mod\ 2,3,4,5,6)\iff x\equiv -1\, \ (mod\ 60)\ \ by\ \ 60 = lcm(2,3,4,5,6)$

Therefore $\rm\ mod\ 7\!:\ x = 60\,k\!-\!1\equiv 0\:\Rightarrow\: k \equiv \dfrac{1}{60}\equiv \dfrac{8}4\equiv 2\ \ $ QED

Or, mechanically, applying Easy CRT to solve $\rm\ x\equiv -1\ (mod\ 60),\, $ $\rm\:x\equiv 0\ (mod\ 7),\:$ yields

$\rm mod\ 7\!\cdot\!60\!:\ x\equiv -1 + 60\, \left(\frac{1}{60}\ mod\ 7\right)\equiv 119\ \ \ by\ \ \ mod\ 7\!:\ \frac{1}{60}\equiv \frac{8}{4}\equiv 2$