Wykład 2
Na ostatnim wykładzie udowodniliśmy następujące twierdzenie:
Twierdzenie 1 Jeśli a, b ∈ Z i a 6= 0 lub b 6= 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 6= 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|a
1
a
2
· · · a
n
to p dzieli przynajmniej jedno a
i
.
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 6= 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 = p
1
p
2
· · · p
r
i n = q
1
q
2
· · · q
s
2
gdzie p
i
, q
j
są pierwsze to s = r i jeśli p
1
¬ p
2
¬ . . . ¬ p
r
, q
1
¬ q
2
¬ . . . ¬ q
s
to
p
1
= ±q
1
, p
2
= ±q
2
, . . . , p
r
= ±q
r
Dowód Możliwość rozkładu wynika z poprzedniego Twierdzenia. przypuść-
my teraz, że:
p
1
p
2
· · · p
r
= q
1
q
2
· · · q
s
wtedy p
1
|q
1
q
2
· · · q
s
, a więc dla pewnego i mamy p
1
|q
i
i ponieważ q
i
jest pierw-
sza to q
i
= ±p
1
, a więc po przenumerowaniu otrzymamy p
1
= ±q
1
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ądź równy od
√
n.
Oznaczmy prze π(n) ilość dodatnich liczb pierwszych mniejszych bądź
równych od n. Wtedy wraz ze wzrostem n liczba π(n) zbliża się do
ln n
n
, czyli
mamy:
lim
n→∞
π(n)
n
ln n
= 1
3