Prove that the set of integers of the form $2^k−3$ contains an infinite subset of relatively prime numbers 
Prove that the set of integers of the form $2^k − 3(k = 2, 3, ...) $
  contains an infinite subset in which every two members are relatively
  prime.


Trying to solve this problem, I stumbled on this conjecture: 
There is an infinity of prime numbers $p$ such that $p=2^n - 1, n\in \mathbb{N}$
I'm interested in solving both the problem and the conjecture.
 A: 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 ...
A: 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.
A: 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$.
A: Let $p_i$ be the $i^\text{th}$ odd prime. Let $(k_r)_{r=1}^\infty$ be any sequence of integers such that $k_1 \geqslant 3$, $k_{r+1} > k_r$, and $k_{r+1}$ is divisible by $\prod_{i=1}^{m_r} (p_i - 1)$, where $p_{m_r}$ is the largest prime factor of $a_r = 2^{k_r} - 3$. Then
$$
a_{r+1} = \left(2^{k_{r+1}/(p_i - 1)}\right)^{p_i - 1}\!\!\! - 3
\equiv -2 \pmod{p_i} \quad (i = 1, \ldots, m_r),
$$
by Fermat's little theorem. Therefore, $a_{r+1}$ has no prime factor in common with $a_r$; and $m_{r+1} > m_r$. The sequences $(k_r)$, $(m_r)$, $(a_r)$ are strictly increasing. If $r, s$ are integers with $1 \leqslant r < s$, then $a_s$ is not divisible by any of the primes $p_1, \ldots, p_{m_{s-1}}$, in particular $p_1, \ldots, p_{m_r}$, therefore $a_s$ is prime to $a_r$.
