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

Zajmiemy się teraz charakteryzacją liczb wymiernych. Dosyć oczywiste jest, że każdy ułamek okresowy jest liczbą wymierną, ale na pierwszy rzut oka właściwie czemu na przykład liczba

0,101001000100001000001\dots

nie miałby być wymierna? Jej rozwinięcie zachowuje się bardzo regularnie.

Okaże się, że nie jest i to niezależnie od tego w jakim systemie liczbowym ją widzimy.

Wymierność różnych ułamków okresowych dowodzi się metodami szkolnymi najczęściej w następujący sposób. Dana jest liczba np. x=0,(9) w związku z tym 10x=9,(9) a stąd po odjęciu stronami 9x=9, więc x=1. Metoda ta jest wygodna i będziemy chcieli ją zastosować w ogólnej sytuacji. Przyjrzyjmy się dlaczego można ją stosować.

Mając dowolną liczbę rzeczywistą x możemy ją przedstawić jako sumę części całkowitej i ułamkowej, a każdą z tych części przedstawić w systemie liczbowym o podstawie L. Zatem

x=[x]+\{x\}=c_N\dots c_1c_0 + 0,d_1d_2\dots

co będziemy po prostu oznaczali

x=c_N\dots c_1c_0,d_1d_2\dots.

Części ułamkowe są sumami pewnych zbieżnych szeregów, a dla zbieżnych szeregów oczywiście zachodzi

\displaystyle \alpha \sum_{n=0}^\infty a_n+\beta \sum_{n=0}^\infty b_n=\sum_{n=0}^\infty (\alpha a_n+\beta b_n)

dla dowolnych \alpha,\beta \in \mathbb{R}.

Jeszcze uwaga odnośnie przesuwania przecinka.

Mając liczbę

\displaystyle x=c_N\dots c_1c_0,d_1d_2\dots=c_NL^N+\dots+c_1L+c_0+\frac{d_1}{L}+\frac{d_2}{L^2}\dots

zgodnie z działaniami na szeregach mamy

\displaystyle xL=c_NL^{N+1}+\dots+c_1L^2+c_0L+d_1+\frac{d_2}{L} + \dots= c_N \dots c_1 c_0 d_1,d_2\dots

\displaystyle xL^{-1}=c_NL^{N-1}+\dots+c_1+\frac{c_0}{L}+\frac{d_1}{L^2}+\frac{d_2}{L^3} + \dots= c_N \dots c_1, c_0 d_1d_2\dots

a zatem

\displaystyle xL^k= c_N \dots c_1 c_0 d_1\dots d_k,d_{k+1}d_{k+2}\dots

\displaystyle xL^{-k}= \dots c_k, c_{k-1} \dots c_0 d_1d_2\dots

dla k \in \mathbb{N} (pamiętając, że „po lewej” mamy do dyspozycji nieskończenie wiele zer).

Twierdzenie 1.

Jeśli x jest ułamkiem okresowym, to x\in [0,1] \cap \mathbb{Q}.

Dowód.

Korzystając z powyższych uwag i oznaczeń wykażemy, że dowolny ułamek okresowy jest liczbą wymierną. Oczywiście każdy ułamek skończony jest liczbą wymierną, gdyż jest skończoną sumą liczb wymiernych.

Dana niech będzie liczba postaci (w systemie o dowolnej podstawie L)

\displaystyle x=0,c_1c_2\dots c_N(d_1d_2 \dots d_T).

Wtedy

\displaystyle xL^N=c_1c_2\dots c_N,(d_1d_2 \dots d_T),

\displaystyle xL^{N+T}=c_1c_2\dots c_Nd_1d_2 \dots d_T,(d_1d_2 \dots d_T).

Przekształcenia te spowodowały, że w obu powyższych liczbach po przecinku mamy od razu okres.

Wystarczy więc zauważyć, że odejmując stronami wyrugują się okresy

