## Task 6A - 241246A

Investigate whether there are 40 consecutive natural numbers that are all less than $10^{9}$ and are not prime numbers.
Consider $n=2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19$. For every natural number $a>0$ and all $k \in\{0, \pm 2, \pm 3, \ldots, \pm 22\}$, $a \cdot n \pm k$ is not a prime number: Each of the first prime numbers up to 19 is a prime factor in $a \cdot n$, so each $k$ in the given set has a prime factor that is contained in $a \cdot n$, allowing us to factor it out. Furthermore, $a \cdot n-22>0$ always holds.

Now, we only need to find an $a$ such that $a \cdot n \pm 1$ are not prime numbers. Using modular arithmetic and appropriate grouping of the factors in $n$, we find that $n \equiv -8 \bmod 23$ and $n \equiv 2 \bmod 29$.

If we can find an $a$ such that $a \equiv 3 \bmod 23$ and $a \equiv 15 \bmod 29$, then $a \cdot n \equiv -1 \bmod 23$ and $a \cdot n \equiv 1 \bmod 29$, and we would be done. Using the Chinese Remainder Theorem, we find that the smallest natural $a$ with this property is $a=624$. Unfortunately, this results in $a \cdot n > 10^9$, so we need to try something else.

An $a$ with $a \equiv -3 \bmod 23$ and $a \equiv -15 \bmod 29$ yields $a \cdot n \equiv 1 \bmod 23$ and $a \cdot n \equiv -1 \bmod 29$. The smallest natural $a$ with this property is $a=43$, and indeed, we can estimate or calculate that $a \cdot n + 22 < 10^9$. (Note: $a=43$ also results from the failed attempt via $23 \cdot 29 - 624 = 43$.)

Therefore, there are 45 (and in particular 40) consecutive numbers less than $10^9$ that are not prime, namely $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 43 + k$ with $k \in \{0, \pm 1, \ldots, \pm 22\}$.