Wykład 1

Arytmetyka liczb całkowitych

Na początku zajmować się będziemy zbiorem liczb całkowitych

Z = {0, ±1, ±2, . . .}.

Zakładamy, że czytelnik zna relację <, która porządkuje ten zbiór. Zakłada-
my również:

Aksjomat dobrego porządku Każdy niepusty zbiór złożony z liczb całko-
witych nieujemnych posiada element najmniejszy

Oczywiście w całym zbiorze liczb całkowitych powyższy aksjomat nie jest

spełniony (nie ma najmniejszej liczby całkowitej).

Jak wiemy każdą liczbę całkowitą dodatnią można podzielić przez inną

liczbę dodatnią z resztą. Ideę dzielenia z resztą wyjaśnia następujące twier-
dzenie.

Twierdzenie 1 (Algorytm dzielenia) Niech a, b będą liczbami całkowitymi.
Wtedy istnieje dokładnie jedna para liczb całkwitych q, r, taka że

a = qb + r i 0 ¬ r < b

Dowód Rozważmy zbiór S wszystkich liczb postaci a − bx, gdzie x jest
dowolną liczbą całkowitą, a więc

S = {a − bx| x ∈ Z}

Nietrudno jest zauważyć, że w zbiorze S istnieją liczby nieujemne. Niech więc
S

0

będzie podzbiorem zbioru S złożonym z wszystkich liczb nieujemnych.

Mamy więc:

S

0

= {s ∈ S| s ­ 0}

Zgodnie z aksjomatem dobrego porządku istnie najmniejsza liczba zawarta
w zbiorze S

0

. Oznaczmy tą liczbę przez r, a więc

r = min(S

0

)

Oznacza to, że istnieje q, takie że r = a − qb i r ­ 0. Pokażemy, że r < b.
Niech bowiem r ­ b, wtedy r − b ­ 0 i r − b < r (bo b > 0) i mamy

r − b = a − qb − b = a − (q + 1)b

1

To oznacza, że r − b ∈ S

0

i r − b jest mniejsze od r, który jest minimalnym

elementem w zbiorze S

0

, a więc otrzymujemy sprzeczność. Sprzeczność ta

wynikła z założenia, że r ­ b. Zatem musimy być r < b. To daje nam rozkład
postaci a = qb + r, gdzie 0 ¬ r < b. Teraz trzeba pokazać jednoznaczność
rozkładu. Przypuśćmy, że istnieją dwie różne liczby r i r

0

, takie że a = qb + r

i a = q

0

b + r

0

i 0 ¬ r < b, 0 ¬ r

0

< b. Wtedy mamy r > r

0

lub r < r

0

.

Wystarczy zbadać jeden z tych przypadków, powiedzmy r > r

0

. Wtedy mamy

0 < r − r

0

< b. Odejmując równości a = qb + r, a = q

0

b + r

0

od siebie

stronami otrzymujemy 0 = (q − q

0

)b + (r − r

0

), a stąd r − r

0

= (q

0

− q)b ­ b

co jest sprzecznością z założeniem r < b. A więc przepadek r > r

0

jest

niemożliwy. Podobnie jest w przypadku r < r

0

. To oznacza, że rozkład jest

jednoznaczny.

Liczbę r nazywamy resztą z dzielenia a przez b.

Przykłady
1. a = 4509, b = 145, wtedy a = 31 · 145 + 14, a więc resztą z dzielenia 4509
przez 145 jest r = 14.
2. Liczba a może być ujemna na przykład dla a = −4509, b = 145 mamy
−4509 = (−32) · 145 + 131, a więc resztą z dzielenia −4509 przez 145 jest
r = 131.
Trzeba pamiętać, że reszta zawsze musi być liczbą większą od zera.

Niech a, b będą liczbami całkowitymi i niech b 6= 0. Wtedy mówimy, że

liczba b dzieli a (lub, że b jest dzielnikiem a) jeśli istnieje liczba całkowita c,
że a = bc. Fakt, że liczba b dzieli a zapisujemy symbolicznie b|a, a jesli liczba
b nie dzieli a to piszemy b - a.

Na przykład 24|96 bo 96 = 4 · 24. Podobnie −4|24 bo 24 = (−6) · (−4).

Liczba 3 nie dzieli liczby 7, a więc możemy zapisać 3 - 7.

Można łatwo zauważyć, że jeśli liczba b dzieli a to liczba b dzieli −a.

Mamy więc proste stwierdzenie:

Liczby a i −a mają takie same dzielniki.
Inną prostą uwagą jest, że 1 dzieli każdą niezerową liczbę całkowitą, oraz

że każda niezerow liczba całkowita dzieli 0.

Następne dwie uwagi dotyczą ilości dzielników danej liczby całkowitej:
(i) dzielniki niezerowej liczby całkowitej a są mniejsze lub równe |a|,
(ii) niezerowa liczba całkowita ma skończoną ilość dzielników.
Na przykład dzielnikami liczby 12 są ±1, ±2, ±3, ±4, ±6, ±12.

Niech a i b będą liczbami całkowitymi, z których przynajmniej jedna jest

różna od zera. Wtedy największym wspólnym dzielnikiem tych liczb
nazywamy największą liczbę całkowitą d, która dzieli jednocześnie a i b. Naj-

2

większy wspólny dzielnik oznaczamy przez NWD(a, b) i jest on wyznaczony
(w tym przypadku) jednoznacznie. Inaczej mówiąc d = NWD(a, b) wtedy i
tylko wtedy gdy

