Prove that the set of integers of the form $2^k−3$ contains an infinite subset of relatively prime numbers

Solution 1:

Here is an incomplete proof attempt involving the infinite Ramsey theorem:

Let $G$ denote the infinite complete graph with vertices $2^k-3$, $k\in\mathbb{N}\backslash\{1\}$. Colour an edge of $G$ red if its ends are relatively prime and blue if they are not. Applying infinite Ramsey gets us an infinite red subgraph of $G$, in which case we're done, or an infinite blue subgraph.

I claim the latter cannot happen: Suppose there infinitely many $k$ such that the corresponding $2^k-3$ are pairwise not relatively prime. Then there must exist a prime $p$ dividing $2^{k_n}-3$ for infinitely many $k_1<k_2< k_3\ldots$ and clearly $p\neq 2$.

Note that $p$ divides each difference $2^{k_{n+1}}-2^{k_n}=2^{k_n}(2^{k_{n+1}-k_n}-1)$ and hence divides $2^{k_{n+1}-k_n}-1$. Let $m$ be smallest with the property that $p$ divides $2^m-1$. If for some $n$ we have $k_{n+1}-k_n>m$, then by applying the same divisibility argument to the difference $2^{k_{n+1}-k_n}-2^m$, we obtain a contradiction to the definition of $m$. Hence, the $k_n$ are in arithmetic progression $k_n=a+nm$, which is (probably) absurd.

Solution 2:

A prime of the form $2^n-1$ is called a Mersenne prime. It is an open problem whether there are infinitely many of them -- but there are no concrete signs of the supply running out; the largest currently known primes are all Mersenne primes.

Hint for the original problem: Show that it's a sufficient condition for $2^k-3$ and $2^j-3$ to be coprime that $(k-2)\mid(j-2)$ but $k\ne j$. Then consider exponents of the form, for example, $n!+2$.

Hmm, I have no idea why I thought that would work. It's not the case the $2^{2+2}-3$ and $2^{14+2}-3$ are coprime, for example, despite $2\mid 14$. But I can't delete the answer because it is accpted ...

Solution 3:

There's a solution available here.

To reproduce it, lest the link go dead:

Clearly we can find a subset of size 1. We show how to enlarge a set of $r$ such integers to a set of $r+1$, so that the result then follows by induction.

So suppose $2^{n_1} - 3, ... , 2^{n_r} - 3$ are all relatively prime. The idea is to find $n$ such that $2^n - 1$ is divisible by $m = (2^{n_1} - 3) \cdots (2^{n_r} - 3)$, because then $2^n - 3$ must be relatively prime to all of the factors of $m$.

At least two of $2^0, 2^1, ... , 2^m$ must be congruent mod $m$. So suppose $m_1 > m_2$ and $2^{m_1} \equiv 2^{m_2} \mod m$. Then we must have $2^{m_1 - m_2} - 1 \equiv 0 \mod m$, since $m$ is odd. So we may take $n_{r+1}$ to be $m_1 - m_2$.