# Length of Arithmetic Progressions Under Congruence Conditions

Let $S$ be a finite set of integer, $n$ be a positive integer, $p_i$ denote the $i^{th}$ prime. Consider the set

$$\mathcal{P}_{S,n}:=\{x\mid0\leq x<\prod_{i=1}^np_i \text{ and }(\forall i\leq n, i>0)(\forall s\in S)\,x\not\equiv s\text{ (mod }p_i)\}$$

In other words, $\mathcal{P}$ is the set of naturals less than $\prod_{i=1}^np_i$ that, when taken mod $p_i$ for any $1\leq i\leq n$, are not congruent to any element of $S$. Using the Chinese Remainder Theorem, the exact number of elements in $S$ can be obtained as

$$|S|=\prod_{i=1}^n \big{(}p_i-|S\text{ (mod }p_i)|\big{)}$$

What is the length (or an estimate of the length) of the longest arithmetic progression in $\mathcal{P}_{S,n}$? For a fixed $S$, can the size of the longest arithmetic progression be estimated as $n$ tends to infinity?

## 1 Answer

If $p_i$ is not a factor of the common difference, then one of the first $p_i$ numbers in the arithmetic progression is congruent to $s\pmod{p_i}$, for any $s\in S$.
If all $p_i$ are factors of the common difference, then the common difference is a multiple of $\prod p_i$, and only one term fits inside $P_{S,n}$.
So the longest arithmetic progression possible has length $p_n-1$, and that is only possible when all the $s\in S$ are equivalent $\mod p_n$