Matematyka Dyskretna

Andrzej Szepietowski

25 czerwca 2002 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

i reszta jest mniejsza od dzielnika. Podobnie mo˙zemy post ˛

api ´c dla dowolnych liczb natu-

ralnych

i

pod warunkiem, ˙ze

.

Twierdzenie 1.1 Dla dowolnych liczb naturalnych

oraz

istnieje dokładnie jedna

para liczb naturalnych

i

spełniaj ˛

acych warunki:

!

#"$

nazywa si˛e ilorazem całkowitoliczbowym

przez

, a

nazywa si˛e reszt¸a z dzielenia

Zauwa˙zmy, ˙ze iloraz

jest zaokr¸agleniem w dół normalnego ilorazu

&%

(')+*

. Iloraz

całkowitoliczbowy liczb

i

b¸edziemy oznacza´c przez

-,.

/10(2

43651789

3

4

Rozdział 1. Teoria liczb

a reszt˛e przez

63

9

Przykład 1.2

)

,

!

oraz

)

63

!

, poniewa˙z

-.

oraz

$

"

.

W przypadku, gdy

i

s ˛

a liczbami całkowitymi iloraz i ró˙znice mo˙zna róznie definiowa ´c.

Na przykład w j¸ezyku Pascal iloraz dwóch liczb typu całkowitego oznacza si¸e przez

a div b

i jest to

%

6')+*

— zaokr¸aglenie ilorazu

6')

w dół, gdy

6')

jest dodatnie i

(')

, —

zaokr¸aglenie ilorazu

('

w gór¸e, gdy

(')

jest ujemne. Reszta, któr¸a oznacza si¸e przez

a mod b,

jest okre´slona wzorem:

a mod b = a-(a div b)*b.

Mamy wi¸ec, 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

Podzielno´s´c liczb

Mówimy, ˙ze liczba całkowita

dzieli liczb¸e całkowit¸a

, je˙zeli istnieje liczba całko-

wita

, taka ˙ze:

9

B¸edziemy to oznacza´c przez

. Zauwa˙zmy, ˙ze zachodzi wtedy:

63

9

Liczb¸e

nazywamy dzielnikiem liczby

.

Przykład 1.3

,

oraz

.

Lemat 1.4 Je˙zeli

oraz

, to

oraz

Dowód. Je˙zeli

i

, to istniej¸a dwie liczby całkowite

i

, takie ˙ze:

oraz

9

Mamy wi¸ec:

oraz

czyli

dzieli

oraz

.

1.3. Relacja kongruencji

5

1.3

Relacja kongruencji

Niech

b¸edzie dowoln¸a liczb¸a naturaln¸a

. Powiemy, ˙ze dwie liczby całkowite

i

s¸a równowa˙zne (lub przystaj¸a) modulo

, je˙zeli

9

B¸edziemy wtedy pisa´c:

63

9

Przykład 1.5

63

,

63

,

63

,

63

.

Je˙zeli

i

s ˛

a dodatnie, to

63

wtedy i tylko wtedy, gdy

i

maj ˛

a takie

same reszty z dzielenia przez

.

Lemat 1.6 Relacja przystawania modulo jest relacj¸a równowa˙zno´sci, czyli spełnia nast¸epuj¸ace
trzy warunki:

zwrotno´

s´

c, dla ka˙zdego

zachodzi

63

,

symetri¸e, dla ka˙zdego

i

, je˙zeli

63

to

63

,

przechodnio´

s´

c, dla ka˙zdego

,

i

,

je˙zeli

63

i

63

to

63

.

Dowód. Udowodnimy tylko przechodnio´s´c relacji. Je˙zeli

oraz

to

czyli

.

Ponadto relacja modulo jest zgodna z dodawaniem, odejmowaniem i mno˙zeniem.

Twierdzenie 1.7 Je˙zeli

3

oraz

3

to:

63

3

63

9

Dowód. Z zało˙zenia mamy:

z tego za´s łatwo wynika, ˙ze

dzieli:

oraz

!

czyli zachodzi teza twierdzenia.

Przykład 1.8 Twierdzenie 1.7 mo˙ze by´c u˙zyte do obliczania reszty z dzielenia Je˙zeli chce-
my policzy´c na przykład

63

6

Rozdział 1. Teoria liczb

to pytamy, która z trzech liczb

przystaje do 1999 modulo 3. Zróbmy najpierw

kilka prostych obserwacji. Po pierwsze:

63

bo

. Z twierdzenia 1.7 wynika, ˙ze ka˙zda pot¸ega liczby dziesi¸e´c przystaje do 1

modulo 3, czyli:

3

dla ka˙zdego

. Mamy teraz:

)8

)84

63

9

Podobnie, dla dowolnej liczby

, je˙zeli zapiszemy

w postaci dziesi¸etnej:

to

63

czyli

ma takie same reszty modulo 3 co suma cyfr w zapisie dziesi¸etnym.

Przykład 1.9 Aby przekona´c si˛e, ˙ze

)8

(

wystarczy zauwa˙zy´c, ˙ze liczba

jest parzysta, wi˛ec tak˙ze wynik mno˙zenia powinien

by˙z parzysty. Mówi ˛

ac inaczej

)

63

oraz

63

, wi˛ec na

podstawie twierdzenia 1.7 mamy

63

, a liczba

(

przystaje

do jedynki modulo 2. Podobnie mo˙zemy si˛e przekona´c, ˙ze

)8

(

wystarczy zauwa˙zy´c, ˙ze w iloczynie

)#

ostatni ˛

a cyfr ˛

a powinno by´c 8 a nie 6.

Inaczej

63

oraz

3

, wi˛ec na podstawie twierdze-

nia 1.7 mamy

.

63

, a liczba

)

przystaje do 6 modulo

10.

1.4

Klasy abstrakcji

Dla relacji przystawania modulo

definiujemy klasy abstrakcji. Dla dowolnej liczby

całkowitej

, klas¸e abstrakcji elementu

definiujemy w nast¸epuj¸acy sposób:

3

9

Innymi słowy, klasa abstrakcji liczby

to zbiór wszystkich liczb z ni¸a równowa˙znych.

Przykład 1.10 Dla

mamy trzy klasy abstrakcji

1.5. Pier´scie´n

7

9

99

9

99

99

9

9

99

99

9

)

9

99

Zauwa˙zmy, ˙ze klasy abstrakcji elementów równowa˙znych pokrywaj¸a si¸e.

Lemat 1.11 Je˙zeli

63

to

.

Dowód. Je˙zeli

to

63

i z przechodnio´sci relacji

63

, czyli:

a wi¸ec pokazali´smy, ˙ze:

9

Identycznie pokazujemy zawieranie odwrotne

.

Nast¸epna wa˙zna własno´s´c klas abstrakcji to ich rozł¸aczno´s´c.

Lemat 1.12 Je˙zeli

to

,

inaczej, dwie klasy abstrakcji

i

albo s¸a identyczne, albo s¸a rozł¸aczne.

Dowód. Przypu´s´cmy, ˙ze klasy

i

maj¸a wspólny element

. Wtedy:

63

63

9

Z przechodnio´sci mamy wtedy

63

, a z lematu 1.11

.

1.5

Pier´scie ´n

Klasy abstrakcji relacji modulo

wygl¸adaj¸a nast¸epuj¸aco:

99

9

9

Dla dowolnego

z przedziału

#

, klasa

jest postaci:

(

oznacza zbiór liczb całkowitych). Zbiór klas abstrakcji modulo

oznacza si¸e przez

.

Poniewa˙z relacja modulo jest zgodna z działaniami dodawania i mno˙zenia, mo˙zemy

zdefiniowa´c dodawanie i mno˙zenie na klasach abstrakcji. Mówi¸ac w skrócie, aby wyko-
na´c działanie na dwóch klasach abstrakcji, wybieramy dowolnych przedstawicieli tych

8

Rozdział 1. Teoria liczb

klas i wykonujemy działania na tych przedstawicielach. Dokładniej, dodawanie klas abs-
trakcji definiujemy nast¸epuj¸aco:

9

Podobnie definiujemy odejmowanie i mno˙zenie:

