Fibonacci Dizisininin $\mod p$'de Periyodu

Question

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.)

Comments

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)

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

Download the PDF: Untitled-1.pdf

Answer 1

Herhangi bir $m$ bileşik sayısı için de devirlidir. Ve $p$ wieferich asalı olmayan bir asal sayı olmak üzere, mod $p$ deki periyoda $d(p)$ dersek, her $k$ pozitif tamsayısı için

                                                                   $d(p^k)=p^{k-1}.d(p)$

eşitliği mevcuttur. Aslında bu çok güçlü bir ifade değil. Elementer yöntemlerle ispatlanabilir.

Herhangi bir $p$ asal sayısı için devir uzunluğunu hesaplamak gerçekten güç bir iş. Çünkü herhangi bir $A$ matrisi için $GL_{2}(F{p})$ grubu içerisinde

                                                                        $A^n = I$

eşitliğini sağlayan "en küçük $n$" yi bulmak gerçekten çok zor. Bunun benzeri ile ilgili çok çalışıldı. Örneğin $Z_{p}$ grubu için,

                                                                         $a^n = 1$

eşitliğini sağlayan "en küçük $n$" yi bulmak da çok zor. Ben uzun zamandır düşünürüm bu soruyu. En net sonuç Carmichael in sonucudur. Carmicheal'in bulduğu üs her zaman en küçük olmaz. Her $a$ için en küçüğünü verir ! Ve o üs

                                                            $n= [(p_{i}-1)p^{a_{i}-1}]_{i}$

Burada $p_{i}$ ler $n$ nin asal çarpanları, $a_{i}$ ler kuvvetler, her $i$ için yazıp $ekok$ alıyoruz.

Bizim işimiz belli bir $a$ sayısı için tabi.

İşin ilginç yanı $n=p^k$ iken

                                                                 $n=(p-1)p^{k-1}$

olur. Bu en küçük üs mü ? HAYIR. Ancak $p-1$ yerine $d'(p)$ alırsak , ($modp$ de en küçük üs)

                                                                  $n=d'(p).p^{k-1}$

elde ederiz ki bu en küçük üs mü ? EVET. Hatta bu eşitlik wieferich asalı olmayan $p$ ler için geçerli !

Görüldüğü gibi gruplar arası böyle benzerlik var. Aradaki ilişkiler kurularak yeni sonuçlar çıkarılabilir. Ancak kesin bir formül elde edemeyiz. Çok zor şu anki matematikle. Ama yeni sonuçlar bulunabilir. $(a/p)$ legendre sembolü olmak üzere,

                                                                    $(a/p) = a^{p-1/2}$

olduğundan, en küçük üssü $p-1$ "olma ihtimali yüksek olan" $a$ sayıları bulunabiliyor. Bunlar $40k+m$ tipinde. Matrislere uyarlanabilirse, periyot uzunluğu hakkında bilgi alabiliriz.

Comments

Her bilesik sayi icin devirli oldugunu nasil gosterebiliriz?

---

Yine matris grubunun eleman sayısının sonlu olmasından kaynaklanıyor. $GL_{2}(F{p})$ nin eleman sayısını bulurken, olabilecek tüm $p^4$ tane matristen determinantı $p$ ile bölünen matrisleri çıkarırız. Yani

                                                          $ad-bc \equiv 0 (mod p)$

olacak biçimde tüm $(a,b,c,d)$ dörtlülerini ararız. Bunu tablo yaparak kolayca hesaplayabilirsin. Mesela mod $7$ için çarpım tablosu yaparsan her satırda ve her sütunda her kalan $1$ kez belirir. Kolayca hesaplarsın. Hatta bunla ilgili 2010 yılında Tübitak ın sorduğu olimpiyat sorusu da vardır. Aynen bunu sormuştu. Mod 7 için sanırsam. Grubun eleman sayısını hesaplarsak,

                  $p^4 - ((2p-1)(2p-1) + (p-1)(p-1)(p-1)) = (p^2-p)(p^2-1)$

Bunu herhangi bileşik bir $m$ sayısı için de yapabiliriz. $m$ asal olmasın. $Mod m$ nin tablosu $Mod p$ nin tablosuna daha göre daha tuhaf olacaktır. Çünkü $m$ asal olmazsa sıfır bölenler var. Tablomuz çok da düzgün olmayacak. Ayrıca $ad-bc$ sayısı $m$ ile aralarında asal olmalı. Grubun eleman sayısını hesaplamak zor. Ama sonlu olduğu kesin ! O yüzden kuvvetlerden biri $I$ ya eşit.