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ść.