9

Poni˙zszy lemat pokazuje, ˙ze działania te s¸a dobrze zdefiniowane; ˙ze wynik działania na
dwóch klasach nie zale˙zy od wyboru reprezentantów.

Lemat 1.13 Je˙zeli

oraz

to:

9

Dowód. Z zało˙zenia mamy:

63

63

9

a z twierdzenia 1.7:

oraz

9

Przykład 1.14 Niech

. Dla dowolnych dwóch liczb

i

ich suma

nale˙zy do

a iloczyn do

)

.

Lemat 1.15 Działania na klasach abstrakcji

9

99

spełniaj¸a nast¸epuj¸ace warunki:

dodawanie oraz mno˙zenie s¸a przemienne i ł¸aczne,

klasa

jest elementem neutralnym dodawania, to znaczy dla ka˙zdego

mamy

,

dla ka˙zdej klasy

istnieje klasa do niej przeciwna

8

, taka ˙ze

8

,

klasa

jest elementem neutralnym mno˙zenia, to znaczy dla dowolnego

mamy

,

mno˙zenie jest rozdzielne wzgl¸edem dodawania, czyli dla ka˙zdych trzech klas

,

,

mamy

.

Zbiór z dwoma działaniami spełniaj¸acymi powy˙zsze warunki nazywa si¸e pier´scieniem
przemiennym z jedynk¸a.

1.5. Pier´scie´n

9

Dowód: Udowodnimy tylko rozdzielno´s´c:

9

Skorzystali´smy w tym dowodzie z rozdzielno´sci mno˙zenia wzgl¸edem dodawania dla liczb
całkowitych.

Przykład 1.16 Rozwa˙zmy zbiór reszt modulo 5. Składa si¸e on z pi¸eciu klas:

dla prostoty b¸edziemy dalej opuszcza´c nawiasy. Mamy wi¸ec zbiór:

z dodawaniem i mno˙zeniem okre´slonym nast¸epuj¸acymi tabelami:

+

0

1

2

3

4

0

0

1

2

3

4

1

1

2

3

4

0

2

2

3

4

0

1

3

3

4

0

1

2

4

4

0

1

2

3

0

1

2

3

4

0

0

0

0

0

0

1

0

1

2

3

4

2

0

2

4

1

3

3

0

3

1

4

2

4

0

4

3

2

1

Zauwa˙zmy, ˙ze ka˙zdy element oprócz zera ma w

element odwrotny wzgl¸edem mno˙zenia,

czyli dla ka˙zdego

istnieje

taki ˙ze

:

9

Dlatego

jest ciałem, czyli pier´scieniem przemiennym z jedynk¸a i z odwrotno´sci¸a wzgl¸edem

mno˙zenia.

Przykład 1.17 Rozwa˙zmy teraz pier´scie´n reszt modulo 4:

gdzie dodawanie i mno˙zenie jest okre´slone nast¸epuj¸acymi tabelami:

+

0

1

2

3

0

0

1

2

3

1

1

2

3

0

2

2

3

0

1

3

3

0

1

2

0

1

2

3

0

0

0

0

0

1

0

1

2

3

2

0

2

0

2

3

0

3

2

1

nie jest ciałem, poniewa˙z nie ma w nim elementu odwrotnego do 2. Ponadto w

mamy:

-

czyli zero mo˙zna przedstawi´c jako iloczyn dwóch liczb ró˙znych od zera.

10

Rozdział 1. Teoria liczb

Łatwo zauwa˙zy´c, ˙ze je˙zeli liczba

jest zło˙zona,

dla

"

"

, to w

pier´scieniu

mamy

i ani , ani

nie maj¸a elementów odwrotnych. Przypu´s´cmy

bowiem, ˙ze istnieje

. Mamy wtedy:

czyli

, sprzeczno´s´c. Tak wi¸ec

nie jest ciałem, je˙zeli

jest liczb¸a zło˙zon¸a.

W dalszej cz¸e´sci tego rozdziału zobaczymy, ˙ze je˙zeli

jest liczb¸a pierwsz¸a, to

jest

ciałem.

1.6

Najwi¸ekszy wspólny dzielnik

Dla dwóch liczb całkowitych

i

, ich najwi¸ekszy wspólny dzielnik to po prostu najwi¸eksza

liczba całkowita

, która dzieli

i

. Najwi¸ekszy wspólny dzielnik liczb

i

b¸edziemy

oznacza´c przez

. Na przykład:

,

.

1.7

Algorytm Euklidesa

Najwi¸ekszy wspólny dzielnik dwóch liczb dodatnich mo˙zna obliczy ´c za pomoc¸a algoryt-
mu Euklidesa.

Algorytm Euklidesa. Aby obliczy´c najwi¸ekszy wspólny dzielnik dwóch dodatnich liczb
naturalnych

,

, powtarzamy a˙z do skutku:

je˙zeli

, to koniec,

,

je˙zeli

, to

,

je˙zeli

"

, to

.

Powy˙zszy algorytm odejmuje od wi¸ekszej liczby mniejsz¸a tak długo, a˙z liczby b¸ed¸a rów-
ne. Wtedy wynikiem działania algorytmu jest wspólna warto´s´c tych liczb. W uproszczo-
nej wersji j¸ezyka Pascal algorytm Euklidesa mo˙zna zapisa´c w nast¸epuj¸acy sposób:

p:=a;q:=b;

while p<>q do

if p>q then p:=p-q

else q:=q-p;

NWD(a,b):=p

W poni˙zszej tabeli pokazano kolejne kroki działania algorytmu Euklidesa na parze

liczb 36 i 15:

1.7. Algorytm Euklidesa

11

36

15

21

15

6

15

6

9

6

3

3

3

Tak wi¸ec 3 jest najwi¸ekszym wspólnym dzielnikiem liczb 15 i 36.

Poprawno´s´c algorytmu Euklidesa wynika z poni˙zszego lematu.

Lemat 1.18 Niech

i

b¸ed¸a dwoma liczbami naturalnymi i niech

"

"

. Wtedy

para

ma taki sam zbiór wspólnych dzielników jak para

,

.

Dowód. Je˙zeli liczba

jest wspólnym dzielnikiem pary

, to

dzieli tak˙ze

, czyli

jest wspólnym dzielnikiem pary

,

.

Na odwrót, je˙zeli liczba

jest wspólnym dzielnikiem pary

,

, to

dzieli tak˙ze

, czyli

jest wspólnym dzielnikiem pary

.

Tak wi¸ec po ka˙zdej iteracji p¸etli

while

para

ma taki sam zbiór wspólnych dziel-

ników, a wi¸ec tak˙ze taki sam najwi¸ekszy wspólny dzielnik. Na ko ´ncu, gdy

, wów-

czas oczywi´scie

.

Nale˙zy jeszcze pokaza´c, ˙ze dla ka˙zdej pary dodatnich liczb naturalnych

i

algorytm

zatrzyma si¸e. Ale to wynika z faktu, ˙ze po ka˙zdej iteracji p¸etli

while

liczba

jest coraz mniejsza, a poniewa˙z jest to zawsze liczba naturalna dodatnia, wi¸ec nie mo˙ze
zmniejsza´c si¸e w niesko ´nczono´s´c. Zauwa˙zmy przy okazji, ˙ze je˙zeli jedna z dwóch liczb,

lub

, jest zerem, to algorytm nie zatrzyma si¸e.

Twierdzenie 1.19 Niech

i

b¸ed¸a dwoma dodatnimi liczbami naturalnymi i niech

. Wtedy istniej¸a liczby całkowite

i

, takie ˙ze:

(

lub mówi¸ac inaczej,

jest kombinacj¸a całkowitoliczbow¸a liczb

i

.

Dowód. Poka˙zmy, ˙ze wszystkie warto´sci, jakie przyjmuj¸a zmienne

i

w trakcie wy-

konywania algorytmu Euklidesa, s¸a całkowitoliczbowymi kombinacjami liczb

i

. Na

pocz¸atku, gdy

i

, mamy:

9

Załó˙zmy teraz, ˙ze po

-tej iteracji p¸etli

$

oraz ˙ze zachodzi:

)

