Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?.
share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.