Matematyka Dyskretna - Andrzej Szepietowski 2003.pdf

(165 KB) Pobierz
Ks16.dvi
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 otrzymalismy iloraz 145 i reszte 3. Liczby te spełniaj a równanie
1743 = 14512 + 3
i reszta jest mniejsza od dzielnika. Podobnie mozemy post api c dla dowolnych liczb natu-
ralnych a i b pod warunkiem, ze b 6= 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
0r < b
q nazywa sie ilorazem całkowitoliczbowym a przez b , a r nazywa sie reszt a z dzielenia
Zauwazmy, ze iloraz q jest zaokragleniem w dół normalnego ilorazu q =ba=bc . Iloraz
całkowitoliczbowy liczb a i b bedziemy oznacza c przez
ab
lub
a div b:
3
3931482.001.png
4
Rozdział 1. Teoria liczb
a reszte przez
a mod b:
Przykład 1.2 224 = 5 oraz 22 mod 4 = 2 , poniewaz 22 = 54 + 2 oraz 02 < 4 .
W przypadku, gdy a i b s a liczbami całkowitymi iloraz i róznice mozna róznie definiowa c.
Na przykład w jezyku Pascal iloraz dwóch liczb typu całkowitego oznacza sie przez
a div b
, —
zaokraglenie ilorazu a=b w góre, gdy a=b jest ujemne. Reszta, która oznacza sie przez
a mod b,
ba=bc
— zaokraglenie ilorazu a=b w dół, gdy a=b jest dodatnie i
da=be
jest okreslona wzorem:
a mod b = a-(a div b)*b.
Mamy wiec, na przykład:
22 div 4 = 5; (-22)div 4 = -5; 22 div(-4)= -5; (-22)div(-4)= 5;
22 mod 4 = 2; (-22)mod 4 = -2; 22 mod(-4)= 2; (-22)mod(-4)= -2.
1.2 Podzielnosc liczb
Mówimy, ze liczba całkowita a 6= 0 dzieli liczbe całkowita b , jezeli istnieje liczba całko-
wita z , taka ze:
b = az:
Bedziemy to oznaczac przez ajb . Zauwazmy, ze zachodzi wtedy:
b mod a = 0:
Liczbe a nazywamy dzielnikiem liczby b .
Przykład 1.3 3j6 , 3j6 oraz 3j0 .
Lemat 1.4 Jezeli ajb oraz ajc , to aj(b + c) oraz aj(bc)
Dowód. Jezeli ajb i ajc , to istnieja dwie liczby całkowite k i m , takie ze:
b = ak
oraz c = am:
Mamy wiec:
b + c = ak + am = a(k + m)
oraz
bc = akam = a(km)
czyli a dzieli b + c oraz bc .
2
i jest to
1.3. Relacja kongruencji
5
1.3 Relacja kongruencji
Niech m bedzie dowolna liczba naturalna m 6= 0 . Powiemy, ze dwie liczby całkowite a i
b sa równowazne (lub przystaj a) modulo m , jezeli
mj(ab):
Bedziemy wtedy pisac:
a = b (mod m):
Przykład 1.5 1 = 4 (mod 3) , 3 = 0 (mod 3) , 1 = 2 (mod 3) , 1 =7
(mod 3) .
Jezeli a i b s a dodatnie, to a = b (mod m) wtedy i tylko wtedy, gdy a i b maj a takie
same reszty z dzielenia przez m .
Lemat 1.6 Relacja przystawania modulo jest relacj a równowaznosci, czyli spełnia nastepuj ace
trzy warunki:
zwrotnosc, dla kazdego a zachodzi
a = a (mod m) ,
symetrie, dla kazdego a i b , jezeli a = b (mod m); to b = a (mod m) ,
przechodniosc, dla kazdego a , b i c ,
jezeli a = b (mod m) i b = c (mod m); to a = c (mod m) .
Dowód. Udowodnimy tylko przechodniosc relacji. Jezeli mj(ab) oraz mj(bc);
to mj((ab) + (bc)); czyli mj(ac) .
2
Ponadto relacja modulo jest zgodna z dodawaniem, odejmowaniem i mnozeniem.
Twierdzenie 1.7 Jezeli a = b (mod m) oraz c = d (mod m); to:
a + c = b + d (mod m);
ac = bd (mod m);
ac = bd (mod m):
Dowód. Z załozenia mamy:
mj(ab)
oraz mj(cd);
z tego zas łatwo wynika, ze m dzieli:
(a + c)(b + d); (ac)(bd) oraz acbd = a(cd) + d(ab);
czyli zachodzi teza twierdzenia.
2
Przykład 1.8 Twierdzenie 1.7 moze byc uzyte do obliczania reszty z dzielenia Jezeli chce-
my policzyc na przykład
1999 mod 3;

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin