# Stapled sequences- set of consecutive positive integers such that no one of them is relatively prime with all of the others

A stapled sequence is defined as a set of consecutive positive integers such that no one of them is relatively prime with all of the others. When I first came across this definition, I thought it wouldn't be that difficult to find an $$n\in \mathbb N$$ such that every set $$A=\{i\in\mathbb N: j≤i≤j+n-1\}$$ for some $$j\in \mathbb N$$ is a stapled sequence.

It turned out, however, that it wasn't that trivial. I first tried to use the "identity" $$\text{gdc}(a,b)=\text{gcd}(a-bt,b)\;\;\forall a,b,t\in\mathbb N$$but it took me nowhere.

I then found an article which seemed to help; in the abstract of this article they assert, that there's a very simple proof to show that no stapled sequence containing $$N$$ consecutive positive intgers exist for any $$N < 17$$.

Nevertheless, I've tried to read the article and I don't find their proof trivial; I don't even understand it!

(It might be worth to tell that I'm a secondary school student interested in maths).

Could someone help me understand their proof or provide a own proof?

I agree that the notations in the article are a little bit confusing and overkill if you're only interested in the result that there are no stapled sequences of length $$\lt 17$$. So here goes my simplified (but longer, because there are more details and explanations) presentation.

I say that two integers are friends if they are distinct and not coprime, and that they are $$p$$-friends (for a prime $$p$$) if they are distinct and both divisible by $$p$$. Thus, two integers are friends iff they are $$p$$-friends for some prime $$p$$, and a stapled sequence is a sequence in which everyone has a friend.

Lemma 3.6 (of the paper) If there is a stapled sequence of length $$2N$$, then

(a) there is also a stapled sequence of length $$2N+1$$.

(b) there is also a stapled sequence of length $$2N-1$$.

Proof of lemma 3.6 Let $$S=(x+1,x+2,\ldots,x+2N)$$ be a stapled sequence of length $$2N$$.

(a) Suppose first that $$x$$ is odd. Then I claim that $$(x+1,x+2,\ldots,x+2N+1)$$ is also stapled. Indeed, everyone except perhaps $$x+2N+1$$ already has a friend, and $$x+2N+1$$ is even and therefore a $$2$$-friend to $$x+1$$. A mirror argument shows that $$(x,x+1,\ldots,x+2N)$$ is stapled when $$x$$ is even.

(b) Suppose first that $$x$$ is odd. Then I claim that the follwing set is also stapled : $$T=(x+1,x+2,\ldots,x+2N-1)$$. To show this, we take a $$y$$ in $$T$$ and show that it has a friend in $$T$$. By hypothesis, $$y$$ has friend $$z$$ in $$S$$. If $$z\neq x+2N$$, then $$z$$ is already in $$T$$ and we are done. If $$z=x+2N$$, there is a prime $$p$$ that divides both $$x+2N$$ and $$z$$. If $$p, either $$y-p$$ or $$y+p$$ is in $$T$$ and is a $$p$$-friend of $$y$$, and we are done also. Finally, if $$p\geq N$$, then there are only two integers divisible by $$p$$ in $$S$$, namely $$x+2N$$ and $$x+2N-p$$. So $$y=x+2N-p$$ is even and has $$2$$-friends inside $$T$$, which finishes the proof that $$T$$ is stapled. A mirror argument shows that $$(x+2,x+3,\ldots,x+2N)$$ is stapled when $$x$$ is even.

Lemma 3.7 (of the paper) If there is a stapled sequence of length $$p$$ where $$p$$ is an odd prime, then there is also a stapled sequence of length $$p+1$$.

Proof of lemma 3.7 Let $$S=(x+1,x+2,\ldots,x+p)$$ be a stapled sequence of length $$p$$. By the Chinese remainder theorem, there is an $$x'$$ such that $$x'$$ is congruent to $$x$$ modulo every prime $$, and such that $$x'+p+1$$ is divisible by $$p$$. Then $$x'+1$$ and $$x'+p+1$$ are $$p$$-friends, and friends in $$S=(x+1,x+2,\ldots,x+p)$$ stay friends when translated by $$x'-x$$. Thus $$S'=(x'+1,x'+2,\ldots,x'+p+1)$$ is a stapled sequence.

Taking the contrapositive statements of lemmata 3.6 and 3.7, we obtain the following :

Corollary. Let $$Z$$ be the set of all integers $$z$$ such that there are no stapled sequences of length $$z$$. Then :

(R1) If $$z\in Z$$ is odd, then $$z-1\in Z$$ also.

(R2) If $$z\in Z$$ is such that $$z-1$$ is prime, then $$z-1\in Z$$ also.

(R3) If $$z\in Z$$ is odd, then $$z+1\in Z$$ also.

