Recurrences and Divisors

Solution

$a_1:b_1=6:61$ , let $a_1= 6k , b_1=61k$

$b_1^1-a_1^2= 61^2k^2- 6^2 k^2 = 3685$ .....given

Thus $k^2(61^2-6^2) = k^23685 = 3685$

Hence k= $\pm1$ but as given that $\forall a_i,b_i \geq 0$ , $k\neq -1$

Hence $a_1= 6$ , $b_1 = 61$

We have recurrence for $a_n$ with characteristic equation $x^2-8x+7=0$ which has roots 7 and 1

Hence $a_n= A_1\times 7^n +B_1 \times 1^n$ ....from initial conditions $a_0=0$ and $a_1=6$ we can calculate $A_1=1 , B_1= -1$

Hence $a_n=7^n-1$

Similarly recurrence for $b_n$ has characteristic equation with roots 63 and 2 hence

$b_n=A_2\times63^n + B_2\times 2^n$

and from initial conditions , $A_2= 1 , B_2=-1$

Hence $b_n=63^n-2^n$

Now we need the last 5 digits of $a_2560$ which are last five digits of $7^{2560}-1$ and they are 36000 .( $7^{2560}\equiv 36001 \pmod {10^5}$ )

Last five digits of $b_{1000}$ will be last five digits of $63^{1000}-2^{1000}$ which are 70625 ... ( $63^{1000}-2^{1000}\equiv 70625 \pmod {10^5}$ )

GCD of 36000 and 70625 is $\boxed{125}$ .