9

Wtedy w

iteracji

b¸edzie pomniejszone o

i b¸edziemy mieli:

9

Z tego wynika, ˙ze tak˙ze ostateczna warto´s´c zmiennej (która jest równa

) jest całkowitoliczbow¸a

kombinacj¸a liczb

i

.

12

Rozdział 1. Teoria liczb

Algorytm Euklidesa mo˙zna tak zmodyfikowa´c, aby oprócz najwi¸ekszego wspólnego

dzielnika

, wyliczał tak˙ze liczby

i

, takie ˙ze:

(

9

Oto ten algorytm w j¸ezyku Pascal:

p:=a;q:=b;

xp:=1;yp:=0;

xq:=0;yq:=1;

while p<>q do

if p>q then

begin

p:=p-q;

xp:=xp-xq;

yp:=yp-yq

end

else

begin

q:=q-p;

xq:=xq-xp;

yq:=yq-yp

end;

NWD(a,b):=p;

x:=xp,y:=yp

W poni˙zszej tabeli pokazano kolejne kroki działania rozszerzonego algorytmu Eukli-

desa na parze liczb 36 i 15:

6

36

15

1

0

0

1

21

15

1

-1

0

1

6

15

1

-2

0

1

6

9

1

-2

-1

3

6

3

1

-2

-2

5

3

3

3

-7

-2

5

Tak wi¸ec liczb¸e 3 mo˙zna przedstawi´c jako kombinacj¸e liczb 15 i 36 w nast¸epuj¸acy sposób:

)

9

Zauwa˙zmy, ˙ze je˙zeli jaka´s liczba

dzieli liczby

i

, to dzieli tak˙ze ka˙zd¸a ich kombinacj¸e

całkowit¸a

(

a wi¸ec dzieli tak˙ze najwi¸ekszy wspólny dzielnik

. Udowodnili´smy poni˙zszy

lemat.

1.8. Liczby pierwsze i wzgl¸ednie pierwsze

13

Lemat 1.20

jest podzielny przez ka˙zdy wspólny dzielnik liczb

i

.

Z lematu 1.20 wynika, ˙ze najwi¸ekszy wspólny dzielnik

mo˙ze by ´c rów-

nowa˙znie zdefiniowany jako taki wspólny dzielnik liczb

i

, który jest podzielny przez

ka˙zdy wspólny dzielnik

i

.

Lemat 1.21 Liczba

jest najwi¸ekszym wspólnym dzielnikiem liczb

i

wtedy i tylko

wtedy gdy

b¸edzie wspólnym dzielnikiem

i

oraz istniej¸a liczby całkowite

i

, takie

˙ze

!

(

.

Dowód Je˙zeli

to

,

oraz (z twierdzenia 1.19) istniej¸a liczby całko-

wite

i

, takie ˙ze:

!

(

.

Na odwrót, je˙zeli

dzieli

i

oraz

(

, to ka˙zdy wspólny dzielnik

i

dzieli

, a wi¸ec

jest najwi¸ekszym wspólnym dzielnikiem

i

.

Wniosek 1.22 Je˙zeli istniej¸a liczby całkowite

i

, takie, ˙ze

(

, to

.

Przykład 1.23 Zastanówmy si¸e, ile wynosi

)

. Poniewa˙z:

)

oraz 2 jest wspólnym dzielnikiem 1998 i 2000, wi¸ec

)

.

Zastanówmy si¸e teraz, ile wynosi

))(

. Poniewa˙z:

))

wi¸ec

))

dzieli 2, a poniewa˙z 2 nie dzieli ani 1999, ani 2001, wi¸ec

(

.

1.8

Liczby pierwsze i wzgl¸ednie pierwsze

Dwie liczby naturalne

i

s ˛

a wzgl¸ednie pierwsze, je˙zeli

, a liczba

naturalna

jest pierwsza, je˙zeli

i jedynymi dzielnikami naturalnymi

s¸a jedynka i

samo .

Oto wszystkie liczby pierwsze mniejsze od 50:

)

)

(

)

9

Liczba

, która nie jest pierwsza jest zło˙zona. Istniej ˛

a wtedy dwie liczby

,

"

,

takie, ˙ze

.

1.9

Rozkład liczb na czynniki pierwsze

W tym rozdziale zobaczymy, ˙ze ka˙zd¸a liczb¸e naturaln¸a

mo˙zna rozło˙zy ´c na czynniki

pierwsze i ˙ze taki rozkład jest jednoznaczny z dokładno´sci¸a do kolejno´sci czynników. Na
przykład:

i

)

9

14

Rozdział 1. Teoria liczb

Twierdzenie 1.24 Ka˙zd¸a liczb¸e naturaln¸a

mo˙zna przedstawi´c jako iloczyn liczb

pierwszych (niekoniecznie ró˙znych):

9

Dowód nie wprost. Przypu´s´cmy, ˙ze istnieje liczba naturalna

, której nie mo˙zna przed-

stawi´c jako iloczynu liczb pierwszych i ˙ze

jest najmniejsz¸a tak¸a liczb¸a.

nie mo˙ze by ´c

liczb¸a pierwsz¸a (bo wtedy

), wi¸ec

jest liczb¸a zło˙zon¸a, czyli jest postaci:

dla

"

. Ale poniewa˙z

i

s¸a mniejsze od

, wi¸ec mo˙zna je rozło˙zy ´c na czynniki

pierwsze

ale wtedy, wbrew zało˙zeniu, mamy rozkład liczby

na czynniki pierwsze:

9

Aby pokaza´c, ˙ze rozkład jest jednoznaczny (z dokładno´sci¸a do kolejno´sci czynników),

musimy najpierw udowodni´c dwa lematy.

Lemat 1.25 Niech

i

b¸ed¸a dodatnimi wzgl¸ednie pierwszymi liczbami naturalnymi.

Wtedy dla dowolnej liczby

, je˙zeli

, to

.

Dowód. Z twierdzenia 1.19, istniej¸a dwie liczby całkowite

i

, takie ˙ze:

6

9

Pomnó˙zmy teraz obie strony tego równania przez

:

