Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

marked as duplicate by Mathmo123, saz, Davide Giraudo, graydad, Ivo Terek Mar 8 '15 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.

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

share|cite|improve this answer




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


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


share|cite|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
@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|cite|improve this answer

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