arytmetyka liczb całkowitych - omówienie 2

Nasza ocena:

3
Pobrań: 7
Wyświetleń: 406
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
arytmetyka liczb całkowitych - omówienie 2 - strona 1 arytmetyka liczb całkowitych - omówienie 2 - strona 2 arytmetyka liczb całkowitych - omówienie 2 - strona 3

Fragment notatki:

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|a1 a2 · · · an to p dzieli przynajmniej jedno ai .
Twierdzenie 6 Każda

(…)

…, a więc jest liczbą pierwszą.
Twierdzenie to można rozszerzyć w następujący sposób:
Wniosek 2 Jeśli p|a1 a2 · · · 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. Przypuśćmy, że istnieją liczby naturalne > 1, które nie są iloczynami liczb pierwszych. Oznaczmy przez S zbiór…
... zobacz całą notatkę

Komentarze użytkowników (0)

Zaloguj się, aby dodać komentarz