Matematyka dyskretna 2004 - 06 Teoria liczb.pdf - Matematyka dyskretna - Minnie_

Matematyka Dyskretna

Andrzej Szepietowski

25 marca 2004 roku

Rozdział 1

Teoria liczb

1.1 Dzielenie całkowitoliczbowe

Zacznijmy od przypomnienia szkolnego algorytmu dzielenia liczb naturalnych. Podziel-

my 174 przez 12.

1 4

1 7 4 : 1 2

1 2

5 4

4 8

W wyniku dzielenia otrzymalismy iloraz 14 i reszte 6 . Liczby te spełniaj a równanie

174 = 1412 + 6

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 zaokr agleniem w dół normalnego ilorazu q =b b

c . Iloraz

całkowitoliczbowy liczb a i b bedziemy oznacza c przez

lub

a div b:

a reszte przez

a mod b:

Rozdział 1. Teoria liczb

Przykład 1.2 224 = 5 oraz 22 mod 4 = 2 , poniewaz 22 = 54 + 2 oraz 02 < 4 .

Powyzsze deﬁnicje zakładały, ze a i b s a naturalne. W przypadku, gdy a i b s a liczba-

mi całkowitymi, iloraz i róznice mozna róznie deﬁniowa c. Na przykład w jezyku Pascal

iloraz dwóch liczb typu całkowitego oznacza sie przez

a div b

i jest to b b

c — zaokr aglenie ilorazu

w dół, gdy

jest dodatnie i d b

e , — zaokr aglenie

ilorazu

w góre, gdy

jest ujemne. Reszta, któr a oznacza sie przez

a mod b,

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łkowit a 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 istniej a 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 .

1.3. Relacja kongruencji

1.3 Relacja kongruencji

Niech m bedzie dowoln a liczb a naturaln a m 6= 0 . Powiemy, ze dwie liczby całkowite a i

b s a 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 na-

stepuj 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) .

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);

c = b

d (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.

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;

Matematyka dyskretna 2004 - 06 Teoria liczb.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: