<s>[INST] How to prove Fibonacci recurrence holds mod p? Let $$J_n \equiv c^{-1} \Big( \Big( \dfrac{1+c}{2} \Big)^n - \Big( \dfrac{1-c}{2} \Big)^n \Big) \ \text{(mod  p)},$$ with $c$ and $c^{-1}$ integers such that $c^2 \equiv 5 \ \text{(mod  p)}$ and $cc^{-1} \equiv 1 \ \text{(mod  p)}$. And $c$ is an odd integer. 
It is easy to check that $J_1 \equiv J_2 \equiv 1 \ \text{(mod  p)}$. However, I can't prove that $J_{n} \equiv J_{n-1} + J_{n-2} \  \text{(mod  p)}$.
My attempt: $$J_{n-1} + J_{n-2} = c^{-1} \Big( \Big( \dfrac{1+c}{2} \Big)^{n-2} - \Big( \dfrac{1-c}{2} \Big)^{n-2}\Big) \Big( \dfrac{6+2c}{4} \Big) + k_3 p = c^{-1} \Big( \Big( \dfrac{1+c}{2} \Big)^n - \Big( \dfrac{1-c}{2} \Big)^n\Big) + c^{-1} \Big( \dfrac{1+c}{2} \Big)^{n-2} \dfrac{k_1p}{4} - c^{-1} \Big( \dfrac{1-c}{2} \Big)^{n-2} \Big(1+ \dfrac{k_2p}{4} \Big) + k_3 p$$ which after a long try still I can't reduce it to the desired result because of factor 4 in the denominator. 
PS I always keep  $k_ip$'s to avoid mistakes working in mod p.
Please help! 
Edit. If $\dfrac{c^{-1}}{2^2} ((1+c)^{n-2} - (1-c)^{n-2})$ were an integer for any $n$ then we are done! But that also I couldn't prove. 
 [/INST] $$J_n \equiv c^{-1} \Big( \Big( \dfrac{1+c}{2} \Big)^n - \Big( \dfrac{1-c}{2} \Big)^n \Big) \ \text{(mod  p)}$$
In order to show that $$J_n = J_{n-1}+J_{n-2}$$ it suffices to show that  both $ (\frac {1+c}{2})^n$ and    $ (\frac{1-c}{2})^n$ satisfy the same relation.
Note that for $ (\frac {1+c}{2})^n =(\frac{1+c}{2})^{n-1} +(\frac{1+c}{2})^{n-2} $ it suffices to show  that $\frac{1+c}{2}$ satisfies $$x^2-x-1=0$$
Solving for $c$ we get $c=\sqrt 5$ which solves the problem.  
</s>