# Consecutive Answers to Chinese Remainder Theorem

We'll start with 2 congruences only. We'll allow only numbers that when divided by 6, don't have a remainder of 3. Also, only numbers that have a remainder of 2 or 4 when divided by 5:

$\equiv${$0,1,2,4,$ or $5$}$\pmod 6$

$\equiv${$2$ or $4$}$\pmod 5$

The question is, at most how many consecutive numbers fit one or both of these congruences? We'll start testing with 3, something that doesn't work, as we don't have any chance of a string of working numbers occuring on the "wrap around" if you understand what I mean. We'll go up to 33, as that will give all possibilities mod 6 and 5. Using "y" for yes it works, or "n" for no we get:

{n,y,y,y,y,y,y,y,y,y,y,y,n,y,y,y,y,y,n,y,y,y,y,y,y,y,y,y,y,y,n}

We have 2 strings of 11 consecutive "yes" answers, thus 11 is our answer.

$\equiv${$0,1,2,4,$ or $5$}$\pmod 6$

$\equiv${$2$ or $4$}$\pmod 5$

$\equiv${$2$ or $4$}$\pmod 7$

How many consecutive "yes" answers can we have now? I'll put the answer in the comments so as to not spoil it.

What if we continue this pattern? Adding:

$\equiv${$2$ or $4$}$\pmod {next prime}$

to the list of congruences? Even using computer code, the furthest I've gotten is through 23 which has a string of 204 "yes" answers, because we're talking huge time and memory problems for testing past that point, orders of magnitude greater than the previous it seems.

1. How long would the string of "yes" answers be for primes up to 41? How did you find this answer?
2. What could we do mathematically to make these answers easier to calculate?
3. Would these answers ever approach a line, parabola, logarithmic curve, etc.?
• SPOILER ALERT! The consecutive answers for primes up to {5,7,11,13,17,19,23} are {11,29,41,65,107,149,203} at least according to my calculations. – Elem-Teach-w-Bach-n-Math-Ed Apr 13 '16 at 16:56
• Looks like OEIS sequence A144311 – Robert Israel Apr 13 '16 at 17:00
• @RobertIsrael I believe you're right! That list is up to 59 it appears. So, let's up the difficulty and find the amount for 61! Also, my 3 original questions still stand as we don't know his method. – Elem-Teach-w-Bach-n-Math-Ed Apr 13 '16 at 17:44

Let $p_n$ represent the n'th prime number.

Then we seek the longest arithmetic sequence $\{x_i\}_{i=0}^{N}$ where

• $x_i = a + id$
• $a \pmod 6 \in \{0,1,2,4,5\}$ .
• $x_i \pmod{p_{i+2}} \in \{2,4\}$ for $i \ge 1$.

So we need to solve

\begin{align} a &\equiv \{0,1,2,4,5\} \pmod 6\\ a+d &\equiv 3\pm 1 \pmod{5}\\ a+2d &\equiv 3\pm 1 \pmod{7}\\ a+3d &\equiv 3 \pm 1 \pmod{11}\\ \vdots \\ a+Nd &\equiv 3 \pm 1 \pmod{p_{N+2}} \end{align}

Which can be looked at as

\begin{align} a &\equiv \{0,1,2,4,5\} \pmod 6\\ a &\equiv 3\pm 1 - d \pmod{5}\\ a &\equiv 3\pm 1 - 2d \pmod{7}\\ a &\equiv 3 \pm 1 -3d \pmod{11}\\ \vdots \\ a &\equiv 3 \pm 1 - Nd \pmod{p_{N+2}} \end{align}

Which will always have a solution.

I'm sorry, but I don't have the software available to me to test this.

• That's ok, this is really cool. Going to have to take a look at this later, but my eventual goal is to use this in building toward a proof of the twin prime conjecture. Thanks for your help! – Elem-Teach-w-Bach-n-Math-Ed Apr 15 '16 at 18:38