Why is $2(5u_p)^2\equiv (1+5^p)+4 \bmod 2p-1$?

Definition: $u_1=u_2=1$ and $u_{n+1}=u_{n}+u_{n-1}$ for $n\ge 2$.

Suppose $p \ge 7$ is a prime for which $p\equiv 2 \bmod 5$ or $p \equiv 4 \bmod 5$. If $2p-1$ is also a prime, then how can I show that $2p-1|u_p$?

My book has the following proof:

Suppose $p$ has the form $5k+2$ for some $k$. Using the Binet's formula, we get $$5u_p^2=\frac{1}{2^{2p-1}}[1+\binom{2p}{2}5+\dots +(\binom{2p}{2p}5^p]+2$$ As $\binom{2p}{k}\equiv 0 \bmod 2p-1$ for $2\leq k < 2p-1$ and $2^{2p-1}\equiv 1 \bmod 2p-1$ by Fermat's little theorem, $2(5u_p)^2\equiv (1+5^p)+4 \bmod 2p-1$.

How did we conclude that $2(5u_p)^2\equiv (1+5^p)+4 \bmod 2p-1$ ?

Perhaps, I am missing something obvious but I can't seem to get this line.

• @CalvinLin, I just edited it. Thanks. – user96343 Apr 28 '15 at 14:19
• Can you check, For $p=2$, $LHS =5$, $RHS = \frac{1}{8} ( 1 + 6\times 5 + 5^2) + 2 = 7 + 2 = 9$. – Calvin Lin Apr 28 '15 at 14:24
• I don't get something here: you repeatedly write $(1+5^p)+4$; why not $5+5^p$ directly? – Alex M. Apr 28 '15 at 14:30

There is a error on your question: $q=2p-1 \implies 2^{q-1}\equiv1\pmod{q}$ for a prime number $q$, so $2^{2p-1-1}\equiv1\pmod{2p-1}$ or $2^{2p-2}\equiv1\pmod{2p-1}$ which implies $2^{2p-1}\equiv2\pmod{2p-1}$, not $2^{2p-1}\equiv1\pmod{2p-1}$. With that result and multiplying by $2^{2p-1}$ you can conclude the final congruence.