Construction of an infinite set such that any two number from the set are relatively prime

Question

This question is taken from a contest in India.

• Prove that we can construct an infinite set of positive integers of the form $2^{n}-3$, where $n \in \mathbb{N}$, such that any two numbers from the set are relatively prime

I would like to have an answer for this question, and i would also like to know why $2^{n}-3$ has importance here. Can this question be generalized. That is:

• Can we construct an infinite set of positive integers of the form $k^{n} -(k+1)$ such that any two numbers from the set are relatively prime?.

Answer 1

Given a set of odd primes $\displaystyle S = \{p_1, p_2, \dots, p_m \}$, we can find an $n$ such that $\displaystyle 2^n - 3 = 1 \mod p_i$, by choosing $n = 2 + \prod (p_i-1)$

Thus starting with

$\{2^2 -3,2^3 - 3\}$ we can add a new member which is relatively prime to all the previous members.

I believe a similar argument will hold for other $k$ (when considering $k^n -(k+1)$), since we will have $gcd(p_i,k) =1$.

Answer 2

Further to Moron's answer, consider any sequence of the form x_n = aⁿ + b for fixed integers a,b. Is there an infinite set of the x_n for which any two are coprime?

First, any common factor of a and b will divide every x_n. Furthermore, for any n, $$ x_n=(a^{n-1}+a^{n-2}+\cdots+a+1)(a-1)+(b+1). $$ so any common factor of a − 1 and b + 1 will divide every x_n. The answer to the question is no if either a, b or a − 1, b + 1 have a common prime factor.

If a, b are coprime and every factor of b + 1 divides a then the answer is yes. Let S = {p₁,...,p_m} be a finite set of primes not dividing a. Taking n to be a multiple of ∏_k(p_k − 1) gives x_n = 1 + b ≠ 0 (mod p_k), so is not a multiple of p_k. If S is the set of prime factors of any finite collection of the x_n, this shows that we can find a new x_n coprime to each of the ones so far and, by induction, we can find an infinite set.

This shows that the answer is yes in the cases you mention a = 2, b = -3 and a = k, b = -(k + 1). It does, however, leave open the cases where a,b are coprime and b + 1 has prime factors not dividing a or a − 1.