2
$\begingroup$

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

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

  • 1
    You have to enclose the $y+1$ in curly braces to make it a subscript: `a_{y+1}`.2012-12-10

2 Answers 2

2

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}$.

0

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$