(i) d|a i d|b,
(ii) jeśli c|a i c|b to c ¬ d.
Z powyższej definicji widać, że NWD(a, b) ­ 1.
Na przykład NWD(12, 30) = 6.
Problemem, który tu się pojawia jest konstruktywne wyznaczanie naj-

większego wspólnego dzielnika dwóch liczb. Problem ten można rozwiązać
następująco. Zauważmy, że NWD(a, b) = NWD(−a, b) = NWD(a, −b) =
NWD(−a, −b). Zatem możemy ograniczyć się do przepadku gdy a i b są
liczbami dodatnimi. Załóżmy dodatkowo, że a ­ b. Oczywiście jeśli b|a to
NWD(a, b) = b i problemu nie ma. Przypuśćmy, że b - a wtedy możemy a
podzielić przez b z niezerową resztą:

a = q

0

b + r

0

,

0 < r

0

< b

Jeśli liczba c dzieli a i dzieli b to ta liczba musi dzielić również r

0

. Oznacza to,

że zbiór dzielników liczb a, b jest taki sam jak zbiór dzielników liczb b, r

0

, a

więc również NWD(a, b) = NWD(b, r

0

). Można więc proces dzielenia z resztą

kontynuować w następujący sposób:

a = q

0

b + r

0

,

0 < r

0

< b

b = q

1

r

0

+ r

1

,

0 < r

1

< r

0

r

0

= q

2

r

1

+ r

2

,

0 < r

2

< r

1

r

1

= q

3

r

2

+ r

3

,

0 < r

3

< r

2

..

.

a więc w następnym kroku dzielimy poprzednią resztę przez następną resztę.
Można zauważyć, że

NWD(a, b) = NWD(b, r

0

) = NWD(r

0

, r

1

) = NWD(r

1

, r

2

) = . . .

i ponieważ ciąg reszt jest ściśle malejącym ciągiem liczb całkowitych nie-
ujemnych to po skończonej ilości kroków musimy otrzymać resztę równą zero.
Zgodnie z wcześniejszym stwierdzeniem największym wspólnym dzielnikiem
liczb a i b będzie ostatnia niezerowa reszta w tym procesie. Opisany algorytm
znajdowania największego wspólnego dzielnika nosi nazwę Algorytmu Eu-
klidesa. Pokażemy teraz na przykładzie działanie tego algorytmu.
Zadanie Wyznaczyć przy pomocy Algorytmu Euklidesa największy wspólny

3

dzielnik liczb 324 i 148. A więc wykonujemy kolejne dzielenia:

324 = 2 · 148 + 28
148 = 5 · 28 + 8
28 = 3 · 8 + 4
8 = 4 · 2 + 0

Ostatnią niezerową resztą jest 4. To oznacza, że NWD(324, 148) = 4. Jest
to dużo lepszy i szybszy algorytm od rozkładania liczb na czynniki pierwsze.
Pokażemy, że powyższy algorytm może posłużyć do znalezienia takich liczb
całkowitych u, v, że 324u + 148v = 4. Najpierw z przedostatniego kroku
możemy wyznaczyć 4 jako:

4 = 28 − 3 · 8

dalej krok wyżej mamy 8 = 148 − 5 · 28 podstawiając to do wcześniej otrzy-
manego wzoru mamy:

4 = 28 − 3 · 8 = 28 − 3 · (148 − 5 · 28) = 16 · 28 − 3 · 148

w kroku wyżej mamy formułę na 28, więc możemy otrzymać:

4 = 28 − 3 · 8 = 16 · 28 − 3 · 148 = 16 · (324 − 2 · 149) − 3 · 148 = 16 · 324 − 35 · 148

co daje nam jedno z możliwych rozwiązań całkowitych równania 324u +
148v = 4, a mianowicie u = 16, v = −35.

A więc Algorytm Euklidesa można wykorzystywać nie tylko do poszuki-

wania największego wspólnego dzielnika dwóch liczb, ale również do rozwią-
zywania równań typu

ax + by = NWD(a, b)

. A więc prawdziwe jest następujące Twierdzenie.

Twierdzenie 2 Niech a, b będą dwiema liczbami całkowitymi z których przy-
najmniej jedna liczba jest różna od 0. Wtedy istnieją liczby całkowite u, v,
takie że

ua + vb = NWD(a, b)

Z powyższego twierdzenia wynika natychmiast następujący wniosek:

Wniosek 1 Liczba d jest największym wspólnym dzielnikiem liczb a i b wtedy
i tylko wtedy gdy

(i) d|a i d|b,
(ii) jeśli c|a i c|b to c|d

4

Dowód
(⇒) Niech d = NWD(a, b) wtedy zgodnie z powyższym twierdzeniem istnieją
liczby całkowite u i v takie, że d = ua+vb. Jeśli liczba c|a i c|b to a = kc, b = lc
dla pewnych k, l. Stąd d = ukc + vlc = (uk + vl)c, a więc c|d.
(⇐) Jeśli c|d to c ¬ d a więc punkty (i), (ii) pociągają warunki:

(i) d|a i d|b,
(ii) jeśli c|a i c|b to c ¬ d
które stanowią definicję największego wspólnego dzielnika.

Liczby a i b nazywamy względnie pierwszymi jeśli NWD(a, b) = 1.

Twierdzenie 3 Jeśli a|bc i liczby a, b są względnie pierwsze to a|c.

Dowód Ponieważ NWD(a, b) = 1 to zgodnie z powyższym Twierdzeniem
istnieją liczby u, v takie, że ua + vb = 1. Mnożąc to równanie obustronnie
przez c mamy uac + vbc = c. Ponieważ a|bc to istnieje k, że bc = ka, a więc
uac + vka = c. Stąd (uc + vk)a = c, więc a|c.

5