# Thread: Sequence and divisibility

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.

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

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

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

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

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

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

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

$
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:
$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
$a_{n + 2} a_{n + 1} \equiv 0 \text{ mod }a_n$

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

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

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

-Dan

By the way, I've been practicing my difference equations:
$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: $a_n$ ever divides $a_{n + 1}$ od doesnt divide.

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