szukanie zaawansowane
 [ Posty: 9 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 10 lut 2016, o 00:16 
Użytkownik
Avatar użytkownika

Posty: 2388
Lokalizacja: Katowice
Długość okresu rozwinięcia ułamka


W zapisie dziesiętnym ułamki liczb naturalnych postaci \tfrac{m}{n} mają rozwinięcie nieskończone okresowe, o ile tylko mianownik po sprowadzeniu ułamka do najprostszej postaci nie jest postaci 2^p\cdot 5^q. Dla przykładu \tfrac{2}{7}=0.\overline{285714} ma okres o długości sześciu cyfr (przypomnijmy, zapis 0.\overline{285714} oznacza 0.28571428571428\ldots), natomiast ułamek \tfrac{17}{110}=0.15\overline{45} ma tylko dwie cyfry w okresie.

Uwaga
Ułamki typu 0.\overline{9} zawsze będziemy utożsamiać z 1, np. liczba 0.4\overline{9}=0.5 nie będzie traktowana jako ułamek okresowy.

Okazuje się, że można jawnie wyrazić długość okresu ułamka. Przed tym wprowadzimy parę oznaczeń, którymi będziemy operować. Od Czytelnika wymagać będziemy jedynie znajomości podstaw kongruencji.

Oznaczenie
Resztę z dzielenia liczby m przez liczbę n oznaczać będziemy jako (m)_n.

Przykładowo (41)_9 =5, ponieważ 41=9\cdot 4 + \underline{5}.

Oznaczenie
Zbiór liczb naturalnych względnie pierwszych z k oraz mniejszych od k oznaczać będziemy symbolem \mathbb{Z}_k^*.

Dla przykładu \mathbb{Z}_{12}^* składa się z liczb 1, 5, 7 oraz 11 - dla pozostałych najwyższy wspólny dzielnik z 12 jest większy od 1.

By móc opisać długość okresu ułamka potrzebujemy pojęcia rzędu elementu. Dla liczby n względnie pierwszej z k możemy określić jej rząd w grupie multyplikatywnej \mathbb{Z}_k^*: jest to najmniejsza liczba naturalna l, dla której n^l \equiv 1 \pmod k. Przyjmijmy oznaczenie r_k(n)=l.

Dla wprawy obliczmy rząd 3 w grupie \mathbb{Z}_{10}^*: zachodzi 3^2 \equiv 9 \not\equiv 1\pmod{10}, 3^3 \equiv 7 \not\equiv 1\pmod{10}, ale 3^4 \equiv 1 \pmod{10}. Zatem r_{10}(3)=4. Oczywiście, możemy sprawdzić rząd r_3(10), wówczas 10 utożsamiamy z (10)_3=1. A więc r_3(10)=1.

Jesteśmy gotowi, by przystąpić do przedstawienia naszego twierdzenia.

Twierdzenie
Niech \tfrac{m}{n} będzie ułamkiem sprowadzonym do najprostszej postaci, dodatkowo niech n=k\cdot 2^p\cdot 5^q dla pewnych p,q\in\mathbb{N}_0. Wówczas długość okresu jest równy rzędowi liczby 10 w grupie multyplikatywnej \mathbb{Z}_k^*, tj. r_k(10).

Istotnie, w naszym pierwszym przykładzie r(10)=r(3)=6, ponieważ 3^6\equiv 1\pmod{7} oraz 3^l\not\equiv 1\pmod 7 dla 0<l<6, natomiast, r(11)=r(-1)=2 - z racji faktu, iż (-1)^2 = 1.

By dowieść podane wyżej twierdzenie, wystarczy przyjrzeć się zwykłemu dzieleniu pisemnemu. Spróbujmy uprzednio zobaczyć na przykładzie \tfrac{2}{7}, co się dzieje podczas dzielenia pod kreską, by móc wyabstrahować cały ten proces i podać ogólny algorytm dzielenia - co więcej nie tylko dla systemu dziesiętnego.

\begin{array}{rl}
\underline{0.285714}&\\[-2pt]
2|7\phantom{42857}&  \\[-2pt]
\underline{-0}\phantom{.142857}&\\[-2pt]
2\phantom{.}0\phantom{42857}& \text{reszta 2 z dzielenia}\\[-2pt]
\underline{-1\phantom{.}4}\phantom{42857}&\\[-2pt]
60\phantom{2857}& \text{reszta 6 z dzielenia}\\[-2pt]
\underline{-56}\phantom{2857}\\[-2pt]
40\phantom{857}& \text{reszta 4 z dzielenia}\\[-2pt]
\underline{-35}\phantom{857}\\[-2pt]
50\phantom{57}& \text{reszta 5 z dzielenia}\\[-2pt]
\underline{-49}\phantom{57}\\[-2pt]
10\phantom{7}& \text{reszta 1 z dzielenia}\\[-2pt]
\underline{-\phantom{0}7}\phantom{7}\\[-2pt]
30& \text{reszta 3 z dzielenia}\\[-2pt]
\underline{-28}&\\[-2pt]
2& \text{reszta 2 z dzielenia - powtarza się.}
\end{array}

Licząc dalej można się przekonać, że faktycznie dalsze cyfry zaczynają się powtarzać.

Spróbujmy zobaczyć, jak będzie wyglądać dzielenie pisemne w ogólnym przypadku - posiłkować będziemy się schematem powyżej, tyle że zamiast konkretnych cyfr używać będziemy symboli. Cyfry będziemy oznaczać ciągiem (x_i), natomiast ciąg (y_i) stanowić będzie ciąg kolejnych reszt występujących podczas dzielenia. Ponieważ interesuje nas część po przecinku, pierwsza "cyfra" będzie po prostu częścią ułamkową: x_0 = \left\lfloor\tfrac{m}{n}\right\rfloor, a pierwsza reszta będzie tym, co pozostało: y_0 = (m)_n. W naszym przypadku z przykładu x_0 = 0, a y_0 = 2.

Pierwszą cyfrę po przecinku możemy łatwo wyznaczyć: dopisując jedno zero do reszty (w ogólnym przypadku znaczy to przemnożenie przez b) i dzieląc przez n:

x_1 = \left\lfloor\frac{b \, y_0}{n}\right\rfloor.

Dla ułamka \tfrac{2}{7} pierwsza cyfra po przecinku wynosiła \left\lfloor\tfrac{20}{7}\right\rfloor=2. By znaleźć kolejną cyfrę, w kolejnym kroku należy obliczyć następującą różnicę:

y_1 = y_0 b - x_1 n.

Odpowiada to odejmowaniu 6 = 20 - 14. Procedurę postępowania powtarzamy:

x_i = \left\lfloor\frac{b \, y_{i-1}}{n}\right\rfloor, \quad y_i = y_{i-1} b - x_i n.

I tak właśnie wygląda algorytm dzielenia. Jak to ma się do podanego twierdzenia? Przede wszystkim wystarczy zauważyć, że y_i = \left(y_0 \, b^i\right)_n. A to już prowadzi praktycznie bezpośrednio do naszego twierdzenia. W przypadku gdy \NWD(b,n)=1, jesteśmy w domu: dla któregoś i reszta się powtórzy: y_0 \equiv y_0\, b^i\pmod n (musi, chociażby z zasady szufladkowej Dirichleta - zbiór reszt jest skończony) - a najmniejsze i różne od zera, dla którego ta kongruencja zachodzi - stanowi właśnie rząd b w grupie \mathbb{Z}_n^*. Warto nadmienić, że dla przykładu \tfrac{2}{7} reszty w rozwinięciu dziesiętnym były jednocyfrowe. W ogólnym przypadku reszty należy traktować jakby miały n cyfr (oczywiście w systemie o podstawie b).

By ustalić sytuację, gdy \NWD(b,n)>1, potrzebne jest "techniczne" obejście problemu: należy wyodrębnić z mianownika n dzielniki b, a więc dokonać rozkładu poniższej postaci:

n= k \cdot p_1^{\beta_1}p_2^{\beta_2}\cdot\ldots\cdot p_j^{\beta_j},

gdzie p_1^{\alpha_1}p_2^{\alpha_2}\cdot\ldots\cdot p_j^{\alpha_j} jest rozkładem liczby b na czynniki pierwsze. Ponieważ potęgi dzielników pierwszych liczby b nie wpływają na długość okresu (ta część techniczna zostanie pominięta), a k jest względnie pierwsze z b, można przejść z badania grupy multyplikatywnej \mathbb{Z}_n^* do grupy \mathbb{Z}_k^* i zastosować uprzednio wyprowadzony wniosek.

Tym samym udowodniliśmy szersze twierdzenie, nie tylko dla rozwinięć dziesiętnych:

Twierdzenie
Niech \tfrac{m}{n} będzie ułamkiem sprowadzonym do najprostszej postaci, dodatkowo niech n=k\cdot p_1^{\beta_1}p_2^{\beta_2}\cdot\ldots\cdot p_j^{\beta_j}. Wówczas długość okresu w rozwinięciu o podstawie b=p_1^{\alpha_1}p_2^{\alpha_2}\cdot\ldots\cdot p_j^{\alpha_j} wynosi r_k(b).

Dzięki tej wiadomości, wiemy już, że długości rozwinięć ułamków nie są bliżej nieokreślonymi koincydencjami. Co możemy wysnuć na podstawie tego twierdzenia? Przykładowo:

Wniosek
Długość okresu ułamka \tfrac{1}{n} nie przekracza n-1.

Zacznijmy od faktu, że zbiór liczb mniejszych od n i względnie pierwszych z n, a więc dokładnie \mathbb{Z}_n^*, ma zawsze co najwyżej n-1 elementów - a przypadek "graniczny" zachodzi wtedy i tylko wtedy, gdy n jest liczbą pierwszą. Jest też jasne, że rząd elementu nie może być większy niż n-1*, a to już jest równoważne z przedstawioną tezą.

Zależności wiążących postać ułamka z długością jego okresu w rozwinięciu dziesiętnym jest więcej. Chętnych wykorzystania nowo poznanej wiedzy zachęcam do rozwiązania poniższych zadań:

Zadanie
Wyznacz długość okresowego rozwinięcia dziesiętnego ułamków o mianownikach postaci 10^n-1, 11^n oraz 3^n.

Zadanie
Wykaż, że ułamek \tfrac{m}{n}, gdzie \NWD(m,n)=1, ma okres tej samej długości co \tfrac{1}{n}.

Zadanie
Sprawdź, że jedynie ułamki postaci \tfrac{m}{3}, gdzie \NWD(m,3)=1, mają okres o długości 2 w systemie dwójkowym. Dlaczego nie istnieją w tym systemie liczby o okresie długości 1?

Zadanie
Udowodnij, że jeżeli ułamek ma okres długości 2 w rozwinięciu dziesiętnym, to ma mianownik postaci 2^k \cdot 3^l \cdot 5^m gdzie l wynosi 1 albo 2.

Zadanie
Udowodnij, że mianowniki ułamków o okresie długości 11 dzielą 21649 lub 513239 (w systemie dziesiętnym).

* - bez znajomości teorii grup bądź też silniejszej wersji małego twierdzenia Fermata - twierdzenia Eulera - możemy udowodnić ten fakt formalnie. Załóżmy nie wprost, że dla liczny naturalnej n istnieje element k\in\mathbb{Z}_n^* o własności r_n(k)\geqslant n, a więc k^l\not\equiv 1\pmod n dla wszystkich 1\leqslant l < n. Ponieważ możliwych reszt modulo n jest co najwyżej n-1, z zasady szufladkowej Dirichleta istnieją dwie takie różne liczby l_1 oraz l_2, że zachodzi k^{l_1}\equiv k^{l_2}\pmod n, przyjmijmy bez straty ogólności l_2>l_1. Stąd k^{l_2}-k^{l_1}\equiv 0 \pmod n, a co za tym idzie - k^{l_1}\left(k^{l_2-l_1}-1\right)\equiv 0 \pmod n. Oczywiście k^{l_1}\not\equiv 0\pmod n, więc wbrew założeniu znaleźliśmy liczbę mniejszą od n realizującą k^{l_2-l_1}\equiv 1\pmod n. Sprzeczność.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 10 lut 2016, o 01:03 
Użytkownik

Posty: 7361
Lokalizacja: Z Bielskia-Białej
2
Ukryta treść:    
Góra
Mężczyzna Offline
PostNapisane: 16 lut 2016, o 00:27 
Użytkownik

Posty: 372
Lokalizacja: Rzeszów
Pozbieram różne twierdzenia z tego wykładu dochodząc do ciekawego wniosku:

Długość okresu ułamka \frac{m}{n} jest mniejsza od n

Jeśli bowiem \frac{m}{n} jest ułamkiem nieskracalnym to wtedy, długość okresu tego ułamka jest taka sama jak długość okresu ułamka \frac{1}{n}, która nie przekracza n-1

Pozostaje sprawdzić ułamki skracalne \frac{m}{n}
Wówczas można je skrócić przez największy wspólny dzielnik m i n otrzymując ułamek nieskracalny \frac{m _{0} }{n _{0} }
Otrzymujemy tą samą liczbę, o tym samym okresie, którego długość jest mniejsza od n_{0}, (na mocy udowodnionej już części), a więc tym bardziej jest mniejsza od n

Dobrze myślę??
Góra
Mężczyzna Offline
PostNapisane: 16 lut 2016, o 00:31 
Użytkownik

Posty: 15103
Lokalizacja: Bydgoszcz
Jakub Gurak napisał(a):
Otrzymujemy tą samą liczbę, o tym samym okresie, którego długość jest mniejsza od n_{0}, (na mocy udowodnionej już części), a więc tym bardziej jest mniejsza od n

Dobrze myślę??


Dobrze myślisz, pomijając fakt, że to podkreślone nie jest jednak udowodnione :)
Góra
Mężczyzna Offline
PostNapisane: 16 lut 2016, o 10:02 
Użytkownik

