To tylko jedna z 36 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Matematyka Dyskretna Andrzej Szepietowski 17 marca 2003 roku Rozdział 1 Teoria liczb 1.1 Dzielenie całkowitoliczbowe Zacznijmy od przypomnienia szkolnego algorytmu dzielenia liczb naturalnych. Podziel- my 1743 przez 12. 1 4 5 1 7 4 3 : 1 2 1 2 5 4 4 8 6 3 6 0 3 W wyniku dzielenia otrzymali´smy iloraz 145 i reszt˛e 3. Liczby te spełniaj ˛ a równanie 1743 = 145 · 12 + 3 i reszta jest mniejsza od dzielnika. Podobnie mo˙zemy post ˛ api ´c dla dowolnych liczb natu- ralnych a i b pod warunkiem, ˙ze b = 0. Twierdzenie 1.1 Dla dowolnych liczb naturalnych a oraz b 0 istnieje dokładnie jedna para liczb naturalnych q i r spełniaj ˛ acych warunki: • a = bq + r • 0 ≤ r
(…)
… rozwia˙ równania: a) 3 · x = 1, b) 3 · x = 2.
s
˛z
15. W pier´cieniu Z17 rozwia˙ równania: a) 8x = 2,
s
˛z
b) 9x = 4.
16. W pier´cieniu Z14 rozwia˙ równania: a) 6x = 2, b) 6x = 9.
s
˛z
17. Znajd´ całkowite rozwi¸ zanie (x, y) spełniaj¸ ce równanie: 17x + 40y = 1.
z
a
a
18. Podaj rozkład na czynniki pierwsze liczb 240 oraz 111.
19. Ile dzielników ma liczba 240?
20. Znajd´ elementy odwrotne…
…
a−1 a + (−k)m = 1
czyli N W D(a, m) = 1 (wniosek 1.20).
2
´
Z powy˙ szego dowodu wynika, ze element odwrotny do a mo˙ na wyliczy c stosuj¸ c
z
˙
z
a
algorytm Euklidesa. Na przykład policzmy element odwrotny do 12 w pier´cieniu Z17 .
s
Najpierw zastosujemy algorytm Euklidesa, aby obliczy´ x i y, takie ze:
c
˙
12x + 17y = 1.
Kolejne kroki algorytmu przedstawiono w tabeli:
p
17
5
5
1
1
q
12
12
2
2
0
xp…
… to nam pomóc w odgadni¸ciu,
e
z
e
ze litera e koduje liter¸ o, a litera p koduje liter¸ t. Mamy wi¸ c dwa równania:
˙
e
e
e
15 = 19a + b (mod 26),
4 = 14a + b (mod 26).
Po odj¸ ciu tych równa´ stronami mamy:
e
n
11 = 5a (mod 26).
Korzystaj¸ c z algorytmu Euklidesa, mo˙emy teraz wyliczy´ element odwrotny do 5 w piera
z
c
scieniu Z26 . Jest to 21, poniewa˙:
´
z
(−5)5 + 26 = 1
− 5 = 21 (mod 26),
oraz
tak wi¸ c…
…, 41, 43, 47.
Liczba n > 1, która nie jest pierwsza jest zło˙ ona. Istnieja wtedy dwie liczby k, m < n,
z
˛
takie, ze n = k · m.
˙
1.9 Rozkład liczb na czynniki pierwsze
W tym rozdziale zobaczymy, ze ka˙ d¸ liczb¸ naturaln¸ n > 1 mo˙ na rozło˙ y c na czynniki
˙
z a
e
a
z
z ´
pierwsze i ze taki rozkład jest jednoznaczny z dokładno´ci¸ do kolejno´ci czynników. Na
˙
s a
s
przykład:
12 = 22 · 3
i
180 = 22…
... zobacz całą notatkę
Komentarze użytkowników (0)