Exercise 4.5.2* (Revisited example 4)

Proof.

Write $𝒮$ in the form $𝒮=\{a_1,a_2,\dots ,a_{n+1}\}\subset [[1,2n+1]]$, where $a_1<a_2<\cdots <a_{n+1}$.

• If there is some $i\in [[1,n]]$ such that $a_{i+1}=a_i+1$, then $a_i$ and $a_{i+1}$ are two relatively prime integers, and we are done.

• At the contrary, suppose that $a_{i+1}-a_i\ge 2$ for all $i\in [[1,n]]$. Then

  $$\begin{array}{lll}\hfill a_{n+1}-a_1=\underset{i=1}{\overset{n}{\sum }}(a_{i+1}-a_i)\ge 2n.& & \hfill \text{(1)}\end{array}$$

  Moreover $1\le a_1<a_{n+1}\le 2n+1$, so

  $$\begin{array}{lll}\hfill a_{n+1}-a_1\le 2n.& & \hfill \text{(2)}\end{array}$$

  If there is some $i\in [[1,n]]$ such that $a_{i+1}-a_i>2$, then

  $$a_{n+1}-a_1=\underset{i=1}{\overset{n}{\sum }}(a_{i+1}-a_i)>2n,$$

  in contradiction with (2). Therefore, for all $i\in [[1,n]]$,

  $$a_{i+1}-a_i=2.$$

  Similarly, if $a_1>1$, then $1<a_1<a_{n+1}\le 2n+1$, thus $a_{n+1}-a_1<2n$, in contradiction with (1). Therefore $a_1=1$. Since $a_{i+1}-a_i=2$ for all $i$,

  $$a_i=1+2i(1\le i\le n).$$

  In particular $a_1=1$ and $a_2=3$ are two relatively prime integers (here $n\ge 1$, otherwise there is nothing to prove).

In both cases, $𝒮$ contains two relatively prime integers.

If $𝒮$ may contain only $n$ integers, we can choose $a_1=2,a_2=4,\dots ,a_n=2n$. Then $𝒮\subset [[1,2n+1]]$, but $𝒮$ does not contain two relatively prime integers. □