Posty: 7361
Lokalizacja: Z Bielskia-Białej
1. W wypadku tych liczb to chyba ich długość, chyba, że masz na myśli je jako mianowniki.
Góra
Mężczyzna Offline
PostNapisane: 16 lut 2016, o 12:50 
Użytkownik
Avatar użytkownika

Posty: 2388
Lokalizacja: Katowice
Tak, mianowniki, dziękuję za zwrócenie uwagi :). Niestety nie mogę już edytować wiadomości.

Przy okazji: w przypadku ułamków nieokresowych z konwencji możemy przyjąć 0 (wartość 1 również jest sensowna, ale nie odróżnia np. 1 od \tfrac13), a dla liczb niewymiernych - \infty. Liczby całkowite będą mieć zatem zerową długość rozwinięcia okresowego.
Góra
Mężczyzna Offline
PostNapisane: 16 lut 2016, o 16:46 
Użytkownik

Posty: 7361
Lokalizacja: Z Bielskia-Białej
Ukryta treść:    
Góra
Mężczyzna Offline
PostNapisane: 16 lut 2016, o 17:17 
Użytkownik
Avatar użytkownika

Posty: 2388
Lokalizacja: Katowice
Niby tak jest, ale wypadałoby to formalnie poprawnie zapisać: tak, żeby nie było żadnych wątpliwości ;).
Góra
Mężczyzna Offline
PostNapisane: 20 lut 2016, o 20:43 
Użytkownik

Posty: 649
Lokalizacja: Polska
Weźmy mianownik ułamka, rozłóżmy go na czynniki pierwsze, następnie wyłączmy czynniki 2 i 5 (jeśli są) a resztę rozszerzyć do 9 lub 99 lub 999 itd.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 9 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Długość środkowej - zadanie 5  beatka20422  1
 długość fali  dns  1
 Wyznacz kąty oraz długość trzeciego boku  typak  3
 Długość boku kwadratu - zadanie 11  ziemniak113  1
 Przedstaw w postaci ułamka zwykłego  biolga  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl