$\frac pq$ kesrinin ($p,q\in\mathbb{N},\ p,q>0$aralarında asal) bir tabana göre açılımının periyodunun tabana göre değiştiğini gösterin ve periyot için tabandan bağımsız bir üst sınır bulun.

Question

$\frac pq$ kesrinin ($p,q\in\mathbb{N},\ p,q>0$ aralarında asal) bir tabana göre açılımının periyodunun, tabana göre değiştiğini (bir örnekle) gösterin ve periyot için tabandan bağımsız bir ($p$ ve/veya $q$ ya bağlı) üst sınır bulun.

Answer 1

ilk olarak: sayinin tam kismini atip $0 \leq p < q$ oldugunu kabul edelim. 

ikinci olarak: $(10,q)=1$ kabul edelim, degise o kismi yok edelim. Ornegin $\frac pq=\frac2{45}$ ise $\frac pq=\frac 1{10}(\frac49)$ olarak yazip, artik islemimize $\frac 49$ ile devam edelim. Cunku $\frac 1{10}$ demek sadece otelemek demek.

Eger surekli bu iki islemi yaparsak ve $q=1$ gelirse (yukaridaki ornekten yola cikarak) sayimiz devirli olmaz ve eger $q \ne 1$ ise $q$ sayisi bir adet $10^n-1$ sayisini boler ve en kucuk $n$ sayisi bize devir periyodunu verir. 

Ornek olarak: $\frac{206}{165}$'yi inceleyelim. 

1) $\frac {206}{165}=1+\frac{41}{165}$,
2) $\frac{41}{165}=\frac{1}{10}\frac{82}{33}$,
1)$\frac{82}{33}=2+\frac{16}{33}$,
Son: $\frac{16}{33}=\frac{48}{99}$.

Yani: $\frac {206}{165}=1+\frac{41}{165}=1+\frac{1}{10}\frac{82}{33}=1+\frac{1}{10}(2+\frac{16}{33})=1+\frac{2}{10}+\frac{48}{990}=1,248484848\cdots$.


Eger tabanimiz $10$ degil ise ayni islem gecerli. $(taban,q)=1$ yapmaya calizacaz ve bir adet $taban^n-1$'i boldugunu soyleyecez. (asagidaki ilgili soruya bakilabilir bunun icin.)

Comments

Ek olarak da ilgili soruya bakarsaniz ust sinirin $q-1$ oldugunu gorursunuz.

Answer 2

Bir düzeltme: Aşağıdaki  çözüm (taban $m$ olsun) $m>q$ için geçerli.

Sercan ın cevabı güzel ama,  ben  basit bir mantıkla da yapılabileceğini göstermek istedim.

Bunu yıllar önce Matematik Dünyası Dergisinde okuduğumu sanıyorum arşivi taradım ama bulamadım.

Cevap  kolay ve basit:  uzun bölmeyi ve Çekmece Çorap İlkesini (Dirichlet nin İlkesi) kullanıyoruz . 

Bir $p$ (pozitif) tamsayısını bir $q$ pozitif tamsayısına nasıl böldüğümüzü hatırlayalım.  $p$ nin basamakları tüketilip, kalan 0 değilse kalanın sağına  ("yeterince"yi siliyoruz) tek bir 0  ekleyip $q$ dan büyük bir sayı oluşturulur ve bu sayıdan $q$ nun en büyük katı çıkarılıp kalan elde edilir (bu işlem hangi basamak kullanılırsa kullanılsın aynıdır). Bölme algoritmasından dolayı kalan $q$ dan küçüktür. (Kalan 0 ise bölme bitmiştir, bölüm sonlu bir kesirdir. Bu durumla ilgilenmiyoruz) Ve aynı işlemi bu yeni sayı ile yeniden yapıyoruz. Ama, Çekmece çorap İlkesinden,   (0 kalan durumu olmadığını varsayıldığından) $q-1$ tane değişik kalan olabileceğinden, (devirli ise) en çok $q$ adımda daha önceki kalanlardan biri tekrara karşımıza çıkacak ve bundan sonra işlem aynı şekilde tekrar edecektir. Bu söylenenler HER TABANDA geçerlidir. Sonuç: $\frac pq$ kesri,  $q$ dan büyük bir tabanda  (o tabanda devirli ise) periyodu en çok $q-1$ dir .

