Show that among any consecutive $16$ natural numbers one is coprime to all others

Show that among any consecutive $16$ natural numbers one is coprime to all others.
Is it useful to use the division algorithm on $16$?
$16k,16k+1,16k+2,...16k+15$

Solution 1:

First off, you should observe that since any two numbers in the sequence differ by at most 15, any common factor is at most 15. Therefore, any number not coprime to the others is divisible by one of the primes 2,3,5,7,11,13.

Now if a number $x$ in the sequence is divisible by $p = 2, 3, $ or $7$, then it cannot be coprime to the others, since in that case either $x-p$ or $x+p$ must also lie in the sequence. (If $x-p$ is not in the sequence, then the first element is at least $x-p+1$, so the last element is at least $x-p+16 > x+p$.)

Therefore, $x$ is a desired coprime element if and only if the following conditions are all satisfied:

• $x$ is not divisible by 2, 3, 5, or 7.
• If $x$ is divisible by 11, then $x-11$ and $x+11$ are not in the sequence.
• If $x$ is by 13, then $x-13$ and $x+13$ are not in the sequence.

We consider the congruence classes modulo 30. Of these, the set $S = \{1, 7, 11, 13, 17, 19, 23, 29\}$ represent elements divisible by neither 2 nor 3 nor 5. Now we must consider each possible set of sixteen consecutive residues and argue that there are enough elements of $S$ that at least one of them satisfies our conditions for being coprime.

In particular we will note that it is sufficient (although not quite necessary) to find an element in the sequence from $S$ that is coprime to 7, 11, 13.

Note that in such a sequence there can be only one element from a residue class in $S$ divisible by 11, and likewise only one element from a residue class in $S$ divisible by 13. There might be two divisible by 7, since that only requires a difference of 14, which happens in three cases:

1. When the sequence has elements of form $30k+17$ and $30(k+1) +1$
2. When the sequence has elements of form $30k+23$ and $30(k+1) +7$
3. When the sequence has elements of form $30k+29$ and $30(k+1) +13$

We consider which residue appears first in the sequence. (I would be happy to avoid covering cases explicitly like this but it seems necessary to the argument, and the last two cases are finicky.)

• If the first element from $S$ is of form $30k+1$, then the first element overall is $30k$ or greater. This means that $30k+1, 30k+7, 30k+11, 30k+13$ are all in the sequence. At most one of these four elements is divisible by 11, at most one is divisible by 13, and by above at most one is divisible by 7. Thus, one of them is coprime to all elements in the sequence, as desired.
• If the first element from $S$ is of form $30k+7$, then the first element is at least $30k+2$ and thus the sequence contains $30k+7, 30k+11, 30k+13, 30k+17$. Again one of these is again divisible by neither 7, 11, nor 13.
• If the first element from $S$ is of form $30k+11$ or $30k+13$, then the first element is at least $30k+8$ and thus the sequence contains $30k+13, 30k+17, 30k+19,30k+23$. Again one of these is again divisible by neither 7, 11, nor 13.
• If the first element from $S$ is of form $30k+17$, then by the same reasoning the sequence contains the elements $30k+17, 30k+19,30k+23, 30k+29$, of which at least one is coprime as desired.
• If the first element from $S$ is of form $30k+19$, then the sequence contains the elements $30k+19,30k+23, 30k+29, 30(k+1) + 1$ and the argument is the same.
• If the first element from $S$ is of form $30k+23$, then the sequence contains the elements $30k+23, 30k+29, 30(k+1) + 1$. At this point we need to be more careful, since one each of these three could very well be divisible by 7,11,13. However in this case note that $30k+29 \pm 11$ and $30k+29 \pm 13$ all lie outside the bounds of the sequence (the first element lies in the range $[30k+20, 30k+23]$ and the last element lies in the range $[30(k+1)+5,30(k+1)+8]$). Thus for this element to be not coprime it must be the one divisible by 7. If we try to force $x = 30(k+1) + 1$, to not be coprime, we examine the elements $x \pm 11, x \pm 13$. Of these, only $x-11 = 30k+20$ is possibly in the sequence, which would therefore be the range $[30k+20,30(k+1)+5]$. In that case, we see that $(30k+23)$ might be divisible by 13, but then $(30k+23)\pm 13$ lie outside the sequence, so that $30k+23$ must be coprime after all.
• If the first element from $S$ is of form $30k+29$, then the sequence contains the elements $30k+29, 30(k+1) + 1, 30(k+1)+7$. If $30(k+1)+11$ lies in the sequence we have four elements from $S$ with at least one of them coprime to 7,11,13, as desired. Thus, we restrict ourselves to when the first element is either $30k+24$ or $30k+25$ and the last element is either $30(k+1)+9$ or $30(k+1)+10$. Again, we see that the three elements $30k+29, 30(k+1) + 1, 30(k+1)+7$ might each be divisible by one of 7,11,13. Since $30(k+1) + 1 \pm 11$ and $30(k+1) + 1 \pm 13$ lie outside the sequence's range, $30(k+1) + 1$ is coprime unless it is the one divisible by 7. Then if we examine $x = 30k+29$, of the values $x\pm 11, x \pm 13$ only $x+11$ is possibly in the sequence, which must be $[30k+25, 30(k+1)+10]$. But then $30(k+1)+7\pm 13$ both lie outside the sequence. We are done by the same reasoning as the previous case.

Solution 2:

Theorem. (S. S. Pillai) For $m\in\mathbb N$ the following statements are equivalent:
(1) there is a set of $m$ consecutive integers, none of which is relatively prime to all the others;
(2) $m\ge17$.

The smallest example of a set as in (1) is $\{2184,2185,\dots,2200\}$.

S. S. Pillai, On $m$ consecutive integers—III, Proc. Indian Acad. Sci. 13 (1941), 530–533.

Irene Gassko, Stapled sequences and stapling coverings of natural numbers, Electronic Journal of Combinatorics, Volume 3, Issue 1, 1996.