MD_wyklad2_2011.pdf

Materiałydydaktyczne–MatematykaDyskretna(Wykład2)

Wst¦p do arytmetyki modularnej: systemy pozycyjne, relacja podzielno±ci liczb

całkowitych, liczby pierwsze, najwi¦kszy wspólny dzielnik, najmniejsza wspólna

wielokrotno±¢, algorytm Euklidesa.

Kilka słów wst¦pu

Jednym z wa»nych powodów, dla których informatycy interesuj¡ si¦ du»ymi liczbami, opera-

cjami na nich i innnymi zagadnieniam, które zaliczane s¡ do działu matematyki zwanej Teori¡

Liczb jest bezpiecze«stwo systemów komputerowych. Teoria liczb, jako dyscyplina matematyki,

wyodr¦bniła si¦ z niej gdzie± na przełomie XVIII i XIX wieku, ale ju» wcze±niej znane były ró»ne

zagadnienia teorio-liczbowe nie maj¡ce praktycznych zastosowa«, ani w dziedzinach matematycz-

nych, ani tym bardziej pozamatematycznych. Mimo ich niepraktyczno±ci silnie przyci¡gały uwag¦

najwybitniejszych matematyków. Najbardziej znanymi z tego zakresu s¡: Wielka Twierdzenie Fer-

mata, Hipoteza Goldbacha, czy cały wachlarz zagadnie« odnosz¡cych si¦ do tego jak w zbiorze

liczb naturalnych s¡ rozmieszczone liczby pierwsze. Warto niektóre z nich przytoczy¢.

Twierdzenie 1. (Wielkie Twierdzenie Fermata) Dladowolnejliczbynaturalnej n>3 nie

istniej¡liczbynaturalne x;y;z takie,»e

x n +y n =z n :

(1)

Twierdzenie to zostało sformułowane w 1637 roku przez francuskiego prawnika i matematyka-

amatora Jeana Pierre’a de Fermata z Tuluzy, a rozwi¡zane w 1995 roku przez Anglika Andrew

Wilesa.

Hipoteza Goldbacha Ka»daliczbaparzystawi¦kszaod 2 jestsum¡dwóchliczbpierwszych.

Hipoteza ta została sformułowana w 1742 roku przez matematyka niemieckiego Christiana Gold-

bacha, syna protestanckiego pastora z Królewca, pracuj¡cego w Akademii w Petersburgu. Do dzisiaj

nie została potwierdzona.

Twierdzenie 2. Niech (n) b¦dzieilo±ci¡liczbpierwszychzprzedziału (1;n] .Wówczas

(1) (J.-M. Legendre) (n) n

lnn 1;08366

(2) (K. F. Gauss)

lnx dx

Ostatnie z wymienionych rezultatów jest autorstwa Karola Fryderyka Gaussa (1777-1855). Teo-

ri¦ liczb nazwał on królow¡ matematyki i orzekł, »e jest nauk¡ czyst¡ i tak pi¦kn¡, »e nie powinna

by¢ splamiona »adnymi zastosowaniami. Jest rzeczywi±cie nauk¡ pi¦kn¡, ale jej czysto±¢ została

naruszona prawie dwie±cie lat pó¹niej, gdy uczyniono z niej podstaw¦ systemów kryptograﬁcznych

maj¡cych niezwykle obszerne zastosowania we współczesnym ±wiecie, gdzie informacji nadano sta-

tus, je±li nie boga, to przynajmniej bo»ka.

Systemy pozycyjne

Deﬁnicja 1. Niech b b¦dzie liczb¡ całkowit¡ wi¦ksz¡ od 1. Klasycznym systemem pozycyjnym o

podstawie b nazywamy sposób zapisu liczb rzeczywistych nieujemnych w postaci

(a n a n1 ::: a 3 a 2 a 1 a 0 ; a 1 a 2 :::) b ;

(2)

Materiałydydaktyczne–MatematykaDyskretna(Wykład2)

gdzie a i 2f0;1;2;:::;b1g. Zapis taki oznacza liczb¦

a n b n +a n1 b n1 ++a 3 b 3 +a 2 b 2 +a 1 b+a 0 +a 1 1

b +a 2 1

b 2 + ; (3)

Liczby0;1; :::; b1nazywamy cyframi systemu o podstawie b. Pełni¡ one dwojak¡ rol¦: liczb

oraz znaków graﬁcznych. Przecinek wyst¦puj¡cy w zapisie oddziela cz¦±¢ całkowit¡ liczby od jej

cz¦±ci ułamkowej. Je»eli cz¦±¢ ułamkowa jest równa zeru, mo»na w tym zapisie zrezygnowa¢ z

przecinka i cyfr (równych0) po jego prawej stronie.

Twierdzenie 3. Niech b b¦dzieliczb¡całkowit¡, b >1 .Ka»d¡liczb¦całkowit¡ a >0 mo»naw

