slajdy teoria liczb

background image

Teoria liczb-

matematyka

background image

Teoria liczb jest dziedziną matematyki, zajmującą się badaniem
własności liczb – początkowo tylko naturalnych.

Obecnie należałoby powiedzieć: głownie naturalnych. Jej początki
sięgają starożytności. Zajmowali się nią Pitagoras, Euklides,
Eratostenes, Diofantos i wielu innych.

Bujny rozwój teorii liczb datuje się mniej więcej od czasów
działalności Pierre'a Fermata (1601-1665), autora wypowiedzi
słynnego Wielkiego Twierdzenia Fermata. Do dwudziestego wieku
powszechną była opinia, iż teoria ta nie ma żadnego
zastosowania. Jednak dzięki wielkiemu rozwojowi kryptografii -
nauki zajmującej się układaniem i łamaniem szyfrów - pogląd ten
musiał zostać zweryfikowany.

background image

Zacznijmy od przypomnienia szkolnego algorytmu dzielenia liczb
naturalnych. Podzielmy 1743 przez 12.

W wyniku dzielenia otrzymaliśmy iloraz 145 i resztę 3. Liczby te
spełniają równanie
1743 = 145*12 + 3 i reszta jest mniejsza od dzielnika.

Podobnie możemy postąpić dla dowolnych liczb a i b, pod warunkiem,
że b

0.

Twierdzenie 6.1 Dla dowolnych liczb naturalnych a oraz b > 0 istnieje
dokładnie jedna para liczb naturalnych q
i r spełniających warunki:
1. a = bq + r
2. 0 r < b

q nazywa się ilorazem całkowitoliczbowym a przez b, a r nazywa się
resztą z dzielenia.

background image

Zauważmy, że iloraz q jest zaokrągleniem w dół normalnego ilorazu;

Iloraz całkowitoliczbowy liczb a i b będziemy oznaczać przez

a resztę przez a mod b.

Przykład

Podzielność liczb

Liczbę a nazywamy dzielnikiem liczby b.

background image

background image

Relacja kongruencji

Przykład 1 = 4 (mod 3), 3 = 0 (mod 3), -1 = 2 (mod 3), -1 = -7(mod
3).

Jeżeli a i b są dodatnie, to a = b (mod m) wtedy i tylko wtedy, gdy
a i b mają takie same reszty z dzielenia przez m.

background image

Lemat 6.2 Relacja przystawania modulo jest relacją równoważności,
czyli spełnia następujące trzy warunki:

1. zwrotność, dla każdego a zachodzi a = a (mod m),

2. symetrię, dla każdego a i b, jeżeli a = b (mod m); to b = a (mod
m),

3. przechodniość, dla każdego a, b i c, jeżeli a = b (mod m) i b = c
(mod m); to a = c (mod m).

Ponadto relacja modulo jest zgodna z dodawaniem, odejmowaniem
i mnożeniem.

Twierdzenie 6.3 Jeżeli a = b (mod m) oraz c = d (mod m), to:
a + c = b + d (mod m); a - c = b - d (mod m); ac = bd (mod m).

background image

Klasy abstrakcji.

Dla relacji przystawania modulo m definiujemy klasy abstrakcji.
Dla dowolnej liczby całkowitej x, klasę abstrakcji elementu x
definiujemy w następujący sposób:

Przykład: Dla m=3 mamy trzy klasy abstrakcji:

background image

Zauważmy, że klasy abstrakcji elementów równoważnych pokrywają się.

Lemat 6.4. Jeżeli x = y (mod m); to [x] = [y].

Następna ważna własność klas abstrakcji to ich rozłączność.

Lemat 6.5. Jeżeli [x]

[y]  , to [x] = [y], inaczej, dwie klasy

abstrakcji [x] i [y] albo są identyczne, albo są rozłączne.

background image

Pierścień Z

m

Klasy abstrakcji relacji modulo m wyglądają następująco:
[0], [1],...,[m - 1].

Dla dowolnego k z przedziału 0

k

m- 1, klasa [k] jest postaci:

background image

z dodawaniem i mnożeniem określonym następującymi tabelami:

Rozważmy zbiór reszt modulo 5. Składa się on z pięciu klas:

[0], [1], [2], [3], [4]; dla prostoty będziemy dalej opuszczać
nawiasy. Mamy więc zbiór:

Pierścień Z

5

background image

Pierścień Z

4

Rozważmy teraz pierścień reszt modulo 4:

gdzie dodawanie i mnożenie jest określone następującymi tabelami:

W tym pierścieniu nie ma elementu odwrotnego do 2. Ponadto mamy
2

2= 0.

Zauważmy, że każdy element oprócz zera ma w tym pierścieniu
element odwrotny względem mnożenia, czyli

background image

Największy wspólny dzielnik.

Dla dwóch liczb całkowitych a i b, ich największy wspólny
dzielnik
to największa liczba całkowita n, która dzieli a i b.
Największy wspólny dzielnik liczb a i b będziemy oznaczać przez
NWD(a, b). Na przykład: NWD(4, 6) = 2, NWD(4, 0) = 4.

Największy wspólny dzielnik dwóch liczb dodatnich można
obliczyć za pomocą algorytmu Euklidesa.

Algorytm Euklidesa: Aby obliczyć największy wspólny dzielnik
dwóch dodatnich liczb naturalnych a, b, powtarzamy aż do skutku:

czyli q=0, sprzeczność.

background image

* dopóki a

b  0, wykonuj:

** jeżeli a

b, to a := a mod b,

** w przeciwnym wypadku b := b mod a.
* NWD(a, b) = a + b,

