# Find x between an interval of 1000 and 2000 using Chinese Remainder Theorem

General Tso was leading a phalanx of chickens and knew there were between 1000 and 2000 in all. He desired a more accurate estimate, and so had a lieutenant line them up in columns of 11, 13, and 17 and use the Chinese Remainder Theorem to obtain a good tally for the general. The general was very happy with the resulting numbers until he found out that before the first two assemblies, Chicken Little was still sleeping. If Chicken Little made the third assembly (and was the only chicken still in the coop), how wrong were General Tso’s “more accurate” numbers?

The wording of the question is a little difficult, but the way I am interpreting this question is that the chickens are lined up in 3 columns/assemblies. The first column/assembly has 11 chickens, the second column/assembly has 13 chickens, and the third column/assembly has 17 chickens. One paricular chicken does not show up in the lineup for 11 or 13 but showed up for the assembly of 17.

So this is what I think the system of congruences will look like:

$x$ $\equiv$ 1 mod 11
$x$ $\equiv$ 1 mod 13
$x$ $\equiv$ 0 mod 17

Then, we solve for the system of congruences.

$x = 17a + 0$
$17a + 0 \equiv 1 \ (mod \ 13)$
$4a \equiv 1 \ (mod \ 13)$
$40 a \equiv 10 \ (mod \ 13)$
$a \equiv 13b + 10$

$x = 17(13b + 10) = 221b + 10$
$x \equiv 1 \ (mod \ 11)$

$221b = 10 = 1 \ (mod \ 11)$
$b + 10 = 1 \ (mod \ 11)$
$b = -9 \ (mod \ 11)$
$b = 2 \ (mod \ 11)$
$b = 11c + 2$

$221(11c + 2) + 10 = 2431c + 452$.

Did I do something wrong in my calculations, because my remainder is not between 1000 and 2000. Or is my entire setup incorrect?

• It must've been your calculations wolframalpha.com/input/… – Shuri2060 Jul 22 '17 at 16:19
• Ah I see - '$x = 17(13b + 10) = 221b + 10$'. You forgot to multiply $10$ by $17$ on that line. – Shuri2060 Jul 22 '17 at 16:21
• Oh awesome. Thanks Shuri! – Keith Axelrod Jul 22 '17 at 16:33

I think you're misunderstanding the problem.

Tso had his lieutenant line the chickens up in rows of 11, 13, and 17 chickens, and in each case note down how many chickens there were in the last, partial, row. This gave Tso three numbers $a$, $b$, $c$, and Tso then solved the congruence $$x\equiv a \pmod{11} \qquad\qquad x\equiv b \pmod{13} \qquad\qquad x\equiv c \pmod{17}$$

Note that we're not told what $a$, $b$ and $c$ was, so we can't know what Tso's initial result was.

What we are told is the $a$ and $b$, but not $c$, were each $1$ too small. We're then asked to figure out how wrong that initial result was.

You're solving the right congruence to find that difference. As noted in comments you must have made an arithmetic error somewhere, because the solution is $x\equiv 1717\pmod{2431}$.

So Tso's answer was $1717$ chickens too low -- but that can't have been true, because he knew there were between 1000 and 2000 chickens in the troop and he was happy with his answer.

Instead the initial answer must have been $2431-1717=714$ chickens too high. That way it can have been possible both for the truth and for the false initial answer to be between $1000$ and $2000$.

• Can you explain what you mean by too high and too low? Was the first answer that was reported to Genereal Tso (such that he was content with the answer) 714? What do you mean by it was too high? I'm just confused with what you mean by those terms. – Keith Axelrod Jul 22 '17 at 17:33
• @JohnLocke: We don't know what the first answer Tso computed was, nor what the true number of chickens was. But we can compute that it was 1717 (modulo 2431) lower than the actual number of chickens, because the $a$ he used was one less than $N\bmod 11$ and the $b$ he used was one less than $N\bmod 13$. – Henning Makholm Jul 22 '17 at 17:52
• That makes sense. General Tso’s “more accurate” numbers were 1717 (modulo 2431) lower than the actual number of chickens. – Keith Axelrod Jul 22 '17 at 17:55
• @JohnLocke: But since that is not possible with both the true and the false answer being between 1000 and 2000, what happened must have been that "1717 too low" rolled over into "714 too high". – Henning Makholm Jul 22 '17 at 18:01