(

i zauwa˙zmy, ˙ze

dzieli oba składniki po lewej stronie równania, a wi¸ec dzieli praw¸a

stron¸e, czyli

.

Lemat 1.26 Je˙zeli liczba pierwsza

dzieli iloczyn liczb pierwszych

(niekoniecznie ró˙znych), to wtedy

jest równe jednej z liczb

.

Dowód przez indukcj¸e ze wzgl¸edu na

. Dla

mamy

, a poniewa˙z

jest

pierwsza i

, wi¸ec

.

Załó˙zmy teraz, ˙ze teza zachodzi dla

i przypu´s´cmy, ˙ze

dzieli

9

Mamy dwa przypadki: albo

dzieli

, albo nie. W pierwszym przypadku

.

W drugim przypadku mamy

, bo 1 i

to jedyne dzielniki liczby

. Z lematu 1.25 wynika teraz, ˙ze

dzieli

a z zało˙zenia indukcyjnego, ˙ze

dla jakiego´s

4

.

.

1.10. Elementy odwracalne

15

Udowodnimy teraz, ˙ze rozkład liczby na czynniki pierwsze jest jednoznaczny, z dokładno´sci¸a
do kolejno´sci czynników.

Twierdzenie 1.27 Ka˙zd¸a liczb¸e naturaln¸a

mo˙zna w dokładnie jeden sposób przed-

stawi´c w postaci iloczynu:

9

99

gdzie

s¸a dodatnimi liczbami naturalnymi,

s¸a liczbami pierwszymi oraz zachodzi

"

"

99

9("

.

Dowód. Twierdzenie 1.24 orzeka, ˙ze liczba ma rozkład na czynniki pierwsze. Trzeba
pokaza´c, ˙ze jest to rozkład jednoznaczny.

jako liczba pierwsza ma jednoznaczny

rozkład. Przypu´s´cmy, ˙ze

jest najmniejsz¸a liczb¸a z dwoma ró˙znymi rozkładami:

999

99

9

9

(1.1)

Wtedy z jednej strony

nie mo˙ze wyst¸epowa´c po prawej stronie równania (1.1), bo

'

byłoby mniejsz¸a liczb¸a z niejednoznacznym rozkładem. Z drugiej strony

dzieli praw¸a

stron¸e, a wi¸ec, z lematu 1.26 wyst¸epuje po prawej stronie. Mamy wi¸ec sprzeczno´s´c.

Lemat 1.28 Je˙zeli

i

s¸a wzgl¸ednie pierwsze, to ich rozkłady s¸a rozł¸aczne, to znaczy

maj¸a rozł¸aczny zbiór liczb pierwszych wyst¸epuj¸acych w ich rozkładach.

1.10

Elementy odwracalne

Definicja 1.29 Element

jest odwracalny, je˙zeli istnieje

, takie, ˙ze

63

9

nazywamy elementem odwrotnym do

i oznaczamy przez

.

Przykład 1.30

jest odwracalna w

bo

3

. Oprócz 3 w

odwra-

calne s ˛

a tak˙ze ,

i

.

Lemat 1.31 Liczba

jest odwracalna wtedy i tylko wtedy, gdy

.

Dowód. Je˙zeli

, to istniej¸a liczby całkowite

i

, takie ˙ze:

a wi¸ec

dzieli

, czyli:

63

9

Teraz wystarczy przyj¸a´c za

tak¸a liczb¸e z przedziału od 1 do

, która przystaje

do

modulo

.

Z drugiej strony je˙zeli istnieje element

odwrotny do

to

63

16

Rozdział 1. Teoria liczb

czyli

dla jakiego´s

. Mamy wi¸ec

czyli

(wniosek 1.22).

Z powy˙zszego dowodu wynika, ˙ze element odwrotny do

mo˙zna wyliczy ´c stosuj¸ac

algorytm Euklidesa. Na przykład policzmy element odwrotny do 12 w pier´scieniu

.

Najpierw zastosujemy algorytm Euklidesa, aby obliczy´c

i

, takie ˙ze:

9

Kolejne kroki algorytmu przedstawiono w tabeli:

6

17

12

1

0

0

1

5

12

1

-1

0

1

5

7

1

-1

-1

2

5

2

1

-1

-2

3

3

2

3

-4

-2

3

1

2

5

-7

-2

3

Mamy wi¸ec:

-)

czyli:

63

ale:

3

czyli 10 jest elementem odwrotnym do 12 w pier´scieniu

.

Definicja 1.32 Zbiór elementów odwracalnych w

oznaczamy przez

.

Przykład 1.33

.

Lemat 1.34 Je˙zeli liczba

jest pierwsza, to ka˙zdy element

,

, jest odwra-

calny, czyli pier´scie´n

jest ciałem.

Lemat 1.35 Je˙zeli

to

oraz

.

To oznacza, ˙ze

z mno˙zeniem jest grup¸a.

Dowód: Elementem odwrotnym do iloczynu

6

jest

, a elementem odrotnym do

jest

.

1.11. Funkcja liniowa

17

1.11

Funkcja liniowa

Zastanówmy si¸e jak w pier´scieniu

działa funkcja liniowa

63

9

Rozpatrzmy najpierw przypadek, gdy

i

s¸a wzgl¸ednie pierwsze, czyli gdy

. Dla

i

warto´sci funkcji przedstawia tabela

x

0

1

2

3

4

5

6

7

3x

0

3

6

1

4

7

2

5

W takim przypadku istnieje

element odwrotny do

i funkcja

, która

jest odwrotna do . Rzeczywi´scie

9

Z tego wynika, ˙ze

jest wzajemnie jednoznaczna i "na" oraz, ˙ze dla ka˙zdego

równanie

ma dokładnie jedno rozwi¸azanie w pier´scieniu

, jest ono równe

.

Funkcja

jest permutacj¸a w

i wykorzystuje si¸e j¸a, gdy trzeba wymiesza´c (prze-

permutowa´c) elementy

. Zauwa˙zmy, ˙ze

jest tak˙ze permutacj ˛

a w

. Rzeczywi´scie,

je˙zeli

, to na podstawie lematu 1.35

. Mamy wi¸ec

Lemat 1.36 Je˙zeli

, to funkcja

jest funkcj¸a wzajemnie

jednoznaczn¸a w

i w

.

Rozpatrzmy teraz przypadek, gdy

i

nie s¸a wzgl¸ednie pierwsze, czyli gdy

. Dla

i

warto´sci funkcji przedstawia tabela

x

0

1

2

3

4

5

6

7

6x

0

6

4

2

0

6

4

2

Zauwa˙zmy, ˙ze je˙zeli

jest warto´sci¸a funkcji , czyli gdy

63

to istnieje takie

, ˙ze

a poniewa˙z

dzieli

i

, to

dzieli

, a wi¸ec warto´sciami funkcji

mog¸a by´c tylko

liczby podzielne przez

.

Lemat 1.37 Je˙zeli

oraz

, to równania

63

oraz

('

'

63

'

s¸a równowa˙zne, czyli maj¸a ten sam zbiór rozwi¸aza´n w zbiorze liczb całkowitych.

18

Rozdział 1. Teoria liczb

Dowód

3

wtedy i tylko wtedy, gdy istnieje

takie ˙ze

a to zachodzi wtedy i tylko wtedy, gdy istnieje

takie, ˙ze

('

'

'

czyli wtedy i tylko wtedy, gdy

('

'

63

'

9

Przypu´s´cmy teraz, ˙ze

dzieli

i rozwi¸a˙zmy równanie

(1.2)

w pier´scieniu

, czyli szukamy takich

99

9

, ˙ze

3

(1.3)

Z lematu 1.37, to równanie jest równowa˙zne równaniu

('

'

63

'

(1.4)

Ale teraz

('

'

i równanie (1.4) ma dokładnie jedno rozwi¸azanie

99

9

'

takie ˙ze

('

'

3

'

9

Ale równania (1.4) i (1.3) s¸a spełnione tak˙ze przez liczby

'

.

'

99

9

'

9

S¸a to wszystkie liczby ze zbioru

9

99

spełniaj¸ace równania (1.4) i (1.3), czyli

wszystkie rozwi¸azania równania (1.2) w pier´scieniu

.

Przykład 1.38 Rozwi¸a˙zmy równanie

63

9

(1.5)

Poniewa˙z

, wi¸ec najpierw rozwi¸azujemy równanie

63

W

mamy

wi¸ec rozwi¸azaniem jest

. Tak wi¸ec rozwi¸azaniami

równaia (1.5) w

s¸a liczby

9

1.12. Szyfry liniowe

19

1.12

Szyfry liniowe

Przypu´s´cmy, ˙ze mamy tekst zapisany za pomoc¸a 26 liter alfabetu łaci ´nskiego:

i chcemy ten tekst zaszyfrowa´c. W tym celu uto˙zsamiamy zbiór liter z elementami pier-
´scienia

:

9

99

wybieramy dwie liczby

, takie ˙ze

, i szyfrujemy litera po

literze według wzoru:

3

9

Funkcja deszyfruj¸aca jest okre´slona wzorem:

63

9

Rzeczywi´scie:

9

Z tego wynika, ˙ze funkcja szyfruj¸aca

jest wzajemnie jednoznaczna.

Przykład 1.39 Wybierzmy

i

)

i zaszyfrujmy słowo

6

9

W tym celu musimy zaszyfrowa´c 6 liter:

,

,

, ,

oraz

. Obliczenia przedstawiono w

tabeli:

litera

szyfr

m

12

10

k

a

0

20

u

t

19

15

p

e

4

8

i

y

24

0

a

k

10

16

q

Słowo

6

po zaszyfrowaniu wygl¸ada tak:

9

Je˙zeli za´s zastosujemy ten sam szyfr do pocz¸atkowego zdania z wiersza Lokomotywa Ju-
liana Tuwima:

stoi na stacji lokomotywa,

to otrzymamy:

spewhuspuotwneqekepagu.

20

Rozdział 1. Teoria liczb

A oto program w j¸ezyku Pascal, który szyfruje teksty zapisane za pomoc¸a 26 liter alfabetu
łaci´nskiego:

var

t:string;

a,b,i,m:integer;

begin

writeln(’podaj klucz’);

write(’a=’);

readln(a);

write(’b=’);

readln(b);

writeln(’podaj tekst do zaszyfrowania’);

readln(t);

for i:=1 to length(t) do

begin

m:=((ord(t[i])-97)*a+b)mod(26)+97;

write(chr(m))

end

end.

Komentarz. Zmienna

t

jest typu

string

, czyli ła ´ncuch. Tak¸a zmienn¸a mo˙zna traktowa´c

jak tablic¸e z indeksami od 1 do

length(t)

i z warto´sciami typu

char

(znak). Zmienne

typu

char

s¸a przechowywane w jednym bajcie i mog¸a zawiera ´c jeden znak. List¸e znaków

wraz z odpowiadaj¸acymi im numerami (od 0 do 255) zawiera tak zwany kod ASCII. Małe
litery alfabetu łaci ´nskiego maj¸a tam numery od 97 —

a

, do 122 —

z

.

Instrukcja

readln(t)

czyta z klawiatury tekst do zaszyfrowania i zapisuje go do zmiennej

t

. Elementy tablicy

t[i]

, dla

i

od 1 do

length(t)

, zawieraj¸a poszczególne znaki naszego tekstu.

Funkcja

ord

przypisuje znakom ich numery w kodzie ASCII, a funkcja

chr

działa

na odwrót, przypisuje znak numerowi. P¸etla

for

, dla ka˙zdego znaku tekstu

t

po kolei,

wylicza numer tego znaku po zakodowaniu:

m:=((ord(t[i])-97)*a+b)mod(26)+97,

a nast¸epnie drukuje zakodowany znak na ekranie:

write(chr(m)).

Klucz do kodowania przechowywany jest w postaci dwóch liczb,

a

i

b,

typu integer.

Szyfry liniowe s¸a bardzo starym wynalazkiem. W prostszej wersji z

sto-

sował je ju˙z Juliusz Cezar. Ich wad¸a jest to, ˙ze bardzo łatwo daj¸a si¸e łama ´c. Czasami
wystarcza odgadn¸a´c, jak zaszyfrowano dwie litery. Mo˙zna to zrobi´c analizuj¸ac cz¸esto´sci
wyst¸epowania liter w zaszyfrowanym tek´scie.

Przykład 1.40 (kontynuacja przykładu 1.39) W naszym drugim zaszyfrowanym tek´scie
litera wyst¸epuje cztery razy, a litery i

po trzy razy. Mo˙ze to nam pomóc w odgadni¸eciu,

1.13. Chi ´nskie twierdzenie o resztach

21

˙ze litera

koduje liter¸e

, a litera

koduje liter¸e

. Mamy wi¸ec dwa równania:

63

63

9

Po odj¸eciu tych równa´n stronami mamy:

63

9

Korzystaj¸ac z algorytmu Euklidesa, mo˙zemy teraz wyliczy´c element odwrotny do 5 w pier-
´scieniu

. Jest to 21, poniewa˙z:

.

oraz

(

63

tak wi¸ec:

(

)

(8

63

9

Teraz z drugiego równania mo˙zemy wyliczy´c

:

-

63

9

1.13

Chi ´nskie twierdzenie o resztach

W staro˙zytnych Chinach generałowie u˙zywali pewnego ciekawego sposobu liczenia swo-
ich ˙zołnierzy. Dla kilku niewielkich liczb parami wzgl¸ednie pierwszych, na przykład dla:

obliczano i zapami¸etywano reszty z dzielenia liczby ˙zołnierzy przez te liczby. W celu
obliczenia reszt kazano ˙zołnierzom ustawi´c si¸e trójkami, pi¸atkami i siódemkami. Je˙zeli
przy nast¸epnym apelu wszystkie trzy reszty były takie same, to znaczyło, ˙ze nie brakuje

˙zadnego ˙zołnierza.

Zobaczmy, jak ten sposób działa. We´zmy najpierw dwie liczby:

9

W poni˙zszej tabeli mamy zestawione reszty modulo 2 i 3 liczb od 0 do 5:

a

63

3

0

0

0

1

1

1

2

0

2

3

1

0

4

0

1

5

1

2

22

Rozdział 1. Teoria liczb

Ka˙zda z liczb od 0 do

.

ma inny zestaw reszt oraz dla ka˙zdej pary reszt

, spełniaj¸acych warunek

"

,

"

, istnieje liczba

, taka ˙ze:

63

63

9

Oczywi´scie 6 ma takie same reszty jak 0:

63

63

i ogólnie, je˙zeli dwie liczby

i

ró˙zni¸a si¸e o wielokrotno´s´c liczby

-

, czyli:

dla jakiego´s całkowitego

, to

63

63

63

63

9

Z tego wida´c, ˙ze sposób chi ´nskich generałów, z liczbami 2 i 3, liczy ˙zołnierzy z dokładno´sci¸a
do pi¸eciu.

Sytuacja jest inna, je˙zeli

i

nie s¸a wzgl¸ednie pierwsze. Je˙zeli, na przykład,

i

, to w´sród liczb od 0 do

)

istniej¸a takie, które maj¸a takie

same reszty, na przykład 1 i 13:

63

3

63

3

9

Ponadto nie istnieje taka liczba

, dla której:

63

63

9

Rzeczywi´scie, z pierwszej równo´sci wynika, ˙ze

powinno by´c nieparzyste, a z drugiej,

˙ze parzyste.

Je˙zeli jednak

i

s¸a wzgl¸ednie pierwsze, to ka˙zda z liczb od 0 do

ma

inny zestaw reszt oraz dla ka˙zdej pary reszt

, spełniaj¸acych warunek

"

,

#

"

, istnieje liczba

, taka ˙ze:

63

63

zachodzi bowiem poni˙zsze twierdzenie.

Twierdzenie 1.41 (chi ´

nskie twierdzenie o resztach) Niech

999

b¸ed¸a dodatnimi liczbami wzgl¸ednie pierwszymi, to znaczy dla ka˙zdej pary

"

mamy

, oraz niech

999

1.13. Chi ´nskie twierdzenie o resztach

23

b¸ed¸a dowolnymi resztami. Wtedy istnieje liczba całkowita

, taka ˙ze:

63

63

(1.6)

9

99

3

9

Ponadto je˙zeli liczby

i

s¸a rozwi¸azaniami układu kongruencji (1.6), to ich ró˙znica

dzieli si¸e przez iloczyn wszystkich liczb

, czyli przez:

9

Dowód. Najpierw udowodnimy drug¸a cz¸e´s´c twierdzenia. Dla ka˙zdego

mamy:

63

3

9

Po odj¸eciu stronami tych dwóch równa ´n mamy:

3

czyli

wi¸ec ka˙zda spo´sród liczb

dzieli

!

, a skoro liczby

99

9

s¸a wzgl¸ednie pierwsze,

wi¸ec tak˙ze ich iloczyn

dzieli

. Rzeczywi´scie, przypu´s´cmy bowiem, ˙ze

ma

rozkład

9

We´zmy teraz dowolne

. Poniewa˙z rozkłady liczb

99

9

s¸a rozł¸aczne, wi¸ec

wyst˛epuje w rozkładzie jakiego´s

, czyli dzieli

oraz

, a wi¸ec w rozkładzie

liczby

, liczba

wyst¸epuje z wykładnikiem

. Dlatego

dzieli

.

Zobaczymy teraz, ˙ze układ (1.6) ma rozwi¸azanie. Niech

'

, czyli:

999

9

Poniewa˙z

i

maj¸a rozł¸aczne rozkłady, wi¸ec

oraz istnieje

,

takie ˙ze:

63

9

We´zmy teraz:

9

Zauwa˙zmy, ˙ze je˙zeli

, to

, oraz:

63

co daje:

3

dla ka˙zdego

, a wi¸ec

jest rozwi¸azaniem układu równa ´n (1.6).

24

Rozdział 1. Teoria liczb

Przykład 1.42 Ka˙zda z liczb od 0 do

!

ma inny zestaw reszt wzgl¸edem

liczb 3, 5 i 7. Tak wi¸ec stosuj¸ac sposób chi´nskich generałów z liczbami 3, 5, 7 mo˙zemy
liczy´c ˙zołnierzy z dokładno´sci¸a do 104.

Ale sposób chi´nskich generałów pozwala tak˙ze stwierdzi´c, o ile zmieniła si¸e liczba

˙zołnierzy. Przypu´s´cmy bowiem, ˙ze na porannym apelu było

˙zołnierzy i uzyskano reszty:

63

63

63

a na apelu wieczornym było

˙zołnierzy i otrzymano reszty:

63

63

63

wtedy ró˙znica

spełnia nast¸epuj¸acy układ kongruencji:

63

63

63

9

Jak wida´c, chi´nskie twierdzenie o resztach pozwala wnioskowa´c o du˙zych liczbach za

pomoc¸a operacji na małych liczbach. Zobaczmy teraz inne zastosowanie tego twierdzenia.

Przykład 1.43 Zastanówmy si¸e, ile wynosi reszta z dzielenia liczby

przez 15. Łatwo mo˙zna policzy´c, ˙ze:

63

oraz

63

, a wi¸ec:

63

poniewa˙z 4 jest jedyn¸a liczb¸a z przedziału

9

99

, która posiada reszty

63

oraz

63

.

1.14

Pierwiastki kwadratowe

Definicja 1.44 Liczb¸e

nazywamy pierwiastkiem kwadratowym liczby

w pier´scieniu

, je˙zeli

3

9

Przykład 1.45 W

pierwiastkami 4 s¸a 2 i 3, a liczba 2 nie posiada pierwiastka.

Zauwa˙zmy, ˙ze je˙zeli

63

to

63

czyli

63

, te˙z jest pierwiastkiem

.

Lemat 1.46 Je˙zeli

jest liczb¸a pierwsz¸a i

, to

i

s¸a jedynymi pierwiastkami

z

.

1.15. Funkcja Eulera

25

Dowód Je˙zeli

3

, to

dzieli

, a poniewa˙z

jest pierwsze to

dzieli

lub

. W pierwszym przypadku

63

, w

drugim

63

.

Przykład 1.47 Tak nie musi by´c, je˙zeli

nie jest liczb¸a pierwsz¸a. Na przykład w

mamy cztery pierwiastki z , s¸a to ,

,

i

.

Ogólnie rozwa˙zmy liczb¸e

która jest iloczynem dwóch ró˙znych liczb pierwszych

.#

. We´zmy teraz dowoln¸a liczb¸e

, dla której

63

lub

63

oraz

3

lub

63

Wtedy

63

oraz

63

czyli z chi´nskiego twierdzenia o resztach wynika, ˙ze

63

9

Poniewa˙z

, to

3

oraz

63

i mamy wtedy

cztery ró˙zne pierwiastki z 1,

. S¸a to liczby dla których

63

63

63

63

63

63

63

63#

9

Zauwa˙zmy, ˙ze

3

oraz

63

.

1.15

Funkcja Eulera

Definicja 1.48 Funkcja Eulera, jest to funkcja, która liczbie

przypisuje

liczb¸e

elementów odwracalnych w

. Z definicji przyjmujemy

.

Przykład 1.49

, bo w

odwracalne s ˛

a

.

Podobnie

,

,

,

,

.

Lemat 1.50

a) Je˙zeli

jest liczb¸a pierwsz¸a, to dla dowolnego

,

. W szczególno´sci

.

b) Je˙zeli

i

s¸a wzgl¸ednie pierwsze, to

26

Rozdział 1. Teoria liczb

Dowód:

a)

Zauwa˙zmy ˙ze, w´sród liczb

99

9

wzgl¸ednie pierwsze z

nie s¸a te, które s¸a po-

dzielne przez , jest ich

'

, czyli

9

b)

Najpierw zauwa˙zmy, ze dla dowolnej liczby

,

#

"

wtedy i tylko wtedy gdy

oraz

a to zachodzi wtedy i tylko wtedy gdy reszty

3

oraz

3

spełniaj¸a warunki

oraz

(1.7)

Par reszt

spełniaj¸acych warunek (1.7) jest

, a z chi ´nskiego twierdzenia

o resztach ka˙zdej liczbie

,

"

odpowiada dokładnie jedna para reszt, i na

odwrót ka˙zdej parze reszt odpowiada jedna liczba. Tak wi¸ec liczb wzgl¸ednie pierwszych
z

jest

9

1.16

Szybkie pot¸egowanie

Teraz zastanowimy si¸e jak mo˙zna pot¸egowa´c, czyli jak obliczy´c

63

dla

oraz

. Pierwszy nasuwaj¸acy si¸e algorytm pot¸egowania polega na

krotnym mno-

˙zeniu przez

:

y:=1;

for i:=0 to k do y:=y*a mod n

W kryptografii oblicza si¸e pot¸egi z wykładnikami posiadaj¸acymi po kilkaset bitów. Do
takich zastosowa ´n powy˙zszy algorytm jest nieprzydatny (wymaga on

mno˙ze ´n).

Poka˙zemy teraz jak mo˙zna pot¸egowa´c du˙zo szybciej. Zauwa˙zmy, ˙ze

i ogólnie

9

Dlatego, aby obliczy´c pot¸eg¸e o wykładniku, który jest pot¸eg¸a dwójki

nale˙zy

wykona´c

y:=a;

for i:=1 to j do y:=y*y mod n

1.16. Szybkie pot¸egowanie

27

Przykład 1.51 Aby obliczy´c

w

obliczmy

-

3

,

!

3

,

3

,

63

.

Je˙zeli wykładnik jest sum¸a pot¸eg dwójki

, to

9

Przykład 1.52 Aby obliczy´c

63

trzeba wymno˙zy´c

)

63

.

Zauwa˙zmy, ˙ze ka˙zda liczba naturalna

jest sum¸a pot¸eg dwójki

gdzie

to cyfry rozwini¸ecia dwójkowego

.

Powy˙zsze uwagi sugeruj¸a nast¸epuj¸acy algorytm obliczania pot¸egi

.

Algorytm szybkiego pot˛egowania

Dane wej´sciowe: podstawa

a

oraz wykładnik

k=(dj,...,d0)

w postaci binarnej.

x:=a; y:=1

if d0=1 then y:=y*a mod n

for i:=1 to j do

x:=x*x mod n;

if di=1 then y:=y*x mod n

Zmienna

x

zawiera kolejne pot¸egi

o wykładnikach b¸ed¸acych pot¸egami 2. Na pocz¸atku

. Po

tej iteracji p¸etli for

. Je˙zeli

to mno˙zymy

przez

.

Na ko´ncu

8

9

Przykład 1.53 Prze´sled´zmy działanie algorytmu podczas obliczania

63

.

w zapisie dwójkowym ma posta´c

)

)

