How to prove Fibonacci recurrence holds mod p?

Question

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.

Answer 1

Write $a=\frac12(1+c)$ and $b=\frac12(1-c)$. Then $a+b=1$ and $$ab=\frac14(1-c^2)\equiv\frac14(1-5)\equiv-1\pmod p.$$ Therefore $$a^2-a-1\equiv a^2-(a+b)a+ab\equiv0\pmod p$$ and $$b^2-b-1\equiv b^2-(a+b)b+ab\equiv0\pmod p.$$ Then $$c(J_n-J_{n-1}-J_{n-2})\equiv a^n-b^n- a^{n-1}+b^{n-1}-a^{n-2}+b^{n-2} \equiv(a^2-a-1)a^{n-2}+(b^2-b-1)b^{n-2}\equiv0\pmod p. $$ It follows that $J_n\equiv J_{n-1}+J_{n-2}$ (mod $p$).

Answer 2

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