# Find the smallest natural number using Chinese Remainder Theorem

Question is find the smallest natural number $$x$$ such that,

\begin{align} x &\equiv 1 \pmod 2 \\ x &\equiv 2 \pmod 3 \\ x &\equiv 3 \pmod 4\\ x &\equiv 4 \pmod 5\\ x &\equiv 5 \pmod 6\\ x &\equiv 6 \pmod 7\\ x &\equiv 7 \pmod 8\\ x &\equiv 8 \pmod 9\\ x &\equiv 9 \pmod {10}\\ x &\equiv 10 \pmod {11}\\ x &\equiv 11 \pmod {12}\\ x &\equiv 0 \pmod {13}\\ \end{align}

However when I use the proof of Chinese remainder theorem, I cannot even get over the first step where I must find inverse modulo: $$b_1 \frac{6227020800}{2}\equiv 1 \pmod 2$$ which I presume is $$0\cdot \frac{6227020800}{2} + 2\cdot 1 \equiv 1$$ hence 0?

I am somewhat confused. A friend did it using another method, but I would like to learn how to use the Chinese remainder theorem.

$$x\equiv a_1 b_1 \frac{M}{m_1} + \cdots + a_k b_k \frac{M}{m_k} \pmod M$$

• Hint: $\ x\equiv -1\,$ mod $\,2,3,\ldots, 12\$ iff their lcm divides $\,x+1\ \$ – Bill Dubuque Jan 26 '19 at 18:38
• "However when I use the proof of theorem, I cannot even get over the first step where I must find inverse modulo: $\frac M{m_1}=\frac{6227020800}2$" Could you write out what proof and why exactly you are finding it? It's not clear what you are trying to do. – fleablood Jan 26 '19 at 18:38
• – C. Ekinci Jan 26 '19 at 18:39
• I know what the CRT theorem is. I'm asking YOU to explain why you are doing that as the first step and why. – fleablood Jan 26 '19 at 18:40
• $-1\pmod 8*9*5*7*11$ and $0 \pmod 13$ so solve that. If you get a negative number just add $8*9*5*7*11*13$. – fleablood Jan 26 '19 at 18:56

The Chinese remainder theorem is about relatively prime modulos. Having all the modulos from $$2$$ to $$13$$ is redundant.

$$x\equiv 1 \mod 2; x \equiv 3\mod 4; x\equiv 7\mod 8$$ are redundant and can be replaced with just $$x \equiv 7 \pmod 8$$.

Assuming the question is legitimate, we need not consider any $$x \equiv j \pmod {2^km}$$ and have to consider only $$x\equiv l\pmod m$$

i.e., this question can be reduced to.

$$x\equiv 7\pmod 8$$

$$x \equiv 8\pmod 9$$

$$x \equiv 4 \pmod 5$$

$$x \equiv 6\pmod 7$$

$$x \equiv 10 \pmod {11}$$

$$x \equiv 0 \pmod {13}$$.

All the rest are redundant, as the solution to the above is unique.

Note the solution to all but $$x \equiv 0 \pmod {13}$$ is $$x \equiv -1 \pmod n$$ for $$n = 8,9,5,7,11$$ so

$$x\equiv -1 \pmod{8*9*5*7*11=27720}$$ and $$x \equiv 0 \pmod {13}$$.

So you need to solve. $$x = 27720k -1 = 13m$$

$$27720 \equiv 4 \pmod {13}$$

So $$x \equiv 27720k - 1\equiv 0 \pmod {13}$$

$$\equiv 4k -1 \equiv 0 \pmod {13}$$

So $$4k \equiv 1 \pmod {13}$$ so we just have to find the inverse of $$4 \mod {13}$$

And $$4 \times 10 = 40 \equiv 1 \pmod{13}$$ and so $$k = 10$$

and $$x \equiv 277199 \pmod {27720*13}$$

• God, I feel like an absolute moron... thanks. – C. Ekinci Jan 26 '19 at 18:58

$$2,3,\ldots,12\mid x+1\iff 27720\mid x+1$$ since $$27720$$ is the lcm of the divisors.

So $$\, 13n = x = 27720\,\color{#c00} k - 1\$$ so $$\bmod 13\!:\,\ \color{#c00} k\equiv \dfrac{1}{27720}\equiv\dfrac{ -12}4\equiv -3\equiv \color{#c00}{10}$$

hence $$\, x = 22720(\color{#c00}{10}+13m)-1 = 277199 + 13\cdot 27720\,m$$