Prime Factors of the Composit Terms of Arithmetic Progressions

Question

Dirichlet's theorem states that for any two positive coprime integers a and d, there are infinitely many primes or the form a + nd, where n is a non-negative integer. My question is concerning the composit terms of such arithmetic progressions, and particularly, concerning the prime factors thereof. Here are some examples and what I have found so far:

If the initial term is 1 and the common difference is 2, every prime other than 2 will appear as a factor of a composite term. I know that once a prime appears as a factor of a term, then the prime will continue to be a factor forevermore. My question is specifically concerning the initial appearance of the prime.

In any arithmetic progression of the form a + nd where a and d are any two positive coprime integers, and n is a non-negative integer, will every prime other than those which are factors of the common difference appear as a factor of a composite term?

If the initial term is 1 or 3 and the common difference is 2, I have found the answer to be yes. Likewise, if the initial term is 5 or 7, and the common difference is 6, the answer is yes. These I have checked by hand and have found proofs for.

Here is one specific example of what I am asking about:

If I set up the arithmetic progression with 2309 as the first term and use 2310 as the common difference, will I find a multiple of 13 within the first 13 terms? I know that the answer to this is yes. My question is, what is the proof for all such arithmetic progressions and the prime factors of the composit terms?

Answer 1

The phenomenon you observed with $a=2309$, $d=2310$, and $p=13$ is not at all an accident. It occurs quite generally.

Suppose that the prime $p$ does not divide $d$. Then for $n=0,1,\dots,p-1$ the numbers $a+nd$ are pairwise incongruent modulo $p$. Thus their remainders on division by $p$ travel, in some order, through the numbers $0,1,\dots,p-1$. In particular there is an $n$, with $0\le n\le p-1$, such that $a+nd$ is divisible by $p$.

Remarks: $1$. The same proof works if instead of a prime $p$, we use a positive integer $m$ which is relatively prime to $d$.

$2.$ To show that if $0\le i\lt j\le p-1$, the numbers $a+id$ and $a+jd$ are incongruent modulo $p$, suppose to the contrary that $p$ divides their difference. Then $p$ divides $(j-i)d$. But since $p$ and $d$ are relatively prime, it follows that $p$ divides $j-i$. This is impossible, since $0\lt j-i\lt p$.