. Poni˙zsza tabela zawiera warto´sci zmiennej

x

i

y

przed wej´sciem do p˛etli

for i=0

) oraz po ka˙zdej iteracji.

i

x

y

0

2

2

1

4

8

2

3

8

3

9

8

4

3

11

Zauwa˙zmy, ˙ze wyniki po´srednie, i ostateczny, nale˙z ˛

a do

i algorytm nie potrzebuje

zbyt du˙zej pami¸eci. Algorytmu tego nie mo˙zna stosowa´c do obliczania

w liczbach

całkowitych, je˙zeli

jest du˙ze, to wynik ostateczny oraz po´srednie b¸ed ˛

a zbyt du˙ze, ˙zeby

mógł si¸e zmie´sci´c w pami¸eci komputera.

28

Rozdział 1. Teoria liczb

1.17

Małe twierdzenie Fermata

Twierdzenie 1.54 (Fermata) Niech

, wtedy

63

9

Dowód Niech

99

9

to b¸ed¸a wszystkie elementy

. Je˙zeli pomno˙zymy je przez

9

99

to zgodnie z lematem 1.36 otrzymamy te same elementy tylko w innej kolejno´sci.

Wymnó˙zmy teraz elemnty obu ci¸agów

63

9

Po pomno˙zeniu przez odwrotno´s´c

