Problem 1429

1. **Case 1: $a$ and $d$ are not coprime**

- If $a$ and $d$ are not coprime, then $\gcd(a, d) = g > 1$.
- Every term in the arithmetic progression $\{a + nd\}_{n=1}^\infty$ can be written as $a + nd$.
- Since $g$ divides both $a$ and $d$, it follows that $g$ divides $a + nd$ for all $n$.
- Therefore, each term $a + nd$ is divisible by $g$ and is greater than $g$ (since $a$ and $d$ are positive integers and $n \geq 1$).
- Hence, every term $a + nd$ is not prime because it has a divisor $g > 1$.
- Thus, $K = 1$ works in this case, as every single element in the progression is not prime.

2. **Case 2: $a$ and $d$ are coprime**

- If $a$ and $d$ are coprime, then $\gcd(a, d) = 1$.
- Consider any $d$ consecutive terms in the arithmetic progression: $a + nd, a + (n+1)d, \ldots, a + (n+d-1)d$.
- These terms can be written as $a + nd, a + (n+1)d, \ldots, a + (n+d-1)d$.
- Since $d$ is coprime with $a$, the numbers $a, a+d, a+2d, \ldots, a+(d-1)d$ are all distinct modulo $d$.
- This means that among any $d$ consecutive terms, there is exactly one term that is congruent to $0 \pmod{d}$.
- Specifically, there exists an integer $k$ such that $a + kd \equiv 0 \pmod{d}$, which implies $a + kd = md$ for some integer $m$.
- Since $a$ and $d$ are coprime, $m$ must be greater than $1$ (as $a + kd$ is greater than $d$).
- Therefore, $a + kd$ is not prime because it is divisible by $d$ and greater than $d$.
- Thus, $K = d$ works in this case, as among any $d$ consecutive terms, there is at least one term that is not prime.

Conclusion:
In both cases, we have shown that there exists a constant $K$ such that every set of $K$ consecutive elements of the arithmetic progression $\{a + nd\}_{n=1}^\infty$ contains at least one number which is not prime. Specifically, $K = 1$ if $a$ and $d$ are not coprime, and $K = d$ if $a$ and $d$ are coprime.

$\blacksquare$