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

  • 0
    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).2012-08-18
  • 0
    I'm unsure how to apply the information in the wikipedia page to this problem2012-08-18
  • 0
    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.2012-08-18
  • 0
    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?2012-08-18
  • 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