# How to count soldiers in the army using Chinese Remainder Theorem?

You are a chinese general and you want to count your army. Your estimate is 790,000 - 810,000. Propose the counting to determine the result unambiguously.

The soldiers can only count from to 1 to 12.

As an example remainders for the task, this information is given: every even counting of the soldiers left the remainder of $0$ and odd counting left the remainder of $1$. However, @Sandeep Silwal suggested, that this is wrong and it could be the other way around.

I tried both. In Sage software I got the following results:

CRT_list([1,1,1,0], [5,7,11,12])

4236

CRT_list([0,0,0,1], [5,7,11,12])

385


The first query is for even counting -> remainder $0$, odd counting -> remainder $1$.

The second one is the opposite.

Neither of the results is in the range $\langle 790000, 810000 \rangle$. What's more, according to the theorem, the number of the army should be $\le n_1 \cdot n_2 \cdot n_3 \cdot \dots$, where $n_i$ is the number in the modulo operation (am I right? I found this information in a few places). If the soldiers can count up to twelve, there is no possibility to find any coprime numbers that would multiply to give a result big enough for the range $\langle 790000, 810000 \rangle$.

How to approach this problem?

Just consider the remainder of the army modulo $2,3, \cdots, 12$. Then by CRT, we get an answer modulo $lcm(1,2, \cdots, 12) > 810,000-790,000$.
Edit: The added information makes no sense. If every even counting is $0$, then the number of solderer is a multiple of $6$. If every odd counting is $1$, then the number of soldiers is not a multiple of $3$ which is a contradiction.
• I updated my question with more details. I tried to apply what you proposed in Sage software, but I got an error: No solution to crt problem since gcd(60,6) does not divide 16-0 for a query of CRT_list([0,1,0,1,0,1,0,1,0,1,0], [2,3,4,5,6,7,8,9,10,11,12]). What am I doing wrong? – vtvs Apr 13 '14 at 21:32
• 1. Could you also explain why the number would be a multiple of $6$ or not a multiple of $3$? 2. The other way around I get an error: No solution to crt problem since gcd(60,6) does not divide 45-1 – vtvs Apr 14 '14 at 6:45