In particular, applying rules R1 and R2 alternatively one sees that if $$15\in Z$$, then all of $$14,13,12,11,10$$ are in $$Z$$ ; also $$16\in Z$$ by R3. Similarly, if $$9\in Z$$ then all of $$8,7,6,5,4,3,2$$ are in $$Z$$.

So, to show that there are no stapled sequences in length $$\leq 16$$, it suffices to show that there are no stapled sequences in length $$9$$ or $$15$$.

Theroem 3.8 (of the paper) There are no stapled sequences of length $$\leq 16$$.

Proof of theorem 3.8 from lemma. As noted above, it suffices to show that

(a) There are no stapled sequences in length $$9$$.

(b) There are no stapled sequences in length $$15$$.

(a) : Suppose that $$S=(x+1,x+2, \ldots,x+9)$$ is stapled. The set $$Y=\lbrace x+1,x+3,x+5,x+7,x+9\rbrace$$ contains at most two multiples of $$3$$, at most one multiple of $$5$$ and at most one multiple of $$7$$. So some $$y\in Y$$ is not divisible by any of $$3,5,7$$. We know that $$y$$ has a friend $$z$$ in $$S$$, so they are both divisible by a prime $$p$$. The only possibility is then $$p=2$$, so $$x$$ is odd. Next, consider $$U=\lbrace x+2,x+4,x+6,x+8\rbrace$$. This set contains at most one multiple of $$5$$ and at most one multiple of $$7$$, so there are two elements $$u_1,u_2 \in U$$ not divisible by $$5$$ or $$7$$. We know that $$u_i(1\leq i \leq 2)$$ has a friend $$v_i$$ in $$S$$, so they are both divisible by a prime $$p_i$$. The only possibility is then $$p_i=3$$ (for both values of $$i$$). So both $$u_1$$ and $$u_2$$ are divisible by $$3$$ ; but the only two elements congruent to each other modulo $$3$$ in $$U$$ are $$x+2$$ and $$x+8$$. It follows that $$x\equiv 1[\mod 3]$$. Combining the two congruences that we now have on $$x$$, we see that $$x$$ is of the form $$6q+1$$. But then $$x+4=6q+5$$ and $$x+6=6q+7$$, and one of those two numbers is not divisible by any of $$2,3,5$$, and therefore cannot have any friends in $$S$$.

(b) : Suppose that $$S=(x+1,x+2, \ldots,x+15)$$ is stapled.

Each element of $$A(x)=\lbrace x+3,x+4,\ldots,x+13\rbrace$$ has a friend in $$S$$ which is at at most $$12$$ of distance to it, and so must be divisible by a prime $$\leq 12$$.

Each element of $$B(x)=\lbrace x+5,x+6,\ldots,x+11\rbrace$$ has a friend in $$S$$ which is at at most $$10$$ of distance to it, and so must be divisible by a prime $$\leq 10$$.

Next, let $$C(x)$$ be set of all elements of $$A(x)$$ not divisible by $$2$$ or $$3$$. The content of $$C(x)$$ depends of the value of $$x$$ modulo $$6$$ :

$$\begin{array}{|l|c|} \hline x \ (mod\ 6) & C(x) \\ \hline 0 & \lbrace x+5,x+7,x+11,x+13\rbrace \\ \hline 1 & \lbrace x+4,x+6,x+10,x+12\rbrace \\ \hline 2 & \lbrace x+3,x+5,x+9,x+11\rbrace \\ \hline 3 & \lbrace x+4,x+8,x+10\rbrace \\ \hline 4 & \lbrace x+3,x+7,x+9,x+13\rbrace \\ \hline 5 & \lbrace x+6,x+8,x+12,x+14\rbrace \\ \hline \end{array}$$

We see then that $$x \ (mod\ 6)$$ is not $$3$$ or $$4$$, then $$C(x)$$ is a set of four elements that are not congruent to each other modulo $$5,7$$ or $$11$$, so that one of them is not divisible by $$5,7$$ or $$11$$, which is impossible. So we can assume that $$x \ (mod\ 6)$$ is $$3$$ or $$4$$. Next, let $$D(x)$$ be set of all elements of $$C(x)$$ not divisible by $$2$$ or $$3$$. We have :

$$\begin{array}{|l|c|} \hline x \ (mod\ 6) & D(x) \\ \hline 3 & \lbrace x+8,x+10\rbrace \\ \hline 4 & \lbrace x+5,x+9,x+11\rbrace \\ \hline \end{array}$$

Reasoning as before, we see that $$x \equiv 4 (mod\ 6)$$ is impossible. So we must have $$x \equiv 3 (mod\ 6)$$, and further, one of $$x+8,x+10$$ is divisible by $$5$$, and the other is divisible by $$7$$.

But then, in $$C(x)=\lbrace x+4,x+8,x+10\rbrace$$, the remaining $$x+4$$ is not divisible by $$5$$ or $$7$$ and so cannot have any friends in $$S$$. This finishes the proof.