Długość okresu rozwinięcia ułamka

Tutaj można wpisywać swoje propozycje tematów do kompendium oraz dyskutować na tematy, które później trafią do właściwego działu Kompendium.
Awatar użytkownika
JakimPL
Użytkownik
Użytkownik
Posty: 2401
Rejestracja: 25 mar 2010, o 12:15
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 43 razy
Pomógł: 459 razy

Długość okresu rozwinięcia ułamka

Post autor: JakimPL »

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

Uwaga
Ułamki typu \(\displaystyle{ 0.\overline{9}}\) zawsze będziemy utożsamiać z \(\displaystyle{ 1}\), np. liczba \(\displaystyle{ 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 \(\displaystyle{ m}\) przez liczbę \(\displaystyle{ n}\) oznaczać będziemy jako \(\displaystyle{ (m)_n}\).

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

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

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

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

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

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

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

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

By dowieść podane wyżej twierdzenie, wystarczy przyjrzeć się zwykłemu dzieleniu pisemnemu. Spróbujmy uprzednio zobaczyć na przykładzie \(\displaystyle{ \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.

\(\displaystyle{ \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 \(\displaystyle{ (x_i)}\), natomiast ciąg \(\displaystyle{ (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ą: \(\displaystyle{ x_0 = \left\lfloor\tfrac{m}{n}\right\rfloor}\), a pierwsza reszta będzie tym, co pozostało: \(\displaystyle{ y_0 = (m)_n}\). W naszym przypadku z przykładu \(\displaystyle{ x_0 = 0}\), a \(\displaystyle{ 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 \(\displaystyle{ b}\)) i dzieląc przez \(\displaystyle{ n}\):

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

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

\(\displaystyle{ y_1 = y_0 b - x_1 n.}\)

Odpowiada to odejmowaniu \(\displaystyle{ 6 = 20 - 14}\). Procedurę postępowania powtarzamy:

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

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

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

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

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

Twierdzenie
Niech \(\displaystyle{ \tfrac{m}{n}}\) będzie ułamkiem sprowadzonym do najprostszej postaci, dodatkowo niech \(\displaystyle{ 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 \(\displaystyle{ b=p_1^{\alpha_1}p_2^{\alpha_2}\cdot\ldots\cdot p_j^{\alpha_j}}\) wynosi \(\displaystyle{ 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 \(\displaystyle{ \tfrac{1}{n}}\) nie przekracza \(\displaystyle{ n-1}\).

Zacznijmy od faktu, że zbiór liczb mniejszych od \(\displaystyle{ n}\) i względnie pierwszych z \(\displaystyle{ n}\), a więc dokładnie \(\displaystyle{ \mathbb{Z}_n^*}\), ma zawsze co najwyżej \(\displaystyle{ n-1}\) elementów - a przypadek "graniczny" zachodzi wtedy i tylko wtedy, gdy \(\displaystyle{ n}\) jest liczbą pierwszą. Jest też jasne, że rząd elementu nie może być większy niż \(\displaystyle{ 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 \(\displaystyle{ 10^n-1}\), \(\displaystyle{ 11^n}\) oraz \(\displaystyle{ 3^n}\).

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

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

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

Zadanie
Udowodnij, że mianowniki ułamków o okresie długości \(\displaystyle{ 11}\) dzielą \(\displaystyle{ 21649}\) lub \(\displaystyle{ 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 \(\displaystyle{ n}\) istnieje element \(\displaystyle{ k\in\mathbb{Z}_n^*}\) o własności \(\displaystyle{ r_n(k)\geqslant n}\), a więc \(\displaystyle{ k^l\not\equiv 1\pmod n}\) dla wszystkich \(\displaystyle{ 1\leqslant l < n}\). Ponieważ możliwych reszt modulo \(\displaystyle{ n}\) jest co najwyżej \(\displaystyle{ n-1}\), z zasady szufladkowej Dirichleta istnieją dwie takie różne liczby \(\displaystyle{ l_1}\) oraz \(\displaystyle{ l_2}\), że zachodzi \(\displaystyle{ k^{l_1}\equiv k^{l_2}\pmod n}\), przyjmijmy bez straty ogólności \(\displaystyle{ l_2>l_1}\). Stąd \(\displaystyle{ k^{l_2}-k^{l_1}\equiv 0 \pmod n}\), a co za tym idzie - \(\displaystyle{ k^{l_1}\left(k^{l_2-l_1}-1\right)\equiv 0 \pmod n}\). Oczywiście \(\displaystyle{ k^{l_1}\not\equiv 0\pmod n}\), więc wbrew założeniu znaleźliśmy liczbę mniejszą od \(\displaystyle{ n}\) realizującą \(\displaystyle{ k^{l_2-l_1}\equiv 1\pmod n}\). Sprzeczność.
Ostatnio zmieniony 17 lut 2016, o 03:44 przez JakimPL, łącznie zmieniany 1 raz.
Kartezjusz
Użytkownik
Użytkownik
Posty: 7330
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 6 razy
Pomógł: 961 razy

Długość okresu rozwinięcia ułamka

Post autor: Kartezjusz »

2
Ukryta treść:    
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Długość okresu rozwinięcia ułamka

Post autor: Jakub Gurak »

Pozbieram różne twierdzenia z tego wykładu dochodząc do ciekawego wniosku:

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

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

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

Dobrze myślę??
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Długość okresu rozwinięcia ułamka

Post autor: a4karo »

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

Dobrze myślę??
Dobrze myślisz, pomijając fakt, że to podkreślone nie jest jednak udowodnione
Kartezjusz
Użytkownik
Użytkownik
Posty: 7330
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 6 razy
Pomógł: 961 razy

Długość okresu rozwinięcia ułamka

Post autor: Kartezjusz »

1. W wypadku tych liczb to chyba ich długość, chyba, że masz na myśli je jako mianowniki.
Awatar użytkownika
JakimPL
Użytkownik
Użytkownik
Posty: 2401
Rejestracja: 25 mar 2010, o 12:15
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 43 razy
Pomógł: 459 razy

Długość okresu rozwinięcia ułamka

Post autor: JakimPL »

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ąć \(\displaystyle{ 0}\) (wartość \(\displaystyle{ 1}\) również jest sensowna, ale nie odróżnia np. \(\displaystyle{ 1}\) od \(\displaystyle{ \tfrac13}\)), a dla liczb niewymiernych - \(\displaystyle{ \infty}\). Liczby całkowite będą mieć zatem zerową długość rozwinięcia okresowego.
Kartezjusz
Użytkownik
Użytkownik
Posty: 7330
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 6 razy
Pomógł: 961 razy

Długość okresu rozwinięcia ułamka

Post autor: Kartezjusz »

Ukryta treść:    
Awatar użytkownika
JakimPL
Użytkownik
Użytkownik
Posty: 2401
Rejestracja: 25 mar 2010, o 12:15
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 43 razy
Pomógł: 459 razy

Długość okresu rozwinięcia ułamka

Post autor: JakimPL »

Niby tak jest, ale wypadałoby to formalnie poprawnie zapisać: tak, żeby nie było żadnych wątpliwości .
Elayne
Użytkownik
Użytkownik
Posty: 926
Rejestracja: 24 paź 2011, o 01:24
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 75 razy
Pomógł: 274 razy

Długość okresu rozwinięcia ułamka

Post autor: Elayne »

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