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

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?.
-

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$.

-

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

First, any common factor of a and b will divide every xn. 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 xn. 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 = {p1,...,pm} be a finite set of primes not dividing a. Taking n to be a multiple of ∏k(pk − 1) gives xn = 1 + b ≠ 0 (mod pk), so is not a multiple of pk. If S is the set of prime factors of any finite collection of the xn, this shows that we can find a new xn 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.

-