Dzielenie pisemne. Rozwijanie liczb wymiernych na ułamki okresowe cz. I

Ponownie poruszamy tematykę liczbowych systemów pozycyjnych. Istnienie rozwinięć liczb z przedziału [0,1] zostało już wykazane we wcześniejszym wpisie. Wykorzystaliśmy do tego celu algorytm przybliżający daną liczbę od dołu, teraz skupimy się na innym sposobie wyznaczania rozwinięć. Sposobem tym jest dzielenie pisemne. Bardzo prosty w praktyce, ma jednak tę wadę, że można go zastosować jedynie do liczb wymiernych. Przyjrzymy się jego istocie, tzn. jak działa i dlaczego. Myślę, że po tylu latach edukacji w szkole każdy, kto się nad tym jeszcze nie zastanawiał powinien być zaciekawiony. Drugim celem jest omówienie ułamków okresowych i scharakteryzowanie przy ich pomocy liczb wymiernych.

Rozważania będziemy prowadzić w systemach liczbowych o dowolnej podstawie L \in \mathbb{N}_2 i będą one dotyczyły jedynie liczb wymiernych \displaystyle 0\leq \frac{p}{q} \leq 1, gdzie p,q \in \mathbb{N}, q \neq 0, chociaż jedynkę będziemy przeważnie wyrzucać dla wygody, co nie przysporzy zbyt wielu problemów, bo wiadomo z poprzednich wpisów jak ona się przedstawia w dowolnym systemie.

Zacznijmy od przykładu. Nie będę niczego dzielił pisemnie, przynajmniej nie w dokładnie takiej wersji jak w szkole, lecz w takiej, która daje wgląd jak i dlaczego w praktyce działa pisemne dzielenie. Spróbujemy wyznaczyć rozwinięcie dla liczby \frac{1}{3}.

Wykonujemy następujące przekształcenia:

\displaystyle \frac{1}{3}= \frac{10}{3}\cdot \frac{1}{10}=\frac{3 \cdot 3 + 1 }{3}\cdot \frac{1}{10}=\frac{3}{10} + \frac{1}{3} \cdot \frac{1}{10}

zatem

\displaystyle\frac{1}{3}=\frac{3}{10} + \frac{1}{3} \cdot \frac{1}{10}

i podstawiając w prawej stronie za \frac{1}{3} otrzymaną równość mamy

\displaystyle \frac{1}{3}=\frac{3}{10}+(\frac{3}{10} + \frac{1}{3} \cdot \frac{1}{10})\cdot \frac{1}{10}=\frac{3}{10}+\frac{3}{10^2}+\frac{1}{3}\cdot \frac{1}{10^2}

Możemy postępować tak w nieskończoność, więc domyślamy się, że

\displaystyle \frac{1}{3}=0,3333\dots

Zresztą jest to fakt znany każdemu użytkownikowi kalkulatora. Choć trzeba przyznać, że przeciętny użytkownik kalkulatora nie może mieć pewności czy po pewnej ilości trójek nie pojawi się coś innego. W dalszej części zobaczymy, że da się to sprawdzić nie wykonując nieskończonej ilości obliczeń. Nasz przykład ilustruje po pierwsze jak działa dzielenie pisemne po drugie coś, co będziemy za chwilę nazywali ułamkiem okresowym.

Definicja.

Ogólnie gdy mamy pewną liczbę rozwiniętą w ciąg cyfr \{c_n\}_{n=1}^\infty w systemie o podstawie L

x=0,c_1c_2c_3c_4\dots

to nazwiemy ją ułamkiem okresowym, gdy od pewnego momentu będzie powtarzał się pewien skończony ciąg cyfr. Ściślej rzecz biorąc gdy istnieją takie n_0, T \in \mathbb{N}_1 , że

\displaystyle (c_{n_0}, c_{n_0+1}, \dots, c_{n_0+T-1})= (c_{n_0+kT}, c_{n_0+kT+1}, \dots, c_{n_0+kT+T-1})

dla każdego k naturalnego.

Obrazowo chodzi o to, że

x=0,c_1c_2 \dots c_{n_0-1} d_1 d_2 \dots d_T d_1 d_2 \dots d_T \dots

gdzie (c_{n_0}, c_{n_0+1}, \dots, c_{n_0+T-1})=(d_1, d_2, \dots d_T)

Powszechnie stosuje się oznaczenie

x=0,c_1c_2 \dots c_{n_0-1} (d_1 d_2 \dots d_T)

wtedy też ciąg d_1 d_2 \dots d_T nazwiemy okresem.

Jest to definicja jedynie dla potrzeb teoretycznych. Dlatego pozwoliłem sobie przyjąć pewną, być może dziwaczną, konwencję. Nie wykluczyłem sytuacji gdy okresem jest ciąg zer, to znaczy gdy

x=0,c_1c_2 \dots c_{n_0-1} 000 \dots

Dla wygody liczby tej postaci będziemy wrzucać  do tego samego worka, co ułamki okresowe, tylko dla odróżnienia będziemy je nazywać ułamkami skończonymi.

Dodatkowo, np. dla liczby 0,123123123\dots okresem jest zarówno (123) jak i (123123) lub też (123123123) itd. W praktyce za okres uważa się ten możliwe najkrótszy ciąg, który się powtarza, ale nie będziemy sobie tym zawracać głowy, bo gdy już jakiś znajdziemy to i znajdziemy najkrótszy. Zwróćmy uwagę jeszcze na jeden aspekt definicji. Jak wiemy, niektóre liczby posiadają dwa rozwinięcia, ale w tym wypadku oba są okresowe, gdyż jedno jest ułamkiem skończonym, a drugie ma cyfrę L-1 w okresie. Dlatego, mimo że definicja nazywa liczbę ułamkiem okresowym, gdy istnieje rozwinięcie okresowe, to w rzeczywistości mamy, że liczba jest ułamkiem okresowym, gdy każde jej rozwinięcie jest okresowe. W związku z tym definicja ma sens, bo albo dana liczba jest okresowa albo nie.

Rozważmy teraz kolejny przykład, gdyż poprzednio znalezienie okresu przyszło zbyt łatwo i niewiele można było zaobserwować. Zastosujemy podobną procedurę do liczby \frac{41}{333}.

Zaczynamy od domnożenia licznika i mianownika przez 10 (podstawę systemu), a następnie podzielenie z resztą domnożonego licznika przez mianownik

\displaystyle \frac{41}{333}=\frac{410}{333}\cdot \frac{1}{10}=\frac{1\cdot333+77}{333}\cdot \frac{1}{10}=\frac{1}{10}+\frac{77}{333}\cdot \frac{1}{10}

To samo wykonujemy dla liczby \frac{77}{333}

\displaystyle \frac{77}{333}=\frac{770}{333}\cdot \frac{1}{10}=\frac{2\cdot333+104}{333}\cdot \frac{1}{10}=\frac{2}{10}+\frac{104}{333}\cdot \frac{1}{10}

A następnie dla liczby \frac{104}{333}

\displaystyle \frac{104}{333}=\frac{1040}{333}\cdot \frac{1}{10}=\frac{3\cdot333+41}{333}\cdot \frac{1}{10}=\frac{3}{10}+\frac{41}{333}\cdot \frac{1}{10}

i widzimy, że historia zaczyna się powtarzać. Przerywamy w tym momencie.

Podstawiając teraz otrzymane wartości dostajemy, że

\displaystyle \frac{41}{333}=\frac{1}{10}+\frac{77}{333}\cdot \frac{1}{10}=\frac{1}{10}+(\frac{2}{10}+\frac{104}{333}\cdot \frac{1}{10})\cdot \frac{1}{10}=\frac{1}{10}+\frac{2}{10^2}+\frac{104}{333}\cdot\frac{1}{10^2}=

\displaystyle =\frac{1}{10}+\frac{2}{100}+(\frac{3}{10}+\frac{41}{333}\cdot \frac{1}{10})\cdot\frac{1}{100}=\frac{1}{10}+\frac{2}{10^2}+\frac{3}{10^3}+\frac{41}{333}\cdot\frac{1}{10^3}.

Zatem

\displaystyle \frac{41}{333}=\frac{1}{10}+\frac{2}{10^2}+\frac{3}{10^3}+\frac{41}{333}\cdot\frac{1}{10^3}.

Widać, że podstawiając w prawej stronie za \frac{41}{333} otrzymaną równość, będziemy dostawać wciąż te same cyfry. Stąd mamy

\displaystyle \frac{41}{333}=0,(123).

Mamy teraz pewien już dosyć dobry wgląd jak działa dzielenie pisemne. Postaramy się więc sformalizować całą sprawę.

Mamy daną liczbę wymierną \frac{p}{q} \in [0,1) oraz podstawę systemu L. Definiujemy rekurencyjnie następujący ciąg

r_0=p

oraz

r_{n+1}=r_q(r_nL)

gdzie r_q jest resztą z dzielenia przez q liczby w nawiasach.

Teraz nasz kandydat na rozwinięcie liczby \frac{p}{q} definiujemy wzorem c_n:=d_q(r_{n-1}L) dla każdego naturalnego n począwszy od jedynki (d_q to wynik dzielenia całkowitego przy dzieleniu z resztą przez q liczby w nawiasach).

Uzyskanie ciągów \{ r_n \}_{n=0}^\infty i \{ c_n \}_{n=1}^\infty przy danym ilorazie \frac{p}{q} będziemy nazywali podzieleniem pisemnym liczby p przez q. Krótko będziemy mówić o dzieleniu pisemnym \frac{p}{q}.

Rozpiszmy pierwszy krok naszej procedury dla lepszego zrozumienia powyższych definicji

\displaystyle \frac{p}{q}=\frac{r_0}{q}=\frac{r_0L}{q}\cdot\frac{1}{L}=\frac{d_q(r_{0}L)q+r_q(r_0L)}{q}\cdot\frac{1}{L}=\frac{c_1q+r_1}{q}\cdot\frac{1}{L}=\frac{c_1}{L}+\frac{r_1}{q}\cdot\frac{1}{L}=\frac{c_1}{L}+\frac{r_1L}{q}\cdot\frac{1}{L^2}=\dots

Ponieważ ciąg \{c_n\}_{n=1}^\infty bierze się z wyników dzielenia, nie jest więc takie oczywiste, że to jest ciąg cyfr. Musimy zatem sprawdzić czy w ogóle 0 \leq c_n < L. Nieujemność c_n jest oczywista zajmiemy się drugą nierównością.

Zauważmy, że r_n<q, ponieważ r_0=p<q (dlatego wyrzucamy 1 z rozważań, choć można by i z nią sobie poradzić) a pozostałe wyrazy są resztami z dzielenia przez q.

Z definicji

r_{n-1}L=d_q(r_{n-1}L)q+r_q(r_{n-1}L)=c_nq+r_n

dzięki wcześniejszej uwadze i nierówności L>1

c_nq+r_n=r_{n-1}L<qL

a stąd

c_nq<qL, więc też c_n<L.

Pokażemy teraz kolejną własność ciągów \{c_n\}_{n=1}^\infty i \{r_n\}_{n=0}^\infty.

Twierdzenie.

Dla n=1,2,3\dots zachodzi równość

\displaystyle \frac{p}{q}=\sum_{k=1}^n \frac{c_k}{L^k} + \frac{r_n}{qL^n}.

Dowód.

Dowiedziemy ją bardzo prosto przez indukcję.

Dla n=1 wykonaliśmy wyliczenia obrazując definicję. Wyszło nam, że

\displaystyle \frac{p}{q}=\frac{c_1}{L}+\frac{r_1}{q}\cdot\frac{1}{L}.

Załóżmy więc teraz, że

\displaystyle \frac{p}{q}=\sum_{k=1}^n \frac{c_k}{L^k} + \frac{r_n}{qL^n}.

Z definicji mamy

r_nL=d_q(r_n L)q+r_q(r_nL)=c_{n+1}q+r_{n+1}

Zatem

\displaystyle \frac{r_n}{qL^n}= \frac{r_nL}{qL^{n+1}}=\frac{c_{n+1}q+r_{n+1}}{qL^{n+1}}=\frac{c_{n+1}}{L^{n+1}}+\frac{r_{n+1}}{qL^{n+1}}

A stąd wprost dostajemy, że

\displaystyle \frac{p}{q}=\sum_{k=1}^{n+1} \frac{c_k}{L^k} + \frac{r_{n+1}}{qL^{n+1}}.

Wniosek.

\displaystyle \frac{p}{q}=\sum_{n=1}^\infty \frac{c_n}{L^n}

Dowód.

Wystarczy zauważyć, że

\displaystyle 0 \leq \frac{p}{q} - \sum_{k=1}^n \frac{c_k}{L^k} = \frac{r_n}{qL^n} < \frac{q}{qL^n}= \frac{1}{L^n} \to0

gdy n \to \infty.

Zatem dzielenie pisemne istotnie działa i nie było to takie trudne do wykazania. :) Możemy, więc z czystym sumieniem powiedzieć, że liczba 0,c_1c_2c_3\dots jest wynikiem dzielenia pisemnego liczby p przez q.

W części II skupimy się na zagadnieniu charakteryzacji liczb wymiernych przy pomocy ułamków okresowych, jednak nie zostawimy dzielenia pisemnego.

Advertisements

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s