984501241

18

I. STRUKTURY LICZBOWE

Twierdzenie 4.1. Dla dowolnych liczb całkowitych dodatnich a i b istnieją takie liczby całkowite x i y, że

NWD(a, b) = ax + by.

W szczególności, jeśli liczby całkowite dodatnie a i b są względnie pierwsze, to istnieją takie liczby całkowite x i y, że

ax + by = 1.

Aby to twierdzenie uzasadnić rozważmy zbiór

S = {ax + by: ax + by > 0 oraz x, y € Z}.

Na mocy Zasady Minimum istnieje

d = min S.

Istnieją wówczas liczby x₀, y₀ G Z takie, że

d = ax o + byo.

Pozostaje wykazać, że d = NWD(a, b). Zaważmy wpierw, że d\a. Istotnie, gdyby reszta z dzielenia a przez d była dodatnia, tzn. gdyby dla pewnego z G N oraz 0 < r < d zachodziła równość a — zd + r to mieli byśmy

r = a — zd = a — azxo — byo = a(l — zxo) + b(—yo) € S, co daje sprzeczność z określeniem elementu d jako najmniejszego elementu w zbiorze S.

Podobni dowodzi się, że d\b. Zatem d < NWD(a, b). Jeśli zaś przyjmiemy, że NWD(a, b) = d₀, to do|a oraz do\b, czyli istnieją takie liczby x, y € N, że a = xd_Q oraz b = yd₀. Mamy wówczas

d = ax o + 6j/₀ = xd₀x₀ + ydoyo = dn(xx₀ + yy₀), co w szczególności oznacza, że d > do- Mamy więc równość d = do, co kończy dowód. Teraz już łatwo otrzymujemy następujące twierdzenie:

Twierdzenie 4.2 (Zasadnicze Twierdzenie Arytmetyki). Jeśli liczby a ib są względnie pierwsze oraz a dzieli iloczyn bc, to a dzieli c.

Istotnie, skoro NWD(a, 6) = 1, to z twierdzenia 4.1 wynika, że ax + by = 1

dla pewnych liczb x, y G N, a więc

c = acx + bcy.

Skoro zaś a|aca: oraz a\bcy, to a|c.

Metodą indukcji matematycznej twierdzenie to można nieco uogólnić:

Wniosek 4.1. Jeśli liczby a oraz b są względnie pierwsze oraz n jest liczbą naturalną, to

a\bⁿc pociąga a\c.