\displaystyle xL^{T+N}-xL^N=c_1c_2\dots c_Nd_1d_2 \dots d_T,(d_1d_2 \dots d_T) -c_1c_2\dots c_N,(d_1d_2 \dots d_T)=c_1c_2\dots c_Nd_1d_2 \dots d_T-c_1c_2\dots c_N

a dalej, że

\displaystyle x=\frac{c_1c_2\dots c_Nd_1d_2 \dots d_T-c_1c_2\dots c_N}{L^N(L^T-1)}

Stąd x jest liczbą wymierną.

Zajmiemy się teraz częścią bardziej problematyczną. Będziemy chcieli wykazać, że dowolna liczba wymierna \frac{p}{q} \in [0,1] jest ułamkiem okresowym. O jedynce wiemy już, że 1=0,(L-1), zatem odkładamy ją na bok i będziemy mogli stosować algorytm dzielenia pisemnego. Dzięki jego własnościom otrzymamy okresowość liczb wymiernych.

Lemat.

Dana niech będzie liczba \frac{p}{q} oraz ciąg \{r_n\}_{n=0}^\infty wynikający z algorytmu dzielenia pisemnego. Weźmy dowolne k naturalne i oznaczmy przez \{r'_n\}_{n=0}^\infty ciąg reszt wynikający z dzielenia pisemnego r_k przez q.

Wtedy

r_{n+k}=r'_n dla n \in \mathbb{N}.

Dowód.

Indukcyjnie. Dla n=0 z definicji r'_0=r_k. Teraz jeśli r_{n+k}=r'_n to mamy też, że

r_{n+k}L=r'_nL

Z definicji po podzieleniu z resztą przez q otrzymamy

r_{n+k+1}+qd_q(r_{n+k}L)=r_{n+k}L=r'_nL=qd_q(r'_nL)+r'_{n+1}

Więc z jednoznaczności reszt

r_{n+k+1}=r'_{n+1}.

Ponieważ definicja ułamka okresowego była w poprzednim wpisie, przypomnimy teraz jej najważniejszą część (zamieniając równoważnie indeksy).

Definicja.

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

nazwiemy ją ułamkiem okresowym, gdy istnieją takie liczby naturalne n_0, T, T\geq 1, że

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

dla każdego k naturalnego.

Twierdzenie 2.

Dowolne dzielenie pisemne \frac{p}{q} od pewnego momentu się zapętla. Uściślijmy: to znaczy gdy dane są ciągi reszt \{r_n\}_{n=0}^\infty oraz cyfr \{c_n\}_{n=1}^\infty, to istnieją takie n_0, T \in \mathbb{N}, przy czym T>0, że

dla dowolnego k \in \mathbb{N}

  1. (r_{n_0}, r_{n_0+1},\dots, r_{n_0+T-1})=(r_{n_0+kT}, r_{n_0+1+kT},\dots, r_{n_0+T-1+kT})
  2. (c_{n_0+1}, c_{n_0+2},\dots, c_{n_0+T})=(c_{n_0 +1+kT}, c_{n_0+2+kT},\dots, c_{n_0+T+kT}).

Dowód.

Zastosujmy dzielenie pisemne liczby p przez q. Otrzymujemy ciągi reszt \{r_n\}_{n=0}^\infty oraz cyfr \{c_n\}_{n=1}^\infty. Oczywiście ciąg reszt ma skończony zbiór wartości, więc istnieją takie n_1<n_2 \in \mathbb{N}, że r_{n_1}=r_{n_2}. Naszym kandydatem na n_0 będzie n_1 a w rolę T wcieli się n_2-n_1.

Aby dowieść części pierwszej poprowadzimy indukcję ze względu na k.