sposóbjednoznacznyzapisa¢wklasycznymsystemieopodstawie b ,tzn.wpostaci:

(a n a n1 ::: a 3 a 2 a 1 a 0 ) b =a n b n +a n1 b n1 ++a 3 b 3 +a 2 b 2 +a 1 b+a 0 ;

gdzie a n >0 .

Dowód. Dowód tego twierdzenia sprowadza si¦ do łatwego zastosowania indukcji matematyczn ej.

T¦ jednoznaczno±¢ zapisu liczb mo»na narusza¢ pisz¡c po nawiasie i przed a n dowoln¡ liczb¦

zer.

Przykład 1. Je±li wł¡czymy w zapis cz¦±¢ ułamkow¡, to przestaje on by¢ jednoznaczny. Wystarczy

zauwa»y¢, »e

b + b1

b 2 + b1

b 3 += b1

1+ 1 b + 1 b 2 + =

1 1 b

=1:

= b1

Zatem(0;b1b1b1:::) b =(1;000:::) b .

Przykład 2. W standardowych zastosowaniach funkcjonuje kilka podstawowych systemów pozy-

cyjnych

podstawa nazwa systemu cyfry

10 dziesi¦tny 1 0;1;2;3;4;5;6;7;8;9

2 dwójkowy 0;1

(binarny)

8 ósemkowy 0;1;2;3;4;5;6;7

(oktonalny)

16 szesnastkowy 0;1;2;3;4;5;6;7;8;9; A; B; C; D; E; F

(hexadecymalny)

60 sze±¢dziesi¦tny 0;1; :::;59

Podstawowe deﬁnicje i fakty

Mówimy »e liczba całkowita a jest dzielnikiem liczby całkowitej b (lub »e a dzieli b) i piszemy

ajb, je±li istnieje liczba całkowita c, taka »e b=ac.

Liczb¦ naturaln¡ p nazywamy liczb¡pierwsz¡ , je»eli ma ona dokładnie dwa ró»ne dzielniki

naturalne. W my±l tej deﬁnicji, liczba1nie jest liczb¡ pierwsz¡, bo ma tylko jeden taki dzielnik.

Materiałydydaktyczne–MatematykaDyskretna(Wykład2)

Lemat 4. Ka»d¡liczb¦naturaln¡wi¦kszaod 1 ,któraniejestliczb¡pierwsz¡,mo»narozło»y¢na

iloczynliczbpierwszych.Wszczególno±ciwi¦c,ka»daliczbanaturalnawi¦kszaod 1 dzielisi¦przez

pewn¡liczb¦pierwsz¡.

Lemat 5. (Twierdzenie Euklidesa) Istniejeniesko«czeniewieleliczbpierwszych.

Tu jako ciekawostk¦ mo»na doda¢, »e L. Euler przedstawił istotne wzmocnienie tego twierdzenia

dowodz¡c, »e szereg odwrotno±ci liczb pierwszych jest rozbie»ny. Warto te» wspomnie¢ nast¦pu-

j¡ce twierdzenie autorstwa Lejeune-Dirichleta. Mo»e mie¢ ono znaczenie przy analizie systemów

kryptograﬁcznych.

Twierdzenie 6. Je±li a i r niemaj¡wspólnychdzielnikówwi¦kszychod 1 ,towzbiorzeliczb

naturalnychpostaci a+nr , n 2 N istniejeniesko«czeniewieleliczbpierwszych.

W szczególno±ci wi¦c istnieje niesko«czenie wiele liczb pierwszych w zbiorach liczb ka»dej z

nast¦puj¡cych postaci:3n+1,3n+2,4n+1,4n+3,5n+1,5n+2,5n+3,5n+4.

Niech p 1 =2< p 2 =3< p 3 =5< ::: < p n < ::: b¦dzie ci¡giem kolejnych liczb pierwszych

(ka»da liczba pierwsza jest wyrazem tego ci¡gu). Z poprzedniego lematu wynika, »e ci¡g ten

jest niesko«czony. Rol¦ liczb pierwszych tłumaczy nast¦puj¡ce twierdzenie zwane zasadniczym

twierdzeniem arytmetyki liczb całkowitych.

Twierdzenie 7. Ka»d¡liczb¦całkowit¡ n ró»n¡odzeramo»nawsposóbjednoznacznyprzedstawi¢

wpostaci:

n=(1) p n 1

1 p n 2

2 p n 3

3 =(1)

p n i

i ;

i=1

gdzie 2f0;1g , n i s¡nieujemnymiliczbamicałkowitymiitylkoichsko«czonailo±¢,toliczbyró»ne

odzera.

Jednoznaczno±¢ zapisu oznacza, »e ka»da liczba n jednoznacznie okre±la oraz wszystkie wy-

kładniki n i .

Najwi¦kszymwspólnymdzielnikiem liczb a i b nazywamy najwi¦ksz¡ liczb¦ naturaln¡ NWD(a;b)=

