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 already has an answer here:

The set $A$ = {$X_n\mid n\in \Bbb N$} where $X_n = a^{n+1} + a^{n} - 1$, with $a \gt 1, a \in \Bbb Z$.

Show that there are infinitely many numbers that are pairwise coprime.

share|improve this question

marked as duplicate by Mathmo123, saz, Davide Giraudo, graydad, Ivo Terek Mar 8 at 16:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3 Answers 3

The givens solution are not correct as pointed by bigant146 in this question and I gave a correct answer there.

share|improve this answer

$(a^{n+2}+a^{n+1}-1,a^{n+1}+a^n-1)$

$=(a^{n+2}-a^{n},a^{n+1}+a^n-1)$

$=((a^{2}-1)a^{n},a^{n+1}+a^n-1)$

$=(a^{2}-1,a^{n+1}+a^n-1)$ as $(a^n,a^{n+1}+a^n-1)=1$

$=((a-1)(a+1),a^n(a+1)-1)$

$=(a-1,a^n(a+1)-1)$ as $(a+1,a^n(a+1)-1)=1$

$=(a-1,a^n(a-1)+2(a^n-1)+1)=1$

share|improve this answer
    
This is not sufficient. We are looking for an infinite subset $M\subset \mathbb N$ such that $\gcd(X_n,X_m)=1$ for all $n.m\in M$ with $n\ne m$, not only for the case $m=n+1$. –  Hagen von Eitzen Oct 17 '12 at 16:03
1  
@HagenvonEitzen, this is an infinite set, containing $X_n$ for all positive integral values of $n$. Now, I've shown that $(X_{n+1},X_n)=1$, so there are infinitely many such pairs, right? –  lab bhattacharjee Oct 18 '12 at 11:43

Assume $n>m$. Let $d=n-m$. Since integer linear combinations of multiples of $\gcd(X_n,X_m)$ are again multiples of $\gcd(X_n,X_m)$, we find that $X_n-a^dX_m = a^d-1$ is a multiples of $\gcd(X_n,X_m)$. Consider the case that $n$ is a proper multiple of $m$. Then $d$ is also a multiple of $m$ and using the well-known fact that $x-y$ divides $x^k-y^k$, we see that $a^m-1$ is a multiple of $a^d-1$, hence $X_m - (a+1)(a^m-1)= a$ is a multiples of $\gcd(X_n,X_m)$. Finally, since $d>0$ we have that $a^{d-1}\cdot a-(a^d-1)=1$ is a multiple of $\gcd(X_n,X_m)$, i.e. $\gcd(X_n,X_m) = 1$. Thus all we have to do is take an infinite subset $M\subseteq \mathbb N$ such that any tow elements of $M$ are multiples of each other. For example, one could take all powers of $2$ as $M$. Then $B:=\{X_m\mid m\in M\}$ has the required properties: It is infinite (because $a>1$) and any two distinct elements of $B$ are coprime.

Remark: We used $a>1$ only to conclude that $B$ is infinite!

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.