Demostración de la propiedad de la secuencia de Fibonacci con la teoría de grupos

Question

Me he topado con este problema en un capítulo sobre teoría de grupos y no consigo entenderlo:

Dejemos que $p$ sea un primo y $F_1 = F _2 = 1, F_{n +2} = F_{n +1} + F_n$ sea la secuencia de Fibonacci. Demuestre que $F_{2p(p^21)}$ es divisible por $p$ .

El libro da la siguiente pista:

Mira el grupo de $2×2$ matrices mod $p$ con determinante $± 1$

Sé que tengo que usar el teorema de Lagrange en algún momento, pero ¿cómo establezco el vínculo entre la secuencia de Fibonacci y las matrices? Es decir, sé que hay una $2×2$ de tal manera que se obtenga la matriz $n^{th}$ número de fibonacci al tomar el $n^{th}$ poder, incluso lo usé para obtener una fórmula general para los números durante mi curso de álgebra lineal, pero ¿cómo puedo usar eso para demostrar esto?

Answer 1

Llama al grupo $G = \left\{A \in (\mathbb{Z}/p\mathbb{Z})^{2\times 2} \ \middle\vert\ \det A = \pm 1\right\}$ .

En primer lugar, contamos el orden de $G$ . Tenemos elementos $\left(\array{a & b \\ c & d}\right)$ con $a,b,c,d \in \mathbb{Z}/p\mathbb{Z}$ y $ad - bc \equiv \pm 1$ ( $\equiv$ significa congruente módulo $p$ ). Contemos primero los elementos con determinante uno. $\mathbb{Z}/p\mathbb{Z}$ es un campo, lo que significa que todos los elementos excepto $0$ tiene un inverso multiplicativo. Por lo tanto, $ad - bc \equiv 1$ equivale a $(d \equiv 0\ \land\ c \equiv -b^{-1})\ \lor\ (a \not\equiv 0 \land d \equiv a^{-1}(1 + bc))$ . Contando las posibilidades se obtiene $$ \underbrace{(d \equiv 0\ \land\ c \equiv -b^{-1})}_{\text{$ a $: $ p $ choices, $ b $: $ p - 1 $ choices}}\ \lor\ \underbrace{(a \not\equiv 0 \land d \equiv a^{-1}(1 + bc))}_{\text{$ a $: $ p - 1 $ choices, $ b,c $: $ p $ choices}} $$ para un total de $p(p-1) + (p-1)p^2 = p(p+1)(p-1) = p(p^2 - 1)$ elementos con determinante $1$ . Por simetría (intercambiando $a$ con $b$ y $d$ con $c$ ) tiene que haber un número igual de elementos con determinante $-1$ . Así que el orden de $G$ es $|G| = 2p(p^2 - 1)$ .

Ahora, dejemos que $M = \left(\array{1 & 1 \\ 1 & 0}\right)$ . Usted ya sabe que $M^n = \left(\array{F_{n+1} & F_{n} \\ F_{n} & F_{n-1}}\right)$ . Para $M$ como para cualquier elemento de un grupo finito, sabemos que $M^{|G|} = I$ (considere el subgrupo cíclico $\left<M\right>$ generado por $M$ y utilizar el teorema de Lagrange). Este hecho se traduce en $$ \left(\array{F_{2p(p^2 - 1) + 1} & F_{2p(p^2 - 1)} \\ F_{2p(p^2 - 1)} & F_{2p(p^2 - 1) - 1}}\right) \equiv \left(\array{1 & 0 \\ 0 & 1}\right) \mod{p}.$$ Las componentes no diagonales de esta ecuación son las que querías mostrar.

Answer 2

La matriz $\left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right]$ tiene la propiedad de que sus potencias codifican los números de Fibonacci. Vive en el grupo de $2 \times 2$ matrices $\bmod p$ con determinante $\pm 1$ (un determinado subgrupo de $GL_2(\mathbb{F}_p)$ ). Si se cuenta el tamaño de este grupo...