60109 Str098

■92    $. lJczby pierwsze i rozkład nn czynniki

■92    $. lJczby pierwsze i rozkład nn czynniki

\h moci n| < 2yjn . W metodzie tej używa się izw. ,,ułamków łańcuchowych"

łańcuchowych, /. których będziemy korzystać; czytelnik zainteresowany ich do-

a więc rozpoczniemy od zwięzłego opisu przedstawiania liczb rzeczywistych za pomocą ułamków łańcuchowych. Omówimy tu tylko le własności ułamków

kładniejszym omówieniem powinien sięgnąć na przykład po klasyczną i łatwo czytelną książkę Davcnporta (por. bibliografię na końcu tego podrozdziału)**.

Ułamki łańcuchowe. Rozwinięcie liczby rzeczywistej na ułamek łańcuchowy konstruujemy w następujący sposób. Niech a₀ = [*] będzie największą liczbą całkowitą, nic większą niż x_t i niech x₀ — x — a₀; niech Qi~[llx₀] i przyjmijmy .v_t = 1/jc₀ — a_x\ dla i > 1 niech    = [ 1/jc_£_    i weźmy

x_t = \/x,__l — a_t. Jeżeli stwierdzimy, że l/x_t__l jest liczbą całkowitą, to otrzymamy .Vj — 0 i kończymy to postępowanie. Nietrudno zauważyć, że to postępowanie kończy się wtedy i tylko wtedy, gdy liczba jc jest wymierna (gdyż wtedy liczby x_{ są wymierne i ich mianowniki tworzą ciąg malejący). Konstrukcja o₀, a_lt .... a_t pozwala napisać dla każdego i:

x = a₀ +

1

^ai +

1

1

a_t + x_Ł

co zwykle zapisujemy w bardziej zwartej postaci jako

x = a₀ +

+ ... +

<*i + x |

Przypuśćmy, że liczba x jest niewymierna. Jeśli rozwiniemy tę liczbę aż do i-tego wyrazu, a potem usuniemy x_lt to otrzymamy liczbę wymierną bjc,, zwaną i-tym reduktem rozwinięcia na ułamek łańcuchowy liczby x:

Twierdzenie 5.4.1. Korzystając z wprowadzonych wyżej oznaczeń, mamy:

gpfli + 1

c_t a_ic_ł_₁ m tjgg

(b) ułamki po prawej stronie wzorów w (a) są nieskracalne, tzn. jeśli b_t =

= a_ih_i_₁ + ó|_₂ oraz c_t = a_/c_/_₁ + C|_₂, to NWD (b_t, c,) = 1; (c) ó_łc,__ł —    = (— l)'”'¹ dla 1,

Czytelnikowi polskiemu warto tu polecić Teorię liczb W. Sierpińskiego (przyp. tłum.).

Dowód. Ocfiniujenmy ciągi {/>,} i {c,} za pomocą wzorów z punktu (a) i dowodzimy przez indukcję, że wtedy ułamek bjc₍ jest Mym reduktem. Będziemy dowodzić tego bez założenia, źe liczby a, są całkowite, tzn. udowodnimy, źe dla dowolnych liczb rzeczywistych a, ułamek bjcgdzie b_t i c_t są zdefiniowane za , . _% .    .    II 11

pomocą wzorów (a), jest równy a₀ + rr Sprawdzenie warunków

_f m \*i

początkowych indukcji (i = 0,1,2) jest trywialne. Przypuśćmy zatem, że teza jest prawdziwa dla wszystkich reduktów aż do Mego włącznie i udowodnijmy ją dla następnego, (/+ l)-go reduktu. Zauważmy, że (/+ l)*szy redukt powstaje przez zastąpienie liczby a, liczbą a,+ 1/A_m we wzorze określającym licznik i mianownik Mego reduktu za pomocą liczników i mianowników (/ - l)-go i (i - 2)-go reduktu. Zatem (/ + l>szy redukt jest równy

(fli +-+    1 1

\ ^ai+1)__ +V₂)-P Vi _ ^an\bj+ b_l__l

(_a,₊J_)_c,__i+Ci_₂ ||lgjpfp|p⁼ w.

na mocy założenia indukcyjnego. To kończy dowód indukcyjny punktu (a).

Punktu (c) też dowodzimy przez indukcję. Krok indukcyjny przebiega w następujący sposób:

ó_i+1C| - Vi+1 = (flj+i b-t + ViK “ Wfli+iĄ + c_H1) =

= Vi*iI Vi-i I -(-i)'"¹ = H)¹,

a więc z punktu (c) dla i wynika punkt (c) dla i + 1. Wreszcie punkt (b) wynika z punktu (c), gdyż wspólny dzielnik liczb ó, i ą musi być dzielnikiem (-1)¹’" \ czyli dzielnikiem ±1. To kończy dowód twierdzenia.

Jeżeli podzielimy równość w twierdzeniu 5.4. l(c) przez C|C_H1, to otrzymamy

^ct ^ci-1    ^ci^ci-1

Ponieważ ciąg liczb Cjjest oczywiście ściśle rosnącym ciągiem liczb całkowitych dodatnich, ta równość oznacza, że ciąg reduktów zachowuje się jak szereg naprzemienny, tzn. oscyluje w prawo i w lewo z amplitudą zmniejszającą się do zera; zatem ciąg reduktów jest zbieżny.

Wreszcie nietrudno zauważyć, że granicą ciągu reduktów jest liczba x, którą rozwijamy. Dla dowodu, zauważmy, że liczba x jest równa (/+ l)-mu