Dla k=0 jest oczywiste. Sprawdźmy jeszcze dla k=1. Nie jest to konieczne, ale pozwoli lepiej wczuć się w ideę rozumowania. Mamy ilorazy \frac{r_{n_1}}{q} oraz \frac{r_{n_2}}{q} i wyznaczamy dla nich odpowiednio ciągi reszt \{r'_n\}_{n=0}^\infty i \{r''_n\}_{n=0}^\infty wynikające z zastosowania dzielenia pisemnego. Na podstawie Lematu mamy

r_{n+n_1}=r'_n,

r_{n+n_2}=r''_n.

Ale liczby \frac{r_{n_1}}{q},\frac{r_{n_2}}{q} są identyczne, więc r'_n=r''_n. Stąd otrzymujemy, że

r_{n+n_1}=r_{n+n_2} dla dowolnego n.

Mamy zatem w szczególności dla n=0

r_{n_1}=r_{n_2}=r_{n_1+T}, gdyż n_2=n_1+n_2-n_1=n_1+T

dla n=1

r_{n_1+1}=r_{n_1+1+T}

\vdots

i dla n=T-1

r_{n_1+T-1}=r_{n_1+T-1+T}

Pokazaliśmy dokładnie, że

(r_{n_1}, r_{n_1+1},\dots, r_{n_1+T-1})=(r_{n_1+T}, r_{n_1+1+T},\dots, r_{n_1+T-1+T}).

Mam nadzieję też, że widać, że moglibyśmy powtórzyć rozumowanie, aby uzyskać, że kolejna „partia” reszt też jest ciągiem (r_{n_1}, r_{n_1+1},\dots, r_{n_1+T-1}) i żeby wykazać, że każda kolejna też będzie, konieczna jest indukcja.

Przechodzimy zatem do kolejnego kroku indukcyjnego i zakładamy, że

(r_{n_1}, r_{n_1+1},\dots, r_{n_1+T-1})=(r_{n_1+kT}, r_{n_1+1+kT},\dots, r_{n_2-1+kT}).

Zastosujemy dokładnie takie samo rozumowanie jak w kroku k=1, ale przy bardziej zawiłych indeksach.

Oznaczmy podobnie jak wcześniej przez \{r'_n\}_{n=0}^\infty, \{r''_n\}_{n=0}^\infty ciągi reszt wynikłe z dzielenia pisemnego odpowiednio \displaystyle \frac{r_i}{q} i \displaystyle \frac{r_j}{q}, gdzie i=n_1+T-1, a  j=n_1+T-1+kT.

Na podstawie Lematu

r_i= r'_n

r_j= r''_n

dla dowolnego n naturalnego.

Ponieważ z założenia mamy równość \displaystyle \frac{r_i}{q}= \frac{r_j}{q}, więc

r_i= r'_n= r''_n=r_j.

W szczególności równość zachodzi dla n=1

r_{i+1}=r_{j+1}

Podstawiając i upraszczając, dla n=1 równość przyjmuje postać

r_{n_1+T}=r_{n_1+T+kT}

Kontynuując dla n=2 mamy

r_{n_1+1+T}=r_{n_1+1+T+kT}

\vdots

Wreszcie dla n=T

r_{n_1 + T-1+T}=r_{n_1+T-1+T+kT}

Dostaliśmy zatem, że

(r_{n_1+T}, r_{n_1+1+T},\dots, r_{n_1+T-1+T})=(r_{n_1+(k+1)T}, r_{n_1+1+(k+1)T},\dots, r_{n_1+T-1+(k+1)T}).

Ale wiedząc z kroku k=1, że

(r_{n_1}, r_{n_1+1},\dots, r_{n_1+T-1})=(r_{n_1+T}, r_{n_1+1+T},\dots, r_{n_1+T-1+T}).

Otrzymujemy

(r_{n_1}, r_{n_1+1},\dots, r_{n_1+T-1})=(r_{n_1+(k+1)T}, r_{n_1+1+(k+1)T},\dots, r_{n_1+T-1+(k+1)T})

co należało pokazać.

Natychmiast też dostajemy, że skoro

(r_{n_1}, r_{n_1+1},\dots, r_{n_1+T-1})=(r_{n_1+kT}, r_{n_1+1+kT},\dots, r_{n_1+T-1+kT}).

to dla cyfr stosując definicję c_{n+1}=d_q(r_nL) mamy

(c_{n_1+1}, c_{n_1+2},\dots, c_{n_1+T})=(c_{n_1 +1+kT}, c_{n_1+2+kT},\dots, c_{n_1+T+kT}).

Uwzględniając jeszcze, że n_1<n_2 czyli, że T=n_2-n_1\geq 1, możemy stwierdzić, że \frac{p}{q} jest ułamkiem okresowym.

Wniosek. (Charakteryzacja liczb rzeczywistych przez ułamki okresowe).

Dowolna liczba rzeczywista x \in [0,1] jest ułamkiem okresowym wtedy i tylko wtedy, gdy x jest liczbą wymierną.

Charakteryzacja liczb rzeczywistych polega więc na tym, że część ułamkowa dowolnej liczby rzeczywistej jest okresowa wtedy i tylko wtedy, gdy jest liczbą wymierną.

Na podstawie tego rezultatu możemy znaleźć mnóstwo przykładów liczb niewymiernych o ładnie, ale nieokresowo zachowujących się rozwinięciach. Np. wspomniana wcześniej liczba

0,101001000100001\dots (przy dowolnej podstawie)

również przy dowolnej podstawie

\displaystyle \sum_{n=1}^\infty \frac{1}{L^{n!}} = 0,11000100000000000000001 \dots

która skądinąd jest znana jako stała Liouville’a dla L=10,

oraz w systemie przynajmniej dziesiątkowym

0,01234567891011121314151617181920 \dots

Teraz będzie jeszcze zapowiadana uwaga odnośnie dzielenia. Zauważmy, że jeśli podczas dzielenia pisemnego otrzymamy r_{n_0} wynikające z Twierdzenia 2, to wiemy, że po pewnej skończonej liczbie kroków T cała sekwencja reszt będzie się powtarzała w nieskończoność. Dzięki temu dowiedliśmy, że cyfry (c_{n_0+1}c_{n_0+2}\dots c_{n_0+T}) wyznaczają nam okres. W związku z tym, jeśli tylko podczas dzielenia pisemnego dana reszta nam się powtórzy, to możemy przerwać algorytm, a cyfry uzyskane pomiędzy tymi powtarzającymi się resztami będą okresem (pamiętając, że dana cyfra zależy od poprzedniej reszty). Jest to istotny fakt z punktu widzenia precyzji programów liczących, gdyż możemy uzyskać dzielenie liczb całkowitych z pełną precyzją w skończonej liczbie kroków. Jednak zwróćmy uwagę, że sekwencja cyfr nie zawsze będzie się powtarzała od najwcześniejszej cyfry powtarzającej się, gdyż np. w liczbie

0,1115(23)

powtarza nam się jedynka, ale jeszcze nie wyznacza ona okresu, a nawet w okresie nie ma jedynki.

W związku z powyższym uczniowie w szkołach i ja w podanych przykładach w części I całkiem słusznie przerywałem algorytm. Mamy więc optymistyczny akcent na koniec, że samodzielnie wykonane rachunki dają większą pewność, bo absolutną, niż choćby sto wyświetlonych cyfr po przecinku na kalkulatorze. Nigdy przecież nie wiadomo czy po stu trójkach po przecinku nie pojawi się dajmy na to czwórka. Choć, że zachodzi \frac{1}{3}=0,(3) możemy sprawdzić wykonując metodą z dowodu Twierdzenia 1.

Reklamy

Jedna uwaga do wpisu “Dzielenie pisemne. Rozwijanie liczb wymiernych na ułamki okresowe cz. II

  1. Pingback: Dodawanie pisemne. Ułamki okresowe. | roznematematyka

Skomentuj

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

Logo WordPress.com

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

Zdjęcie z Twittera

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

Zdjęcie na Facebooku

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

Zdjęcie na Google+

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

Connecting to %s