Wykład 4
Podzielność i NWD
4.1 Podzielność i liczby pierwsze
Definicja 4.1. Niech a, b " Z, a = 0. Mówimy, że liczba a dzieli liczbę b (lub: b jest

podzielna przez a albo a jest dzielnikiem b) i piszemy a|b, gdy istnieje taka liczba cał-
kowita d, że b = ad. Dzielnikiem nietrywialnym liczby b nazywamy każdy jej dzielnik
dodatni różny od 1 i od b.
Definicja 4.2. Liczbę całkowitą nazywamy złożoną, jeżeli ma ona dzielnik nietrywialny.
Definicja 4.3. Liczbę naturalną nazywamy pierwszą, jeżeli ma ona dokładnie dwa róż-
ne dzielniki dodatnie. Zbiór wszystkich liczb pierwszych oznaczamy symbolem P.
Twierdzenie 4.1. Zbiór P zawiera nieskończenie wiele elementów.
Twierdzenie 4.2 (o rozkładzie na czynniki pierwsze). Niech m będzie dowolną licz-
bą naturalną. Istnieją wówczas i są określone jednoznacznie ciągi: p1 < p2 < . . . < pk
liczb pierwszych oraz a1, a2, . . . , ak liczb naturalnych takie, że
1 2 k
m = pa pa · . . . · pa .
1 2 k
4.2 Iloraz całkowity i reszta
Definicja 4.4. Podłogą lub dolną częścią całkowitą liczby x " R nazywamy liczbę
#x# = max{n " Z : n x}.
Sufitem lub górną częścią całkowitą liczby x " R nazywamy liczbę
#x # = min{n " Z : n x}.
12
Twierdzenie 4.3. Niech p " N. Dla każdej liczby całkowitej n liczby

n n n
q = oraz r = - · p
p p p
są jedynymi liczbami takimi, że q " Z i r " {0, 1, . . . , p - 1} oraz zachodzi równość
n = p · q + r . (4.1)
Definicja 4.5. Niech p będzie dowolną liczbą naturalną. Dla każdej liczby n " Z liczby

n n n
n DIV p = i n MOD p = - · p .
p p p
nazywamy odpowiednio ilorazem całkowitym liczby n przez p i resztą z dzielenia liczby
n przez p lub resztÄ… modulo p.
Przy tak wprowadzonych oznaczeniach równość (4.1) można zapisać w postaci:
n = (n DIV p) · p + (n MOD p) . (4.2)
4.3 Największy wspólny dzielnik
Definicja 4.6. Niech a i b będą dwiema liczbami całkowitymi, z których przynajmniej
jedna jest różna od 0. Największym wspólnym dzielnikiem liczb a i b nazywamy najwięk-
szą liczbę całkowitą d taką, że d|a i d|b. Liczbę tę oznaczamy symbolem NWD(a, b).
Uwaga 4.1. (a) Jeżeli a " Z, to NWD(a, b) = NWD(a, 0) = |a|.
(b) Dla całkowitych liczb a, b = 0 mamy NWD(a, b) = NWD(|a|, |b|)

Definicja 4.7. Liczby a, b " Z nazywamy względnie pierwszymi, gdy NWD(a, b) = 1.
Piszemy wtedy: aĄ"b.
Twierdzenie 4.4. Jeżeli a, b " N są takimi liczbami, że a > b, to
NWD(a, b) = NWD(b, a MOD b).
13
4.4 Algorytm Euklidesa
Dane: Liczby naturalne a, b.
Szukane: NWD(a, b).
Zmienne pomocnicze: r, q.
Start
r := a;
q := b;
dopóki q > 0 wykonuj
p := r MOD q
r := q
q := p;
zwróć r
Stop
Twierdzenie 4.5. Algorytm Euklidesa działa poprawnie, tzn. otrzymana w wyniku dzia-
Å‚ania tego algorytmu liczba r = NWD(a, b).
Twierdzenie 4.6 (o liniowym rozkładzie NWD). Niech a, b będą dwiema liczbami
naturalnymi i d = NWD(a, b). Istnieją wówczas liczby s, t " Z takie, że
sa + tb = d.
Wniosek 4.1. Liczby naturalne a i b są względnie pierwsze wtedy i tylko wtedy, gdy
istnieją liczby całkowite s i t takie, że
sa + tb = 1.
Wniosek 4.2. Jeżeli a, b są liczbami naturalnymi i c jest liczbą całkowitą, to równanie
ax + by = c
ma rozwiązanie (x, y) będące parą liczb całkowitych wtedy i tylko wtedy, gdy liczba c jest
całkowitą wielokrotnością NWD(a, b).
14