otrzymamy tez¸e twierdzenia.

Wniosek 1.55 Je˙zeli

jest liczb¸a pierwsz¸a, to dla ka˙zdego

wzgl¸ednie pierwszego z

mamy

3

9

1.18

Szyfry RSA

W szyfrach one-pad opisanych w rozdziale o funkcjach boolowskich klucz do szyfrowa-
nia jest ten sam co klucz do deszfrowania. W szyfrach liniowych wprawdzie klucze do
szyfrowania i deszyfrowania s¸a ró˙zne, ale jaden łatwo mo˙zna wyliczy ´c z drugiego. Takie
szyfry nazywamy symetrycznymi.

Teraz zapoznamy si¸e ze sposobem szyfrowania, w których klucz do szyfrowania mo˙ze

by´c jawny, nawet ogłaszany publicznie, a klucz do deszyfrowania jest tajny i jest praktycz-
nie niemo˙zliwe wyliczenie klucza tajnego z klucza jawnego. Sposób ten zaproponowali
Rivest, Shamir i Adleman. Przypu´s´cmy, ˙ze Alicja chce utworzy´c swój klucz. Bierze w
tym celu dwie du˙ze liczby pierwsze

i

, ka˙zda mo˙ze zawiera´c po kilkaset bitów. Tworzy

ich iloczyn

. Funkcja Eulera

. Nast¸epnie Alicja losuje liczb¸e

, która jest wzgl¸ednie pierwsza z

. Skoro

to istnieje liczba

, taka, ˙ze

3

. Teraz para

jest jawnym kluczem Alicji i mo˙ze

by´c publicznie ogłoszona. Para

jest kluczem prywatnym Alicji, nie powinna go ona

nikomu zdradza´c. Alicja nie powinna te˙z zdradza´c rozkładu liczby

na czynniki. Je˙zeli

kto´s zna

i

, to mo˙ze wyliczy´c

oraz

.

Przypu´s´cmy, ˙ze Bob chce przesła´c Alicji jak¸a´s zaszyfrowan¸a wiadomo´s´c

. Traktuje-

my t¸e wiadomo´s´c jako liczb¸e

"

. (Je˙zeli wiadomo´s´c jest ci¸agiem znaków, to kodujemy

1.19. Testy pierwszo´sci

29

ka˙zdy znak jako 8 bitów i cały ci¸ag mo˙ze by´c traktowany jako liczba w postaci dwójko-
wej.) Bob szyfruje wiadomo´s´c przy pomocy funkcji szyfruj¸acej

63

i przesyła j¸a Alicji. Alicja odszyfrowuje za pomoc¸a funkcji deszyfruj¸acej

63

9

Poka˙zemy teraz, ˙ze je˙zeli

, to

9

Mamy

63

9

Poniewa˙z

!

63

, wi¸ec istnieje

takie, ˙ze

4

, czyli

63

ale je˙zeli

, to

63

. Tak wi¸ec

. Do powy˙zszego potrzebne było zało˙zenie, ˙ze

. Ale gdy kto´s trafi na

wiadomo´s´c

, która nie jest wzgl¸ednie pierwsza z

, to Alicja ma pecha, poniewa˙z wtedy

mo˙zna dokona´c rozkładu liczby

i złama´c jej szyfr.

Łatwo te˙z mo˙zna pokaza´c, ˙ze

.

Niesymetryczne szyfry daj¸a nowe mo˙zliwo´sci. Mo˙zna ich na przykład u˙zywa´c do

podpisu. Aby podpisa´c jak¸a´s wiadomo´s´c

, Alicja szyfruje j¸a swoim szyfrem prywat-

nym

i jest to podpis wiadomo´sci

. Alicja wysyła Bobowi par¸e

.

˙

Zeby sprawdzi´c, ˙ze wszystko si¸e zgadza Bob szyfruje podpis publicznym kluczem Alicji
i sprawdza czy

9

1.19

Testy pierwszo´sci

W tym rozdziale zajmiemy si¸e zagadnieniem jak sprawdzi´c, czy liczba

jest pierwsza.

Mo˙zemy sobie wyobrazi´c, ˙ze

ma kilkaset bitów. Jak wida´c z poprzedniego rozdziału

du˙ze liczby pierwsze mog¸a by´c przydatne.

1.19.1

Test naiwny

Najprostszy sposób to, dzieli´c

przez kolejne liczby (pierwsze) a˙z do

. Jednak ten

test jest zupełnie niepraktyczny, je˙zeli

ma kilkaset bitów.

30

Rozdział 1. Teoria liczb

1.19.2

Test Fermata

Drugi test jest algorytmem probabilistycznym i opiera si¸e na twierdzeniu Fermata 1.54.

Losujemy liczb¸e

"

i najpierw sprawdzamy, czy

. Je˙zeli

i

nie s¸a wzgl¸ednie pierwsze, i

, to

jest dzielnikiem

i

nie jest

pierwsza.

Je˙zeli

, to obliczamy

63

. Je˙zeli

63

, to

mamy pewno´s´c, ˙ze

nie jest liczb¸a pierwsz¸a.

Definicja 1.56 Tak¸a liczb¸e

, dla której

oraz

63

b¸edziemy nazywa´c ´swiadkiem Fermata dla

, poniewa˙z za´swiadcza ona, ˙ze

jest zło˙zona.

Je˙zeli

63

, to orzekamy, ˙ze liczba

jest pierwsza. W tym przypadku

mo˙zemy si¸e pomyli´c. Liczba

mo˙ze by´c zło˙zona a mimo to wylosowali´smy pechowo i

3

. Ale zachodzi nast¸epuj¸acy lemat.

Lemat 1.57 Je˙zeli istnieje takie

, ˙ze

63

, to przynajmniej poło-

wa elementów

jest ´swiadkiem Fermata dla

.

Dowód. Przypu´s´cmy, ˙ze

9

99

s ˛

a to wszystkie elementy

, dla których

3

. Wtedy po pomno˙zeniu

przez

otrzymamy

elementów

6

9

99

6

ró˙znych mi¸edzy sob¸a (lemat 1.36), z których ka˙zdy jest ´swiadkiem Fermata. Rzeczywi-
´scie

63

9

A wi¸ec ´swiadków zło˙zono´sci jest co najmniej połowa.

Je˙zeli

jest pierwsze, to z Twierdzenia Fermata, algorytm zawsze orzeknie dobrze.

Z lematu 1.57 wynika, ˙ze je˙zeli

jest zło˙zona i istnieje ´swiadek Fermata dla

, to takich

´swiadków jest co najmniej połowa, i nasz algorytm pomyli si¸e z prawdopodobie ´nstwem

"

'

. Prawdopodobie ´nsto, to mo˙zna zmniejszy´c poprzez powtórzenie algorytmu

razy,

z ró˙znymi wylosowanymi

.

Istniej¸a jednak liczby zło˙zone

, które nie maj¸a ´swiadków zło˙zono´sci. Na przykład

. Kłopot bierze si¸e st¸ad, ˙ze

!

)

, a

dzieli si¸e przez

,

oraz przez

. Dlatego dla dowolnego

, je˙zeli

, to

jest wzgl¸ednie pierwsze z

,

i

oraz mamy

63

63

63

i z chi´nskiego twierdzenia o resztach wynika, ˙ze

63

Takie liczby nazywaj¸a sie liczbami Carmichaela. Pierwsze trzy z nich to 561, 1105 i 1729.
Wyst¸epuj¸a one bardzo rzadko, jest ich tylko 255 w´sród liczb mniejszych od 100 000 000.

1.19. Testy pierwszo´sci

31

1.19.3

Test Millera-Rabina

Zakładamy, ˙ze

jest nieparzyste (2 jest jedyn¸a parzyst¸a liczb¸a pierwsz¸a). Najpierw spraw-

dzamy, czy

jest pot¸eg¸a jakiej´s liczby naturalnej. Dla

od 2 do

/

sprawdzamy czy

, dla jakiego´s

. W rozdziale o arytmetyce opisano jak za pomoc¸a binary search

