Matematyka.pl

Odwróćmy ten proces robienia czegoś z liczbą, tzn, jak z liczby a powstaje liczba \(\displaystyle{ b=a+1}\), to liczba b powstała z liczby \(\displaystyle{ a=b-1}\), a jak z liczby a powstaje liczba \(\displaystyle{ b= \frac{a}{a+1}}\), to liczba b powstała z liczby \(\displaystyle{ a=\frac{b}{1-b}}\). No to jak tamtymi operacjami miałem dojść z jedynki do dowolnej liczby dodatniej, to dojdę tymi przeciwnymi z dowolnej dodatniej do jedynki. Niech operacja zmienienia a na \(\displaystyle{ a-1}\) nazywa się A, a operacja zmienienia a na \(\displaystyle{ \frac{u}{1-u}}\) nazywa się B. Będę postępować następującym algorytmem:
Przedstawiam aktualnie rozważaną liczbę w postaci \(\displaystyle{ \frac{p}{q}}\) dla względnie pierwszych p i q. Jeżeli \(\displaystyle{ p>q}\) to wykonuję operację A, w przeciwnym wypadku operację B (i tak aż nie dojdę do jedynki). A czemu dojdę do jedynki? Powiedzmy, że miałem liczbę \(\displaystyle{ \frac{p}{q}}\). Jeżeli była ona większa od jedynki to otrzymałem z niej liczbę \(\displaystyle{ \frac{p-q}{q}}\), w przeciwnym wypadku otrzymałem liczbę \(\displaystyle{ \frac{p}{q-p}}\). Czyli to co naprawdę robię to algorytm Euklidesa (odejmuję mianownik od licznika albo licznik od mianownika) dla liczb p i q. A że były względnie pierwsze to dostanę w końcu jedynkę. To jest jednoznaczne tak samo jak względnie pierwsze liczby a i b spełniające \(\displaystyle{ ap+bq=1}\) są jednoznacznie wyznaczone (jak ktoś nie wie dlaczego, to pewnie znajdzie to pod hasłem "rozszerzony algorytm Euklidesa" w googlu).

Przyjmijmy, że \(\displaystyle{ a}\) jest ojcem \(\displaystyle{ b}\) \(\displaystyle{ \Leftrightarrow}\) \(\displaystyle{ b}\) jest dzieckiem \(\displaystyle{ a}\).
Dla danej liczby wymiernej \(\displaystyle{ w=\frac{p}{q}}\) \(\displaystyle{ (p,q \in \mathBB{Z} \cap (p,q)=1)}\).
Ojcem \(\displaystyle{ w}\) może być liczba \(\displaystyle{ w-1= \frac {p-q}{q}}\) lub \(\displaystyle{ \frac{w}{1-w}=\frac{p}{q-p}}\). Dla \(\displaystyle{ w \neq 1}\) dokładnie jedna z tych liczb jest dodatnia, więc ojciec każdej liczby jest wyznaczony jednoznacznie. Co więcej ma on ostro mniejszą sumą licznika i mianownika niż potomek. Ponieważ suma ta jest liczbą naturalną to przodkiem każdej liczby jest liczba 1.
c.n.d.