Bossy Lobster

A blog by Danny Hermes; musing on tech, mathematics, etc.

Edit on GitHub

Some Fibonacci Fun with Primes

I haven't written in way too long and just wanted to post this fun little proof.

Assertion: Let FnF_n be the nnth Fibonacci number defined by

Fn=Fn−1+Fn−2,F0=0,F1=1.F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0, F_1 = 1.

Show that for an odd prime p≠5,p \neq 5, we have pp divides Fp2−1F_{p^2 - 1}.

Proof: We do this by working inside Fp\mathbb{F}_p instead of working in R\mathbb{R}. The recurrence is given by

(1110)(Fn−1Fn−2)=(Fn−1+Fn−2Fn−1)=(FnFn−1)\left(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} F_{n-1} \\ F_{n-2} \end{array} \right) = \left(\begin{array}{c} F_{n-1} + F_{n-2} \\ F_{n-1} \end{array} \right) = \left(\begin{array}{c} F_n \\ F_{n-1} \end{array} \right)

and in general

(1110)n(10)=(1110)n(F1F0)=(Fn+1Fn)\left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)^{n} \left( \begin{array}{c} 1 \\ 0 \end{array} \right) = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)^{n} \left( \begin{array}{c} F_1 \\ F_0 \end{array} \right) = \left(\begin{array}{c} F_{n + 1} \\ F_n \end{array} \right)

The matrix

A=(1110)A = \left(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)

has characteristic polynomial

χA(t)=(1−t)(0−t)−(1)(1)=t2−t−1\chi_A(t) = (1 - t)(0 - t) - (1)(1) = t^2 - t - 1

If this polynomial has distinct roots, then AA is diagonalizable (this is sufficient, but not necessary). Assuming the converse we have χA(t)=(t−α)2\chi_A(t) = (t - \alpha)^2 for some α∈Fp\alpha \in \mathbb{F}_p; we can assume α∈Fp\alpha \in \mathbb{F}_p since −2α=−1-2\alpha = -1 is the coefficient of t,t, which means α=2−1\alpha = 2^{-1} (we are fine with this since pp odd means that 2−12^{-1} exists). In order for this to be a root of χA,\chi_A, we must have

0≡4⋅χA(2−1)≡4⋅(2−2−2−1−1)≡1−2−4≡−5 mod p.\begin{aligned} 0 \equiv 4 \cdot \chi_A\left(2^{-1}\right) &\equiv 4 \cdot \left(2^{-2} - 2^{-1} - 1\right) \\ &\equiv 1 - 2 - 4 \equiv -5 \bmod{p}. \end{aligned}

Since p≠5p \neq 5 is prime, this is not possible, hence we reached a contradiction and χA\chi_A does not have a repeated root.

Thus we may write χA(t)=(t−α)(t−β)\chi_A(t) = (t - \alpha)(t - \beta) for α,β∈Fp2\alpha, \beta \in \mathbb{F}_{p^2} (it's possible that χA\chi_A is irreducible over Fp,\mathbb{F}_p, but due to degree considerations it must split completely over Fp2\mathbb{F}_{p^2}. Using this, we may write

A=P(α00β)P−1A = P \left(\begin{array}{cc} \alpha & 0 \\ 0 & \beta \end{array} \right) P^{-1}

for some P∈GL2(Fp2)P \in GL_{2} \left(\mathbb{F}_{p^2}\right) and so

Ap2−1=P(α00β)p2−1P−1=P(αp2−100βp2−1)P−1A^{p^2 - 1} = P \left(\begin{array}{cc} \alpha & 0 \\ 0 & \beta \end{array} \right)^{p^2 - 1} P^{-1} = P \left(\begin{array}{cc} \alpha^{p^2 - 1} & 0 \\ 0 & \beta^{p^2 - 1} \end{array} \right)P^{-1}

Since χA(0)=0−0−1≠0\chi_A(0) = 0 - 0 - 1 \neq 0 we know α\alpha and β\beta are nonzero, hence αp2−1=βp2−1=1∈Fp2\alpha^{p^2 - 1} = \beta^{p^2 - 1} = 1 \in \mathbb{F}_{p^2}. Thus Ap2−1=PI2P−1=I2A^{p^2 - 1} = P I_2 P^{-1} = I_2 and so

(FpFp2−1)=(1110)p2−1(10)=I2(10)=(10)\left(\begin{array}{c} F_p \\ F_{p^2 - 1} \end{array} \right) = \left(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)^{p^2 - 1} \left(\begin{array}{c} 1 \\ 0 \end{array} \right) = I_2 \left( \begin{array}{c} 1 \\ 0 \end{array} \right) = \left( \begin{array}{c} 1 \\ 0 \end{array} \right)

so we have Fp2−1=0F_{p^2 - 1} = 0 in Fp\mathbb{F}_p as desired.

Comments