stwierdzi´c, czy liczba jest pot¸eg¸a innej liczby. Je˙zeli

jest pot¸eg¸a, to jest zło˙zona.

Poniewa˙z

jest nieparzyste, to

mo˙zemy przedstawi´c w postaci

9

dla jakiego´s

nieparzystego.

Losujemy

"

. Sprawdzamy, czy

(je˙zeli

8

, to

jest zło˙zona).

Nast¸epnie obliczamy

63

. Je˙zeli

63

, to koniec, stwierdzamy, ˙ze

jest pierwsza. Je˙zeli

63

, to obliczamy po kolei

3

63

99

9

63

9

Zauwa˙zmy, ˙ze w tym ci¸agu ka˙zda liczba jest kwadratem poprzedniej. Je˙zeli w´sród tych
liczb nie ma jedynki, to z twierdzenia Fermata wynika, ˙ze

jest zło˙zona, bo wtedy

3

9

Je˙zeli w tym ci¸agu jest jedynka, na przykład

3

to patrzymy na poprzedni element

. Je˙zeli

, to znale˙zli´smy nietrywial-

ny pierwiastek z 1. Z twierdzenia 1.46 wynika, ˙ze jest to mo˙zliwe tylko wtedy gdy

nie

jest pierwsze. Je˙zeli

, to orzekamy, ˙ze

jest pierwsze.

Łatwo wi¸ec wida´c, ˙ze je˙zeli

jest pierwsze, to test zawsze odpowie prawidłowo,

niezale˙znie od losowania. Wiadomo te˙z, ˙ze je˙zeli

jest zło˙zona i nie jest pot¸eg¸a licz-

by pierwszej, to z prawdopodobie ´nstwem wi¸ekszym ni˙z

'

wykryjemy to (dowód tego

faktu wybiega poza zakres tej ksi¸a˙zki i pomijamy go).

W praktyce stosujemy wszystkie trzy testy na raz. Maj¸ac nieparzyst¸a liczb¸e

, naj-

pierw sprawdzamy, czy dzieli si¸e ona przez kilka kolejnych liczb pierwszych

9

99

9

Dobór

zale˙zy od tego jak du˙ze liczby sprawdzamy. W ten sposób eliminujemy du˙z¸a

cz¸e´s´c liczb. Zauwa˙zmy, ˙ze obliczaj¸ac iloczyn tych liczb

i sprawdzaj¸ac, czy

&

mo˙zemy za jednym razem sprawdzi´c, czy

dzieli

si¸e przez któr¸a´s z tych liczb.

32

Rozdział 1. Teoria liczb

Po przej´sciu pierwszego testu stosujemy test drugi, a gdy liczba

go przejdzie stosu-

jemy test trzeci.

Poniewa˙z liczby Carmichaela s¸a do´s´c rzadkie, wi¸ec drugi test wyeliminuje wi¸ekszo´s´c

liczb zło˙zonych.

Je˙zeli chcemy wyklosowa´c liczb¸e pierwsz¸a to losujemy nieparzyst¸a liczb¸e, a mast¸epnie

sprawdzamy, czy jest ona pierwsza. Je˙zeli nie, to sprawdzamy nast¸epne liczby

91919

.

1.20

Zadania

1. Dla ka˙zdej z liczb:

,

,

oraz

)

znajd´z liczb˛e

tak ˛

a,

˙ze

63

.

2. W pier´scieniu

wykonaj działania

oraz

.

3. W pier´scieniu

rozwi ˛

a˙z równania: a)

, b)

, c)

8

, d)

8

.

4. W pier´scieniu

rozwi ˛

a˙z równania: a)

, b)

.

5. W pier´scieniu

rozwi ˛

a˙z równania: a)

-

, b)

.

6. Dla liczb

i

)

oblicz

oraz liczby całkowite

i

spełniaj¸ace równanie

6

.

7. Oblicz

(

.

8. W pier´scieniu

rozwi ˛

a˙z równania: a)

3

.

9. W pier´scieniu

rozwi ˛

a˙z równania: a)

, b)

.

10. Znajd´z całkowite rozwi¸azanie

spełniaj¸ace równanie:

.

11. Podaj rozkład na czynniki pierwsze liczb

oraz

)

.

12. Ile dzielników ma liczba

?

13. Podaj tabliczk¸e dodawania i mno˙zenia w ciele

. Podaj elementy odwrotne do 5 i

6 w

.

14. Znajd´z elementy odwrotne do wszystkich elementów dwracalnych w

.

15. Dla jakich par reszt

istniej¸a liczby

spełniaj¸ace układ kongruencji:

63

63

9

16. Niech

i

b¸ed¸a dowolnymi dodatnimi liczbami całkowitymi. Dla jakich par

reszt

istniej¸a liczby

spełniaj¸ace układ kongruencji:

63

63

9

1.21. Problemy

33

1.21

Problemy

1.21.1

Najwi˛ekszy wspólny dzielnik

Udowodnij, ˙ze

jest najmniejsz¸a dodatni¸a liczb¸a

, dla której istnieje

i

całkowite, takie ˙ze

(

.

Udowodnij, ˙ze ka˙zda liczba postaci

(

, dla

i

całkowitych, jest wielokrotno´sci¸a

, i na odwrót, ka˙zda wielokrotno´s´c

jest postaci

(

, dla jaki´s

i

całkowitych.

Udowodnij, ˙ze poni˙zszy algorytm poprawnie oblicza najwi¸ekszy wspólny dzielnik

, je˙zeli

$

:

var a,b,p,q,r,:integer;

begin

readln(a,b);

p:=a;q:=b;

while q >0 do

begin

r:=p mod q;

p:=q; q:=r

end;

writeln(’NWD(’,a,’,’,b,’)=’,p)

end.

Zmodyfikuj powy˙zszy program, tak aby oprócz

, obliczał tak˙ze współ-

czynniki

i

, takie ˙ze

6

.

1.21.2

Najmniejsza wspólna wielokrotno´

s´

c

Niech

oznacza najmniejsz¸a wspóln¸a wielokrotno´s´c liczb

i

.

Udowodnij, ˙ze

dzieli ka˙zd¸a inn¸a wspóln¸a wielokrotno´s´c liczb

i

.

Poka˙z, ˙ze

1.21.3

Liczby wzgl˛ednie pierwsze

Udowodnij, ˙ze je˙zeli

jest wzgl¸ednie pierwsze z

i

, to

jest wzgl¸ednie pierwsze z

iloczynem tych liczb

6

.

Jako wniosek udowodnij, ˙ze je˙zeli

jest wzgl¸ednie pierwsze z ka˙zd¸a z liczb

919

9

,

to

jest wzgl¸ednie pierwsze z iloczynem tych liczb

9

34

Rozdział 1. Teoria liczb

1.21.4

Układ kongruencji

Istnieje inny sposób rozwi¸azywania układu kongruencji. Poka˙zemy go na przykładzie
układu

63

(1.8)

63

Najpierw szukamy dwóch liczb

i

spełniaj¸acych warunki

63

63

63

63

Udowodnij, ˙ze rozwi¸azaniem układu (1.8) jest

63

9

Jak policzy´c

oraz

? Poniewa˙z 3 i 5 s¸a wzgl¸ednie pierwsze, wi¸ec istniej¸a

i

takie,

˙ze

Poka˙z, ˙ze je˙zeli podstawimy

63

oraz

63

, to b¸edzie

dobrze.

1.21.5

Chi ´

nskie twierdzenie o resztach

Z chi´nskiego twierdzenia o resztach wynika, ˙ze je˙zeli

, to funkcja

63

63

stanowi wzajemnie jednoznaczne odwzorowanie pomi¸edzy

a iloczynem kartezja ´n-

skim

.

Na iloczynie kartezja ´nskim

mo˙zemy okre´sli´c działania dodawania i mno˙ze-

nia w nast¸epuj¸acy sposób:

9

Łatwo mo˙zna sprawdzi´c, ˙ze zbiór

z tak okre´slonymi działaniami, jest pier´scie-

niem. Ponadto funkcja

spełnia warunki

oraz

.