Fibonacci Dizisininin $\mod p$'de Periyodu

5 beğenilme 0 beğenilmeme
634 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,152 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

1 cevap

0 beğenilme 0 beğenilmeme

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.

5, Haziran, 5 Dogukan633 (859 puan) tarafından  cevaplandı

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.

...