# Show that there exists infinitely many numbers that are coprime pairwise, in the set defined as following [duplicate]

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.

-

## marked as duplicate by Mathmo123, saz, Davide Giraudo, graydad, Ivo TerekMar 8 '15 at 16:57

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

-

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

-
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
@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!

-