1. ## Sequence and divisibility

We have recurrent sequence of integer number a1,a2,... a1=1, a2=2 an=3a(n-1)+5a(n-2) for n=3,4,5,... Is integer number k>=2, that a(k+1)*a(k+2) mod ak = 0 ? Please for quick help

2. Originally Posted by terafull
We have recurrent sequence of integer number a1,a2,... a1=1, a2=2 an=3a(n-1)+5a(n-2) for n=3,4,5,... Is integer number k>=2, that a(k+1)*a(k+2) mod ak = 0 ? Please for quick help
Lets just translate this into good English.

$\displaystyle \{a_n\}$ is a sequence definde by the recurrence:

$\displaystyle a_1=1,\ a_2=2,\ a_n=3a_{n-1}+5a_{n-2} \mbox{ for }n>2$

Is there a $\displaystyle k \ge 2$ such that:

$\displaystyle a_{k+1}\times a_{k+2} \equiv 0 \mbox{ modulo } a_k$?

RonL

3. Exactly, thx

4. Originally Posted by CaptainBlack
Lets just translate this into good English.

$\displaystyle \{a_n\}$ is a sequence definde by the recurrence:

$\displaystyle a_1=1,\ a_2=2,\ a_n=3a_{n-1}+5a_{n-2} \mbox{ for }n>2$

Is there a $\displaystyle k \ge 2$ such that:

$\displaystyle a_{k+1}\times a_{k+2} \equiv 0 \mbox{ modulo } a_k$?

RonL
Well, let's start by writing out an explicit representation of the series:
$\displaystyle a_n = \left ( \frac{-29 + 13\sqrt{29}}{290} \right ) \left ( \frac{3 + \sqrt{29}}{2} \right ) ^n + \left ( \frac{-29 - 13\sqrt{29}}{290} \right ) \left ( \frac{3 - \sqrt{29}}{2} \right ) ^n$

You wish to know if
$\displaystyle a_{n + 2} a_{n + 1} \equiv 0 \text{ mod }a_n$

$\displaystyle a_{n + 2} = 3a_{n + 1} + 5a_n$

So this amounts to wanting to know if
$\displaystyle (3a_{n + 1} + 5a_n ) a_{n + 1} \equiv 0 \text{mod }a_n$

Which amounts to questioning if $\displaystyle a_n$ ever divides $\displaystyle a_{n + 1}$ evenly.

-Dan

By the way, I've been practicing my difference equations:
$\displaystyle a_n = \left ( \frac{-29 + 13\sqrt{29}}{290} \right ) \left ( \frac{3 + \sqrt{29}}{2} \right ) ^n + \left ( \frac{-29 - 13\sqrt{29}}{290} \right ) \left ( \frac{3 - \sqrt{29}}{2} \right ) ^n$

5. I had done what you wrote, but I dont know what next... I dont see proof for: $\displaystyle a_n$ ever divides $\displaystyle a_{n + 1}$ od doesnt divide.

6. We will show that $\displaystyle \gcd(a_n,a_{n+1}) = 1$ for all $\displaystyle n$ this is true for $\displaystyle n=1$ now accept induction. Say $\displaystyle d=\gcd(a_{n+1},a_{n+2})$ then $\displaystyle d|a_{n+1}$ and $\displaystyle d|a_{n+2}\implies d|(5a_{n+1}+3a_n)\implies d|(3a_n)$. Now if $\displaystyle d>1$ (by contradiction) then $\displaystyle d\not | a_n\implies d|3$ thus $\displaystyle d=3$. It remains to show that none of the numbers in this sequence ever are divisible by 3. Again accept induction. Say $\displaystyle a_{n+1} = 5a_n+3a_{n-1}$ is divisible by 3 this means $\displaystyle 3|(5a_n)\implies 3|5$ by induction. Which is an impossibility.