Powyższy algorytm oblicza resztę z dzielenia większej liczby przez
mniejszą tak długo, aż otrzyma zero. Wtedy wynikiem działania
algorytmu jest ta druga liczba (jeżeli a = 0, to a + b = b, a jeżeli b = 0,
to a + b = a).

W poniższej tabeli pokazano kolejne kroki działania algorytmu
Euklidesa na parze liczb 36 i 15:

background image

background image

Algorytm Euklidesa można tak zmodyfikować, aby oprócz
największego wspólnego dzielnika NWD(a, b), wyliczał
także liczby x i y, takie że: xa + yb = NWD(a, b).

Rozszerzony algorytm Euklidesa.

Dane wyjściowe: NWD(a,b) oraz liczby całkowite x,y takie, że
xa + yb = NWD(a, b).

Dane wejściowe: dwie liczby naturalne a,b.

* podstaw: xa := 1, ya := 0, xb := 0, yb := 1.

* dopóki a

b  0, wykonuj:

** jeżeli a

b, to a := a mod b,

xa := xa – xb

(a

b);

ya := ya – yb

(a

b);

background image

** w przeciwnym wypadku: b := b mod a,
xb := xb – xa

(b

a);

yb := yb – ya

(b

a).

* NWD(a,b): = a+b.

* Jeżeli a > 0, to x := xa ; y:= ya.

* Jeżeli b > 0, to x := xb ; y:= yb.

W poniższej tabeli pokazano kolejne kroki działania
rozszerzonego algorytmu Euklidesa na parze liczb 36 i 15:

a b xa ya xb yb

36 15 1 0 0 1

6 15 1 -2 0 1

6 3 1 -2 -2 5

0 3 5 -12 -2 5

Tak więc liczbę 3 można przedstawić jako kombinację liczb 15 i 36
w następujący sposób:
3 = (-2)

36 + (5)

15.

background image

Liczby pierwsze i względnie pierwsze.

Dwie liczby naturalne a i bwzględnie pierwsze, jeżeli NWD(a;
b)
= 1, a liczba naturalna p jest pierwsza, jeżeli p > 1 i jedynymi
dzielnikami naturalnymi p są jedynka i samo p.

Oto wszystkie liczby pierwsze mniejsze od 50:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Liczba n > 1, która nie jest pierwsza, jest złożona. Istnieją wtedy
dwie liczby k, m < n, takie, że n = k

m.

Twierdzenie: Liczb pierwszych jest nieskończenie wiele.

background image

Rozkład liczby na czynniki pierwsze.

W tym rozdziale zobaczymy, że każdą liczbę naturalną n > 1
można rozłożyć na czynniki pierwsze i że taki rozkład jest
jednoznaczny z dokładnością do kolejności czynników. Na przykład:

Twierdzenie 6.6. Każdą liczbę naturalną n > 1 można przedstawić jako
iloczyn liczb pierwszych (niekoniecznie różnych):
n = q

1

q

2

...q

r

Zasada minimum. W każdym niepustym zbiorze liczb naturalnych
istnieje liczba najmniejsza

.

background image

Lemat Euklidesa: Jeżeli n|ab i NWD(a,n) = 1, to n|b.

Twierdzenie 6.7. Każdą liczbę naturalną n > 1 można w dokładnie
jeden sposób przedstawić w postaci iloczynu:

gdzie

i są dodatnimi liczbami naturalnymi, pi są liczbami pierwszymi

oraz zachodzi

background image

Elementy odwracalne.

background image

Twierdzenie 6.7.

background image

Przykład.

background image

Rozwiązywanie równań z kongruencją.

Jeśli mamy równanie

to rozwiązaniem jest

Przykład Rozwiązać równanie 2x

101 (mod 637).

background image

Funkcja Eulera.

Twierdzenie Eulera

Przykład. Za pomocą twierdzenia Eulera obliczyć 129 podniesione
do potęgi 209 modulo 18.

background image

Twierdzenie chińskie o resztach.

background image

background image

Kod RSA.

Niech litery alfabetu – liczby 1-26; pauza 27, pozostałe znaki-
powyżej 27.

Z danego słowa otrzymujemy liczbę L.

Na przykład: ADAM: 01040113; L=1040113.

Niech p, q- liczby względnie pierwsze, r = p

q, L

<0,r).

Niech s- liczba naturalna taka, że NWD(s,p-1)=1 i NWD(s, q-1)=1.

Kod C liczby L obliczamy według wzoru:

background image

Jak odkodować liczbę L ?

Z tego, że NWD(s,p-1)=1 wynika, że istnieją liczby całkowite a, b
takie, że sa+(p-1)b = 1.

W takim razie

(ponieważ z twierdzenia Eulera mamy, że

).

Podobnie, z tego, że NWD(s,q-1)=1 otrzymamy,
że

L otrzymamy rozwiązując układ równań:

Przykład Dla p=13, q=17, s=5 zakodować AB.


Document Outline


Wyszukiwarka

Podobne podstrony:
algebra z teoria liczb wyk
algebra z teoria liczb wyk cz2
9 Teoria liczb
Algebra z teorią liczb
elektronika teoria liczb id 158 Nieznany
Matematyka dyskretna 2004 06 Teoria liczb
Lenda A Teoria liczb
Matematyka dyskretna cz 1 Teoria liczb
W10 - Teoria liczb kardynalnych, szkoła, logika
Teoria liczb przyklady, studia, 6 semestr, Teoria liczb, wyklady cwiczenia
08 Rozdział 07 Teoria liczb zespolonych
Algorytmiczna teoria liczb id 5 Nieznany (2)
LAB1 Teoria Liczb
algebra z teoria liczb wyk
Matematyka dyskretna 2004 06 Teoria liczb

więcej podobnych podstron