# Problem regarding Chinese remainder theorem and modulo arithmetic

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

-
The Chinese remainder theorem gets you out of having to do this. It guarantees you a unique solution modulo the product of the moduli and in most books is accompanied by a formula for the unique solution. This is a long winded way to get the solution. Also your set of congruences is not set out rigorously and has no unique solution (the moduli aren't coprime). –  fretty Aug 18 '12 at 11:05
I'm unsure how to apply the information in the wikipedia page to this problem –  achacttn Aug 18 '12 at 11:07
You won't be able to fully, you will not get a unique solution. The Chinese remainder theorem says you have to have coprime moduli for there to be a unique solution. –  fretty Aug 18 '12 at 11:09
There is unique solution for chinese remainder theorem. As I did in my graduate study I neve had problems. I was using extended Euclidean algorithm somewhere as long as I remember. Do you know it? –  Seyhmus Güngören Aug 18 '12 at 11:11
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. –  Gerry Myerson Aug 18 '12 at 13:13

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}$.

-

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$$

-