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.

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

2 Answers 2

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

Your Answer

 
discard

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

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