d, tak¡ »e d jest dzielnikiem a, d jest dzielnikiem b i dzieli si¦ przez ka»dy wspólny dzielnik tych

liczb. Najwi¦kszy wspólny dzielnik liczb a i b oznaczamy symbolem NWD(a;b). Przyjmujemy,

»e NWD(0;b)=b. Liczby całkowite a i b nazywamy wzgl¦dniepierwszymi je±li ich najwi¦kszy

wspólny dzielnik jest równy1:

Najmniejsz¡wspóln¡wielokrotn¡ liczb a i b nazywamy najmniejsz¡ liczb¦ naturaln¡ e, tak¡ »e a

jest dzielnikiem e, b jest dzielnikiem e i e jest dzielnikiem ka»dej liczby, która si¦ dzieli jednocze±ni

przez a i b. Najmniejsz¡ wspóln¡ wielokrotno±¢ a i b oznaczamy symbolem NWW(a;b).

Twierdzenie 8. Niech m i n b¦d¡ustalonymiliczbamicałkowitymiró»nymiodzera:

m=(1) p m 1

2 p m 3

3 ; n=(1) p n 1

1 p n 2

2 p n 3

3 :

Wówczas

NWD(m;n)=p min(m 1 ;n 1 )

2 p min(m 3 ;n 3 )

p min(m i ;n i )

3 =

i :

i=1

Powy»sze twierdzenie podaje sposób wyznaczania najwi¦kszego wspólnego dzielnika dwóch do-

wolnych niezerowych liczb całkowitych. Jest to jednak sposób niepraktyczny, poniewa» musi by¢

poprzedzony rozkładem liczb na czynniki pierwsze, co mo»e si¦ okaza¢ niebagatelnym zadaniem.

1 p m 2

1 p min(m 2 ;n 2 )

Materiałydydaktyczne–MatematykaDyskretna(Wykład2)

Lemat 9. Niech a i b b¦d¡dowolnymiliczbamicałkowitymi, b >0 .Wówczasistniej¡liczby

całkowite q i r takie,»e

a=bq+r; gdzie 06r6b:

Twierdzenie 10. Niech a i m ( m >1 )b¦d¡dowolnymiliczbamicałkowitymiiniech d=NWD(a;m) .

Wówczasistniej¡liczbycałkowite x i y takie,»e

ax+my=d:

Wszczególno±ci,je±li a i m s¡wzgl¦dniepierwsze,toistniej¡liczbycałkowite x i y takie,»e

ax+by=1:

Algorytm Euklidesa .

Niech a i b b¦d¡ dowolnymi liczbami całkowitymi dodatnimi. Dla n=1;2;::: deﬁniujemy

kolejne wyrazy ci¡gów a n , b n , q n i r n przyjmuj¡c:

a 1 =a, b 1 =b, q 1 =ba 1 =b 1 c, r 1 =a 1 b 1 q,

a 2 =b 1 , b 2 =r 1 , q 2 =ba 2 =b 2 c, r 2 =a 2 b 2 q

. . .

a n =b n1 , b n =r n1 , q n =ba n =b n c, r n =a n b n q

Nietrudno zauwa»y¢, »e wyrazy ci¡gu fr n g s¡ nieujemne oraz r 1 > r 2 > r 3 > , o ile s¡

dodatnie. Zatem, istnieje takie n; »e r n 6=0i r n+1 =0. Wówczas NWD(a;b)=r n .

Przyjmuj¡c nieco inn¡ notacj¦ ten algorytm mo»na przedstawi¢ w dwóch krokach:

A1. Je±li b=0, to NWD(a;b)=a i algorytm zatrzymuje si¦.

A2. Podstaw r a(modb), a b, b r i wró¢ do kroku A1.

Algorytm Euklidesa jest znany od2;5tys. lat.

Rozszerzony Algorytm Euklidesa Deﬁniujemy ci¡gi fx n g, fy n g, fa n g, fb n g, fq n g, fr n g,

przy tym dla n>1cztery ostatnie s¡ takie, jak w opisanym wy»ej algorytmie Euklidesa:

x y a b q r

x 0 =1 y 0 =0 b 0 =a b

x 1 =0 y 1 =1 a 1 =b 0 b 1 =r 0 q 1 =ba 1 =b 1 c r 1 =a 1 b 1 q 1

:::

x n = y n = a n =b n1 b n =r n1 q n =ba n =b n c r n =a n b n q n

x n2 x n1 q n1 y n2 y n1 q n1

Łatw¡ indukcj¡ mo»na teraz pokaza¢, »e

x n+1 a 1 +y n+1 b 1 =r n ;

w szczególno±ci wi¦c, je±li r n+1 jest pierwsz¡ reszt¡ ró»n¡ od zera, to NWD(a;b)=r n i wobec tego

x n+1 a+y n+1 b=NWD(a;b):

Opracował: Cz. Bagi«ski

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: