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$$
Best Answer
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}$