Arytmetyka liczb całkowitych

Nasza ocena:

3
Pobrań: 49
Wyświetleń: 616
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Arytmetyka liczb całkowitych - strona 1 Arytmetyka liczb całkowitych - strona 2 Arytmetyka liczb całkowitych - strona 3

Fragment notatki:


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)

Zaloguj się, aby dodać komentarz