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