Find the sequence defined by the recurrence equation $x_{n+1} = 4x_n − x_{n−1}, (n ≥ 1)$ with $x_0 = 1$ and $x_1=2$. Find an odd prime factor of $x_{2015}$.
I've found the characteristic equation to be $x^2-4x+1=0$ and the solutions for it to be $x=2+\sqrt3$ and $x=2-\sqrt3$. I've also found 2015 to equal the product of the odd primes $5*13*31$, but don't know what to do with that, or if its relevant to being with.
What is it that I'm supposed to do next?
As stated in the question the associated quadratic is $x^2-4x+1=0$ with roots $x=2\pm\sqrt3$, so the general solution to the recurrence is $x_n=A(2+\sqrt3)^n+B(2-\sqrt3)^n$. Putting $x_0=1,x_1=2$ we get $A=B=\frac{1}{2}$.
In particular $x_{2015}=\frac{1}{2}\left((2+\sqrt3)^{2015}+(2-\sqrt3)^{2015}\right)$, which we can also write as the nearest integer to $\frac{1}{2}(2+\sqrt3)^{2015}$.
$x_{2015}$ is clearly far too large to factorise directly, but we often find that recurrence sequences are periodic modulo a prime, so we look at the first few terms: $x_1=2,x_2=7,x_3=26,x_4=97$, $x_5=362$.
If we now look at residues mod 7 we find they are 0 for $n=2\bmod 4$. That does not help. If we look at residues mod 13 we find they are 0 for $n=3\bmod 6$. Again that does not help. But the pattern of 0 for $n=k\mod 2k$ suggests that we might get lucky with $x_5$ and find that the residues mod 181 are 0 for $n=5\bmod 10$. Indeed that is the case: the first few residues are: $2, 7, 26, 97, 0, 84, 155, 174, 179, 180, 179, 174, 155, 84, 0$.
So we conclude that 181 is a factor of $x_{2015}$.