Wykład 2
Na ostatnim wykładzie udowodniliśmy następujące twierdzenie:
Twierdzenie 1 Jeśli a, b " Z i a = 0 lub b = 0. to istnieją liczby całkowite

u, v, że au + bv = NWD(a, b).
Można postawić ogólne pytanie dla jakich a, b, c " Z równanie ax+by = c
ma rozwiązanie całkowite? Powyższe twierdzenie mówi, że takie rozwiązanie
istnieje jeśli c = NWD(a, b). Czy tylko w takim przypadku? Okazuje się,
że nie, bo z faktu istnienia rozwiązania równania ax + by = NWD(a, b),
wynika istnienie rozwiązania równania ax + by = kNWD(a, b). Czyli jeśli
NWD(a, b)|c to równanie ax + by = c ma rozwiązanie. I nietrudno zauważyć,
że jeśli NWD(a, b) c to ax + by = c nie może mieć rozwiązania całkowitego
(prawa strona jest podzielna przez NWD(a, b), a lewa nie). Udowodniliśmy
więc:
Twierdzenie 2 Jeśli a, b, c " Z to równanie ax + by = c ma rozwiązanie
całkowite wtedy i tylko wtedy gdy NWD(a, b)|c.
Z Twierdzenia 1 można wysnuć 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
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 Liczby a i b są względnie pierwsze wtedy i tylko wtedy gdy
istnieją liczby całkowite u i v, że au + bv = 1.
Dowód Jeśli NWD(a, b) = 1 to zgodnie z Twierdzeniem 1 istnieją u, v takie,
że au+bv = 1, a jeśli dla pewnych u, v " Z mamy au+bv = 1 to NWD(a, b)|1,
a więc NWD(a, b) = 1.
1
Twierdzenie 4 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.
Będziemy mówić, że liczba całkowita p jest pierwsza jeśli p = 0, ą1 i

jedynymi dzielnikami liczby p sÄ… Ä…1, Ä…p.
Twierdzenie 5 Liczba p jest pierwsza wtedy i tylko wtedy gdy p spełnia
warunek: jeśli p|bc to p|b lub p|c.
Dowód
(Ò!)Załóżmy, że p jest liczbÄ… pierwszÄ… i p|bc. NajwiÄ™kszy wspólny dzielnik
liczb p i b jest równy 1 lub p. Jeśli NWD(p, b) = p to p|b. W przeciwnym
przypadku mamy NWD(p, b) = 1 i z poprzedniego Twierdzenia p|c.
(Ð!) Przypuśćmy, że p = kl wtedy p|kl, a wiÄ™c p|k lub p|l. JeÅ›li p|k to
istnieje t, że k = pt, a więc p = ptl czyli tl = 1, a ta równość w zbiorze
liczb całkowitych jest możliwa tylko dla l = ą1. To oznacza, że p nie ma
dzielników poza ą1, ąp, a więc jest liczbą pierwszą.
Twierdzenie to można rozszerzyć w następujący sposób:
Wniosek 2 JeÅ›li p|a1a2 · · · an to p dzieli przynajmniej jedno ai.
Twierdzenie 6 Każda liczba całkowita n oprócz liczb 0, ą1 jest iloczynem
liczb pierwszych.
Dowód Twierdzenie wystarczy udowodnić w przypadku gdy n > 1. Przy-
puśćmy, że istnieją liczby naturalne > 1, które nie są iloczynami liczb pierw-
szych. Oznaczmy przez S zbiór takich liczb. Wtedy istnieje najmniejsza liczba
w zbiorze S (na podstawie ADP). Nazwijmy jÄ… s. Ta liczba nie jest pierwsza,
a więc istnieją liczby a, b, takie że s = ab i 1 < a < s, 1 < b < s. Stąd
wynika, że a, b = S. Zatem liczby a, b dadzą się zapisać jako iloczyny liczb

pierwszych, a więc s również co jest sprzeczne z założeniem że tego się nie
da zrobić. Czyli S jest zbiorem pustym.
Twierdzenie 7 (Zasadnicze Twierdzenie Arytmetyki) Każda liczba cał-
kowita, różna od 0, ą1 jest iloczynem liczb pierwszych. Rozkład na liczby
pierwsze jest jednoznaczny w następującym sensie: Jeśli
n = p1p2 · · · pr i n = q1q2 · · · qs
2
gdzie pi, qj są pierwsze to s = r i jeśli p1 p2 . . . pr, q1 q2 . . . qs
to
p1 = Ä…q1, p2 = Ä…q2, . . . , pr = Ä…qr
Dowód Możliwość rozkładu wynika z poprzedniego Twierdzenia. przypuść-
my teraz, że:
p1p2 · · · pr = q1q2 · · · qs
wtedy p1|q1q2 · · · qs, a wiÄ™c dla pewnego i mamy p1|qi i ponieważ qi jest pierw-
sza to qi = ąp1, a więc po przenumerowaniu otrzymamy p1 = ąq1 itd...
Następujące Twierdzenie pozwala uprościć poszukiwanie dzielników pierw-
szych danej liczby.
Twierdzenie 8 Jeśli liczba n > 1 nie jest pierwsza to n posiada dzielnik
"
mniejszy bÄ…dz
równy od n.
Oznaczmy prze Ą(n) ilość dodatnich liczb pierwszych mniejszych bądz

ln n
równych od n. Wtedy wraz ze wzrostem n liczba Ą(n) zbliża się do , czyli
n
mamy:
Ä„(n)
n
lim = 1
n"
ln n
3