1
$\begingroup$

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..

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – lulu
    Mar 9 '17 at 19:28
  • $\begingroup$ 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. $\endgroup$
    – lulu
    Mar 9 '17 at 19:31
  • $\begingroup$ See this answer for an example of the pairwise step-by-step CRT solution method mentioned by @lulu $\endgroup$ Mar 9 '17 at 19:40
  • $\begingroup$ 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. $\endgroup$
    – Bob Happ
    Mar 9 '17 at 22:27
  • $\begingroup$ The details of the general proof of the CRT can be used to give an algorithm fof solutions. $\endgroup$ Mar 10 '17 at 0:58
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.