To tylko jedna z 8 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…
… 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)