10
$\begingroup$

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$

$\endgroup$
9
  • 3
    $\begingroup$ See Solution-O51 in projectpen.files.wordpress.com/2009/06/pen-a9-a37-o511.pdf $\endgroup$
    – Ege Erdil
    May 11, 2016 at 14:26
  • 1
    $\begingroup$ @HamidRezaEbrahimi modulo $30$ is used because $2\cdot 3\cdot 5=30$, so the numbers congruent to one of $1,7,11,13,17,19,23,29$ are automatically not divisible by $2,3,5$. $\endgroup$ May 11, 2016 at 14:59
  • 2
    $\begingroup$ The proof referenced above is wrong. It claims that if we have 8 consecutive odd numbers, then we can always find one which is not divisible by any of 2, 3, 5, 7, 11 or 13. But we have 20573 divisible by 7, 20575 by 5, 20577 by 3, 20579 by 13, 20581 by 11, 20583 by 3, 20585 by 5 and 20587 by 7. $\endgroup$
    – almagest
    May 11, 2016 at 15:40
  • 1
    $\begingroup$ A deceptively simple question. $\endgroup$
    – Mr. Brooks
    May 11, 2016 at 21:16
  • 1
    $\begingroup$ I thought someone else would have mentioned by now that "any consecutive 16 natural numbers" is not quite the same as $16k, 16k + 1, \ldots, 16k + 15". For example, compare 273, ..., 288 to 276, ..., 291. $\endgroup$ May 12, 2016 at 5:08

2 Answers 2

5
$\begingroup$

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.
$\endgroup$
2
  • $\begingroup$ My answer is quite long-winded as it stands, but I do want to note that careful examination of the finicky cases allow one to construct a sequence of seventeen consecutive integers with each element sharing a prime factor with another in the sequence. $\endgroup$
    – Rolf Hoyer
    May 12, 2016 at 6:04
  • $\begingroup$ I feel there must be a shorter answer to this question.However I appreciate your answer. $\endgroup$ May 12, 2016 at 12:53
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.