Wykład 4

Podzielność i NWD

4.1

Podzielność i liczby pierwsze

Definicja 4.1. Niech a, b ∈ Z, a 6= 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: p

1

< p

2

< . . . < p

k

liczb pierwszych oraz a

1

, a

2

, . . . , a

k

liczb naturalnych takie, że

m

= p

a

1

1

p

a

2

2

· . . . · p

a

k

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

q

=

$

n

p

%

oraz

r

=

n

p

−

$

n

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

DIV p =

$

n

p

%

i

n

MOD p =

n

p

−

$

n

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 6= 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