Comments

Aslinda son kisimdaki yorum ve ilgili soru (ve cevabi) ayni ust siniri vermisti. Soyledigi $(p,q)=1$ ise en az bir $1\leq n \leq q-1$ icin $p|q^{n}-1$. Aslinda aynisi degil mi?

ilgili sorudaki cevabima da bakabilirsiniz. Ben ilgili soruyu sorunca ust sinir bu demeyi unutmusum...  

---

Galiba Sercan da vermiş bu cevabı. Benim gözümden kaçmış.

---

Önceki Çözüme Ek: 

(Taban $m$) $m<q$ ise iş bu kadar basit değil, çünki kalanın yanına tek bir 0 yazmak yetmeyebilir o durumda bölüme de 0 yazıldığını (ben unutmuşum) hatırlamak gerekiyor. Bölüm kısmına yazılacak sıfırların sayısının  $\lfloor\log_m\frac qk\rfloor$ dur ($\lfloor\ \rfloor$: tam değer, $k$: kalan) Öyleyse en çok $$\sum_{k=1}^{\lfloor\frac qm\rfloor}\lfloor\log_m\frac qk\rfloor$$ tane 0 (bölüm kısmına) yazılmış olabilir. O zaman periyot en çok  $q-1+\sum_{k=1}^{\lfloor\frac qm\rfloor}\lfloor\log_m\frac qk\rfloor$ olacaktır. Bu sayı büyük bir olasılıkla en küçük üst sınır değil ama kolay ulaşılıyor. Bu arada aynı sayı (benzer nedenle) virgülden soraki devretmeyen kısmın uzunluğu için de bir üst sınır oluyor sanırım. Bu sayılara   tabandan bağımsız bir üst sınır bulabiliriz 

Answer 3

Bu soruyu cevaplayabilmek için bir koşula ihtiyacımız var. Bu koşul ise, çalışacağımız taban $a$ ise $(a,q)=1$ olması gerektiğidir. Neden böyle bir koşula ihtiyacımız var ? Öncelikle periyod uzunluğuna $d$ diyelim. Biliyoruz ki $d$ tane bölme adımından sonra tekrardan $p$ kalanını elde ederiz. Periyodun kendisine $P$ dersek bunu,

                                                                      $p.a^d = P.q+p$

şeklinde yazabiliriz.

                                                                     $p(a^d-1)=P.q$

$p$ ve $q$ aralarında asal olduğundan

                                                                      $a^d \equiv 1 (mod q)$

olacaktır. Buradaki $d$ sayısı özel bir sayısıdır. Bu mümkün olan en küçük üstür. Zira $a^x \equiv 1 (mod q)$ denkliğini sağlayan pek çok sayı var. Eğer $a$ ve $q$ aralarında asal olmazsa, bu denkliği sağlayan $x$ sayıları var olmayabilir. Bu denkliği sağlayan sayılardan birininde $\phi(q)$ olduğunu biliyoruz. Buradan rahatlıkla $d\leq \phi(q)$ diyebiliriz. Yani $(a,q)=1$ olmak şartıyla $a$ tabanında $p/q$ rasyonel sayısının devir uzunluğu en fazla $\phi(q)$ olur. Grup teorisinden biliyoruz ki $a$ tabanında

                                                                      $a^d \equiv 1 (mod q)$

denkliğini sağlayan en küçük sayı $d$ ise $a^k \equiv (mod q)$ tabanında bu sayı $d/(k,d)$ olacaktır. Tabanlar arası devir uzunluğunun değiştiğini de bu şekilde göstermiş olduk.

                                                                     

Comments

modu göstermek için a\equiv b \pmod{c} yazabilirsin, parantezsiz versiyonu için direk \mod{c} oluyor.