Fibonacci Dizisininin $\mod p$'de Periyodu

5 beğenilme 0 beğenilmeme
382 kez görüntülendi

Fibonacci dizisi $a_0 = 0, a_1 = 1$ olmak üzere $n \geq 2$ için $a_n =a_{n-1} + a_{n-2}$ olarak tanımlanıyor. Dizinin ilk birkaç terimi $0,1,1,2,3,5,8,13,21,34,55, ..$ diye gidiyor.

Bu diziyi $p$ asal olmak üzere modulo $p$ düşünürsek ne olur?

  • $p = 2$ için: $\boxed{0,1,1},0,1,1,0,1,1,0,1,1,0,1,1,0,1,1...$
  • $p=3$ için: $\boxed{0,1,1,2,0,2,2,1},0,1,1,2,0,2,2,1,0,...$
  • $p=5$ için: $\boxed{0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1},0,1,1,2...$
  • $p = 7$ için: $\boxed{0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1},0,1,1,2,...$
  • $p= 11$ için: $\boxed{0,1,1,2,3,5,8,2,10,1},0,1,1,2,...$
Görüldüğü gibi dizi her seferinde kendini tekrar ediyor, yani periyodik bir dizi elde etmiş oluyoruz. Bunu göstermek zor değil. Şuradaki cevapta yer alan $$A = \begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}$$ matrisini $GL_2(F_p)$ (girdileri modulo $p$ sayılar olan tersinebilir matrisler grubu) içerisinde düşünürsek, bu grubun eleman sayısı sonlu olduğu için $A$'nın bir kuvvetinin birim matris olacağını söyleyebiliriz. Dolayısıyla $e_1 = (1,0)^T$ vektörüne $A$'yı sürekli uygularsak bir zaman sonra $e_1$ vektörüne geri geleceğimizi görebiliriz. Bu da bir zaman sonra dizinin tekrar $...,0,1,...$ diye devam edeceğini söylüyor. Ama dizinin elemanları sadece kendinden önceki iki elemana bağlı olduğu için $0,1$'i yakaladığımız taktirde, dizi en başa dönmüştür diyebiliriz. Tamam. Dizinin periyodik olduğunu söyledik. Peki periyodu kaçtır?

Yukarıdaki örneklere bakacak olursak:
  • $p=2$ için: Periyot $3$.
  • $p=3$ için: Periyot $8$.
  • $p=5$ için: Periyot $20$.
  • $p=7$ için: Periyot $16$.
  • $p=11$ için: Periyot $10$.
Burada nasıl bir kural var? Bildiklerimiz şöyle:
  1. $GL_2(F_p)$ grubunun eleman sayısı $(p^2 -1)(p^2 - p)$ olduğu için $A$ matrisinin derecesinin bunu bölmesi gerektiğini biliyoruz. Dolayısıyla periyot da bu sayıyı bölmeli. Örneklerde bunun tuttuğunu görebiliriz.
  2. Ama bunu geliştirmek mümkün. $A$ matrisinin karakteristik polinomu $x^2 - x- 1$. Kökleri: $$\phi_{1,2}=\frac{1 \pm \sqrt{5}}{2}$$ Yani eğer $p = 2$ ya da $p=5$ değilse iki farklı kök var. Dolayısıyla bu matrisi $$D = \begin{bmatrix} \phi_1 & 0 \\ 0 & \phi_2 \end{bmatrix}$$şeklinde köşegenleştirmek mümkün. Fakat burada dikkatli olmak lazım. $\sqrt{5}$ derken, karesi modulo $p$'de $5$ olan bir sayıdan bahsediyoruz. Ama böyle bir sayı $F_p$'nin içinde yer almak zorunda değil. Mesela $F_7$'de böyle bir sayı yok. Dolayısıyla bu $\phi_1, \phi_2$ kökleri $F_7$ içerisinde değiller. Ama minimal polinomları ikinci dereceden olduğu için kuadratik bir genişleme içindeler: $F_{p^2}$.
  3. $A$'nın derecesi ile $D$'nin derecesinin aynı olması gerektiğini lineer cebirden biliyoruz. Aynı zamanda $\phi_1$ ile $ \phi_2$ eşlenik oldukları için $F_p$'de ya da $F_{p^2}$'de aynı dereceye sahip olmaları gerektiğini biliyoruz. Dolayısıyla, $D$'nin derecesinin $\phi_1$'in derecesine eşit olması gerektiğini söyleyebiliriz. Demek ki periyodumuz, $\phi=\phi_1$'in $F_p$ içindeki (ya da $F_p$'de değilse $F_{p^2}$ içindeki -ki ilk durumda aslında ikisi de aynı-) derecesine eşit. Bu derece de $F_p$ için $p-1$'i, $F_{p^2}$ için ise $p^2 -1$'i bölmeli.
  4. Peki ne zaman $\sqrt{5}$ elemanı $F_p$ içinde yer alır. Yani, $x^2 = 5 \mod p$ denkleminin hangi asallar için kökleri vardır? Quadratic Reciprocity yasasını kullanarak, bunun ancak ve ancak $x^2 = p \mod 5$ denkleminin kökü varsa olacağını söyleyebiliriz. Ama $p \neq 5$ ise, modulo $5$'te yalnızca iki tane kare var: $1$ ve $4$. Yani, eğer $p = 1, 4 \mod 5$ ise, ya da başka deyişle $p= 1, 4, 6, 9 \mod 10$ ise (son rakam $4$ ya da $6$ olamaz çünkü $2$'den başka çift asal yok.), 
  5. Yani eğer $p$ asalının son rakamı $1$ ya da $9$ ise periyot $p-1$'i bölmeli. Diğer durumlarda ($p$'nin son rakamı $3$ ya da $7$) ise, periyot $p-1$'i bölmese bile $p^2-1$'i bölmeli.
Soru: Bizim (arkadaşlarla) bulabildiğimiz en iyi sonuç bu. Bunu geliştirmek mümkün müdür? Parentez içini iki gün sonra okuyun: (Bu soruyu 340 puan karşılığında ödüllü ilan ediyorum. Bundan daha iyi bir sonuç olmasa bile başka bir yöntem de olur.)
25, Ocak, 2017 Akademik Matematik kategorisinde Ozgur (2,145 puan) tarafından  soruldu
25, Ocak, 2017 Ozgur tarafından düzenlendi

Kural yazilmamis ama odullu soru ilan etmek icin 2 gun beklememiz gerekli. 

Tamamdır, değiştirdim. Mersi.

Bakmadan ugrasayim dedim. Ben de tam bunlari buldum, ne eksik ne fazla. :)

Untitled-1.pdf (0,1 MB)


..........................

Your browser does not have a PDF plugin installed.

Download the PDF: Untitled-1.pdf

...