# How to show this is relatively prime?

Let $a_1= 2$, and for each $y > 1$, deﬁne $a_{y+1} = a_y(a_y −1) +1$.

Prove that for all $x \ne y$, $a_x$ and $a_y$ are coprime.

-
In the second equality of the first line, in the left side, it must be $\,a_{y+1}\,$ , I think...and not what you wrote. – DonAntonio Dec 10 '12 at 4:40
Yes, you're right. Thank you. – guest525 Dec 10 '12 at 4:41
You have to enclose the $y+1$ in curly braces to make it a subscript: a_{y+1}. – Brian M. Scott Dec 10 '12 at 4:42

We show that if $m\ne n$, then $a_m$ and $a_n$ are relatively prime.

Without loss of generality we may assume that $m\lt n$. We show by induction on $i$ that if the prime $p$ divides $a_m$, then $a_{m+i}\equiv 1\pmod{p}$. This implies that if $m\lt n$, then $a_m$ and $a_n$ are relatively prime.

Let $P(x)=x(x-1)+1$. If $i=1$, then $a_{m+i}=P(a_m)\equiv (0)(1)+1\equiv 1\pmod{p}$. Now suppose that $a_{m+i}\equiv 1\pmod{p}$. Then $a_{m+i+1}=P(a_{m+i})\equiv (1)(0)+1\equiv 1\pmod{p}$.

-

Hint:

$a_{y+1}=a_y(a_y-1)+1$

$\implies a_{y+1}-1=a_y(a_y-1)$

So, $a_y-1=a_{y-1}(a_{y-1}-1)$ and $a_{y+1}-1=a_ya_{y-1}(a_{y-1}-1)$

$a_{y-1}-1=a_{y-2}(a_{y-2}-1)$ and

so $a_{y+1}-1=a_ya_{y-1}a_{y-2}(a_{y-2}-1)=(a_1-1)\prod_{y\le x \le1}a_x=\prod_{y\le x \le1}a_x$ as $a_1=2$

As $(a_{y+1}-1,a_{y+1})=1, (\prod_{y\le x \le1}a_x,a_{y+1})=1\implies (a_x,a_{y+1})=1$ for $x\le y$

-