# Chinese Remainder Theorem Confusion

I need to use the Chinese Remainder Theorem to find six consecutive integers, each divisible by a prime squared greater 5.

So I chose to solve these $$x\equiv 0 \pmod {49}$$ $$x+1\equiv 0 \pmod {121}$$ $$x+2\equiv 0 \pmod {169}$$ $$x+3\equiv 0 \pmod {289}$$ $$x+4\equiv 0 \pmod {361}$$ $$x+5\equiv 0 \pmod {529}$$

I wrote a program to try and solve it but wasn't able to find a solution, could someone help get me started on how to use the CRT to solve this problem?

I'm not quite sure how to apply it to even tackle this problem..

• That would only be five numbers. Did you want to require that $x\equiv 0 \pmod {49}$? That's what you had the first time you posted this question, no?
– lulu
Mar 9 '17 at 19:28
• Hint: do it step by step. Assuming you wanted to require that $x$ was divisible by $49$, write $x=49y$. Then we need to solve $49y\equiv -1\pmod {11^2}$. That's easily done via the euclidean algorithm, so we'll end up with some class $\pmod {(7\times 11)^2}$ which satisfies the first two congruences. Now do the third, and so on. The numbers will get very large, so you'll want to do it with a machine.
– lulu
Mar 9 '17 at 19:31
• See this answer for an example of the pairwise step-by-step CRT solution method mentioned by @lulu Mar 9 '17 at 19:40
• Maybe your program ran into some integer size limitations. I put the query ChineseRemainder[{0, 1, 2, 3, 4, 5}, {49, 121, 169, 289, 361, 529}] to Wolfram Alpha and the answer was almost $32$ trillion. Mar 9 '17 at 22:27
• The details of the general proof of the CRT can be used to give an algorithm fof solutions. Mar 10 '17 at 0:58

Let's solve just one pair of those congruences:
\begin{align} x+4&\equiv 0 \bmod {361} &\implies x&\equiv -4 \bmod {361}\\ x+5&\equiv 0 \bmod {529} &\implies x&\equiv -5 \bmod {529}\\ \end{align}

We can jump into the extended Euclidean algorithm to find a combination of $361$ and $529$ that solves to their GCD of $1$:

$\begin{array}{|c|c|} \hline \quad n \quad & \quad s \quad & \quad t \quad & \quad q \quad \\\hline 529 & 1 & 0 & \\ 361 & 0 & 1 & 1 \\ 168 & 1 & -1 & 2 \\ 25 & -2 & 3 & 6 \\ 18 & 13 & -19 & 1 \\ 7 & -15 & 22 & 2 \\ 4 & 43 & -63 & 1 \\ 3 & -58 & 85 & 1 \\ 1 & 101 & -148 & \\ \hline \end{array}$

where each line solves $n=529s+361t$ and $q$ is a multiplier used to get to the reduced $n$ on the following line. From the last line we see Bézout's identity of $101\cdot 529 -148\cdot 361 =1$, giving $-148\cdot 361 \equiv 1 \bmod 529$.

Then $x=361k-4 \implies 361k+1\equiv 0\bmod 529 \implies k-148 \equiv 0\bmod 529$ using the result from the Bézout identity, so $k=148$ is a result consistent with the $\bmod 529$ equivalence , and we get

$$x \equiv 361\cdot 148 -4 \equiv 53424 \bmod 190969 (=361\cdot529)$$

Then this result can be combined with one of the other equivalences, and so on to a (very large) solution.