I haven't written in way too long and just wanted to post this fun little proof.
Assertion: Let Fn be the nth Fibonacci number defined by Fn=Fn−1+Fn−2, F0=0,F1=1. Show that for an odd prime p≠5, we have p divides Fp2−1.
Proof: We do this by working inside Fp instead of working in R. The recurrence is given by
(1110)(Fn−1Fn−2)=(Fn−1+Fn−2Fn−1)=(FnFn−1)
and in general
(1110)n(10)=(1110)n(F1F0)=(Fn+1Fn)
The matrix A=(1110) has characteristic polynomial
χA(t)=(1−t)(0−t)−(1)(1)=t2−t−1
If this polynomial has distinct roots, then A is diagonalizable (this is sufficient, but not necessary). Assuming the converse we have χA(t)=(t−α)2 for some α∈Fp; we can assume α∈Fp since −2α=−1 is the coefficient of t, which means α=2−1 (we are fine with this since p odd means that 2−1 exists). In order for this to be a root of χA, we must have
0≡4⋅χA(2−1)≡4⋅(2−2−2−1−1)≡1−2−4≡−5modp.
Since p≠5 is prime, this is not possible, hence we reached a contradiction and χA does not have a repeated root.
Thus we may write χA(t)=(t−α)(t−β) for α,β∈Fp2 (it's possible that χA is irreducible over Fp, but due to degree considerations it must split completely over Fp2). Using this, we may write
A=P(α00β)P−1
for some P∈GL2(Fp2) and so
Ap2−1=P(α00β)p2−1P−1=P(αp2−100βp2−1)P−1
Since χA(0)=0−0−1≠0 we know α and β are nonzero, hence αp2−1=βp2−1=1∈Fp2. Thus Ap2−1=PI2P−1=I2 and so
(FpFp2−1)=(1110)p2−1(10)=I2(10)=(10)
so we have Fp2−1=0 in Fp as desired.
