To tylko jedna z 5 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Wykład 1
Arytmetyka liczb całkowitych
Na początku zajmować się będziemy zbiorem liczb całkowitych
Z = {0, ±1, ±2, . . .}.
Zakładamy, że czytelnik zna relację 0) i mamy
r − b = a − qb − b = a − (q + 1)b
1
To oznacza, że r − b ∈ S i r − b jest mniejsze od r, który jest minimalnym
elementem w zbiorze S , a więc otrzymujemy sprzeczność. Sprzeczność ta
wynikła z założenia, że r b. Zatem musimy być r r lub r r . Wtedy mamy
0 r jest
niemożliwy. Podobnie jest w przypadku r
(…)
… w tym procesie. Opisany algorytm
znajdowania największego wspólnego dzielnika nosi nazwę Algorytmu Euklidesa. Pokażemy teraz na przykładzie działanie tego algorytmu.
Zadanie Wyznaczyć przy pomocy Algorytmu Euklidesa największy wspólny
3
dzielnik liczb 324 i 148. A więc wykonujemy kolejne dzielenia:
324 = 2 · 148 + 28
148 = 5 · 28 + 8
28 = 3 · 8 + 4
8=4·2+0
Ostatnią niezerową resztą jest 4. To oznacza, że NWD…
… − 5 · 28) = 16 · 28 − 3 · 148
w kroku wyżej mamy formułę na 28, więc możemy otrzymać:
4 = 28 − 3 · 8 = 16 · 28 − 3 · 148 = 16 · (324 − 2 · 149) − 3 · 148 = 16 · 324 − 35 · 148
co daje nam jedno z możliwych rozwiązań całkowitych równania 324u +
148v = 4, a mianowicie u = 16, v = −35.
A więc Algorytm Euklidesa można wykorzystywać nie tylko do poszukiwania największego wspólnego dzielnika dwóch liczb…
… dzielników danej liczby całkowitej:
(i) dzielniki niezerowej liczby całkowitej a są mniejsze lub równe |a|,
(ii) niezerowa liczba całkowita ma skończoną ilość dzielników.
Na przykład dzielnikami liczby 12 są ±1, ±2, ±3, ±4, ±6, ±12.
Niech a i b będą liczbami całkowitymi, z których przynajmniej jedna jest
różna od zera. Wtedy największym wspólnym dzielnikiem tych liczb
nazywamy największą liczbę całkowitą d, która dzieli jednocześnie a i b. Naj-
2
większy wspólny dzielnik oznaczamy przez NWD(a, b) i jest on wyznaczony
(w tym przypadku) jednoznacznie. Inaczej mówiąc d = NWD(a, b) wtedy i
tylko wtedy gdy
(i) d|a i d|b,
(ii) jeśli c|a i c|b to c d.
Z powyższej definicji widać, że NWD(a, b) 1.
Na przykład NWD(12, 30) = 6.
Problemem, który tu się pojawia jest konstruktywne wyznaczanie największego wspólnego dzielnika…
… Wykład 1
Arytmetyka liczb całkowitych
Na początku zajmować się będziemy zbiorem liczb całkowitych
Z = {0, ±1, ±2, . . .}.
Zakładamy, że czytelnik zna relację <, która porządkuje ten zbiór. Zakładamy również:
Aksjomat dobrego porządku Każdy niepusty zbiór złożony z liczb całkowitych nieujemnych posiada element najmniejszy
Oczywiście w całym zbiorze liczb całkowitych powyższy aksjomat…
... zobacz całą notatkę
Komentarze użytkowników (0)