Until Covid, I was meeting up with a friend once a week for some recreational abstract algebra. This was an early problem in the textbook we used:
Prove that for any positive integer m there exists a sequence of m consecutive positive integers that are all composite.
My gut instinct was to try to prove this by contradiction, using the pigeonhole principle somehow. But before I could work that out, I saw that it’s easily provable by construction.
Proof by construction
Let n = m!. Then, for all integers k such that 0 < k \le m, we know k \mid n. So we can say that n + k = k (\frac{n}{k} + 1). Since k \mid n, the quantity \frac{n}{k} + 1 is an integer. Therefore n+k has k as a factor, making it composite. So, the sequence
n+1, n+2, \dots, n+m
are all composite. \blacksquare
Pretty trivial. But I still wanted to know if my gut instinct was right; could this be proved by contradiction?
It turns out that it can, but it’s much more complicated, and took me a couple of days to figure out.
Proof by contradiction
Assume that every set of m consecutive positive integers contains at least one prime number.
The positive integers can be expressed as a union of sets
\Z^+ = A_0 \cup A_1 \cup A_2 \cup \dots
where
A_n = \{nm+1, nm+2, \dots, nm+m\}Since \vert A_n \vert = m, our assumption requires that every set A_n contains at least one prime number.
Let a_i(n) be the i^{th} element of A_n, where 1\le i \le m. Call i the “position” of a_i(n) within A_n. Since there is only one even prime number, the maximum number of positions in A_n at which there can be a prime is \lceil \frac{m}{2}\rceil.
Lemma: If A_j has a prime p in position i then A_{j+q} cannot have a prime in position i when q is a multiple of p.
Proof: Let A_j and A_{j+q} be sets with prime numbers in position i, and say that a_i(j) = p and a_i(j+q) = p^*. Then
p^* = p + (m-i) +m(q-1)+i
In the sum on the right hand side of this equation, the term (m-i) represents all the positions in A_j after p, the term m(q-1) is all the positions in all of the sets between A_j and A_{j+q}, and the term i is how many positions in A_{j+q} we must move through to reach p^*.
This equation simplifies to
p^* = p +qm
If q is a multiple of p, then for some k \in \Z^+
p^* =p+kpm=p(1+km)
which contradicts that p^* is prime.
Consider a set A_j such that a_i(j) is prime. Let a_i(j) = p_1.
By the above lemma, we know that a_i(j+p_1) is composite. By our assumption, the set A_{j+p_1} must contain a prime number. There remain \lceil \frac{m}{2}\rceil - 1 positions in A_{j+p_1} at which there can be a prime. Let a_{i^*}(j+p_1) be a prime, and call it p_2.
Now consider the set A_{j+(p_1p_2)}. This set has two positions, i and i^*, at which there can’t be a prime, leaving only \lceil \frac{m}{2}\rceil - 2 positions at which there can be a prime. By our assumption, one of these positions must have a prime, which we will call p_3.
Continue this pattern until we find the set A_{k+(p_1 p_2 \dots p_{\lceil \frac{m}{2}\rceil})}. This set contains zero positions where there can be a prime. But this contradicts our assumption, which requires every A_n to contain a prime number. Thus our assumption is false, and there exists an A_n (a set of m consecutive positive integers) with only composite elements. \blacksquare
If there’s a simpler way to prove this by contradiction, I’d like to know about it.
