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 otrzymali´smy iloraz 145 i reszt˛e 3. Liczby te spełniaj ˛

a równanie

1743 = 145

· 12 + 3

i reszta jest mniejsza od dzielnika. Podobnie mo˙zemy 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

• 0 ≤ r < b

q nazywa si˛e ilorazem całkowitoliczbowym a przez b, a r nazywa si˛e reszt¸a z dzielenia

Zauwa˙zmy, ˙ze iloraz

q jest zaokr¸agleniem w dół normalnego ilorazu q =

ba/bc. Iloraz

całkowitoliczbowy liczb

a i b b¸edziemy oznacza´c przez

a

÷ b

lub

a div b.

3

4

Rozdział 1. Teoria liczb

a reszt˛e przez

a mod b.

Przykład 1.2

22

÷ 4 = 5 oraz 22 mod 4 = 2, poniewa˙z 22 = 5 · 4 + 2 oraz 0 ≤ 2 < 4.

W przypadku, gdy

a i b 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

ba/bc — zaokr¸aglenie ilorazu a/b w dół, gdy a/b jest dodatnie i da/be, —

zaokr¸aglenie ilorazu

a/b w gór¸e, gdy a/b 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

a

6= 0 dzieli liczb¸e całkowit¸a b, je˙zeli istnieje liczba całko-

wita

z, taka ˙ze:

b = az.

B¸edziemy to oznacza´c przez

a

|b. Zauwa˙zmy, ˙ze zachodzi wtedy:

b mod a = 0.

Liczb¸e

a nazywamy dzielnikiem liczby b.

Przykład 1.3

3

|6, 3| − 6 oraz 3|0.

Lemat 1.4 Je˙zeli

a

|b oraz a|c , to a|(b + c) oraz a|(b − c)

Dowód. Je˙zeli

a

|b i a|c, to istniej¸a dwie liczby całkowite k i m, takie ˙ze:

b = ak

oraz

c = am.

Mamy wi¸ec:

b + c = ak + am = a(k + m)

oraz

b

− c = ak − am = a(k − m)

czyli

a dzieli b + c oraz b

− c.

2

1.3. Relacja kongruencji

5

1.3

Relacja kongruencji

Niech

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

6= 0. Powiemy, ˙ze dwie liczby całkowite a i

b s¸a równowa˙zne (lub przystaj¸a) modulo m, je˙zeli

m

|(a − b).

B¸edziemy wtedy pisa´c:

a = b (mod m).

Przykład 1.5

1 = 4 (mod 3),

3 = 0 (mod 3),

−1 = 2 (mod 3),

−1 = −7

(mod 3).

Je˙zeli

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ównowa˙zno´sci, czyli spełnia nast¸epuj¸ace
trzy warunki:

• zwrotno´

s´

c, dla ka˙zdego

a zachodzi

a = a (mod m),

• symetri¸e, dla ka˙zdego a i b, je˙zeli

a = b (mod m),

to

b = a (mod m),

• przechodnio´

s´

c, dla ka˙zdego

a, b i c,

je˙zeli

a = b (mod m)

i

b = c (mod m),

to

a = c (mod m).

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

m

|(a − b) oraz m|(b − c),

to

m

|((a − b) + (b − c)), czyli m|(a − c).

2

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

Twierdzenie 1.7 Je˙zeli

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

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

m

|(a − b)

oraz

m

|(c − d),

z tego za´s łatwo wynika, ˙ze

m dzieli:

(a + c)

− (b + d), (a − c) − (b − d) oraz ac − bd = a(c − d) + d(a − b),

czyli zachodzi teza twierdzenia.

2

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

1999 mod 3,

6

Rozdział 1. Teoria liczb

to pytamy, która z trzech liczb

{0, 1, 2} przystaje do 1999 modulo 3. Zróbmy najpierw

kilka prostych obserwacji. Po pierwsze:

10 = 1 (mod 3),

bo

3

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

modulo 3, czyli:

10

k

= 1 (mod 3)

dla ka˙zdego

k. Mamy teraz:

1999 = 1000 + 9

· 100 + 9 · 10 + 9 = 1 + 9 + 9 + 9 = 1 (mod 3).

Podobnie, dla dowolnej liczby

x, je˙zeli zapiszemy x w postaci dziesi¸etnej:

x =

X

d

i

· 10

i

,

to

x =

X

d

i

(mod 3),

czyli

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

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

2002

· 1999 6= 4001999

wystarczy zauwa˙zy´c, ˙ze liczba

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

by˙z parzysty. Mówi ˛

ac inaczej

2002 = 0 (mod 2) oraz 1999 = 1 (mod 2), wi˛ec na

podstawie twierdzenia 1.7 mamy

2002

· 1999 = 0 (mod 2), a liczba 4001999 przystaje

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

2002

· 1999 6= 4001996

wystarczy zauwa˙zy´c, ˙ze w iloczynie

2002

· 1999 ostatni ˛

a cyfr ˛

a powinno by´c 8 a nie 6.

Inaczej

2002 = 2 (mod 10) oraz 1999 = 9 (mod 10), wi˛ec na podstawie twierdze-

nia 1.7 mamy

2002

· 1999 = 8 (mod 10), a liczba 4001996 przystaje do 6 modulo

10.

1.4

Klasy abstrakcji

Dla relacji przystawania modulo

m definiujemy klasy abstrakcji. Dla dowolnej liczby

całkowitej

x, klas¸e abstrakcji elementu x definiujemy w nast¸epuj¸acy sposób:

[x] =

{y | y = x (mod m)}.

Innymi słowy, klasa abstrakcji liczby

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

Przykład 1.10 Dla

m = 3 mamy trzy klasy abstrakcji

1.5. Pier´scie´n Z

m

7

[0] =

{3k | k ∈ Z} = {. . . , −9, −6, −3, 0, 3, 6, 9, . . .}

[1] =

{3k + 1 | k ∈ Z} = {. . . , −8, −5, −2, 1, 4, 7, 10, . . .}

[2] =

{3k + 2 | k ∈ Z} = {. . . , −7, −4, −1, 2, 5, 8, 11, . . .}

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

Lemat 1.11 Je˙zeli

x = y

(mod m),

to

[x] = [y].

Dowód. Je˙zeli

z

∈ [x],

to

z = x

(mod m) i z przechodnio´sci relacji z = y

(mod m), czyli:

z

∈ [y],

a wi¸ec pokazali´smy, ˙ze:

[x]

⊂ [y].

Identycznie pokazujemy zawieranie odwrotne

[y]

⊂ [x].

2

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

Lemat 1.12 Je˙zeli

[x]

∩ [y] 6= ∅,

to

[x] = [y],

inaczej, dwie klasy abstrakcji

[x] i [y] albo s¸a identyczne, albo s¸a rozł¸aczne.

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

[x] i [y] maj¸a wspólny element z. Wtedy:

z = x (mod m)

oraz

z = y

(mod m).

Z przechodnio´sci mamy wtedy

x = y

(mod m), a z lematu 1.11 [x] = [y].

2

1.5

Pier´scie ´n Z

m

Klasy abstrakcji relacji modulo

m wygl¸adaj¸a nast¸epuj¸aco:

[0], [1], . . . , [m

− 1].

Dla dowolnego

k z przedziału 0

≤ k ≤ m − 1, klasa [k] jest postaci:

[k] =

{jm + k | j ∈ Z}

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

m oznacza si¸e przez

Z

m

.

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:

[x] + [y] = [x + y].

Podobnie definiujemy odejmowanie i mno˙zenie:

[x]

− [y] = [x − y],

[x]

· [y] = [x · y].

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

[x] = [y]

oraz

[u] = [w],

to:

[x + u] = [y + w],

[xu] = [yw]

oraz

[x

− u] = [y − w].

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

x = y

(mod m)

oraz

u = w

(mod m).

a z twierdzenia 1.7:

[x + u] = [y + w],

[x

− u] = [y − w] oraz [xu] = [yw].

2

Przykład 1.14 Niech

m = 3. Dla dowolnych dwóch liczb x

∈ [0] i y ∈ [1] ich suma

x + y nale˙zy do [0 + 1] = [1] a iloczyn do [0

· 1] = [0].

Lemat 1.15 Działania na klasach abstrakcji

[0], [1], . . . , [n

− 1]

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

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

• klasa [0] jest elementem neutralnym dodawania, to znaczy dla ka˙zdego a mamy

[a] + [0] = [a],

• dla ka˙zdej klasy [a] istnieje klasa do niej przeciwna [−a], taka ˙ze [a] + [−a] = [0],

• klasa [1] jest elementem neutralnym mno˙zenia, to znaczy dla dowolnego [x] mamy

[x]

· [1] = [x],

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

[y], [z] mamy [x]([y] + [z]) = [x][y] + [x][z].

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

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

[x]([y] + [z]) = [x][y + z] = [x(y + z)] = [xy + xz] = [xy] + [xz] = [x][y] + [x][z].

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

2

1.5. Pier´scie´n Z

m

9

1.5.1

Pier´

scie ´

n Z

5

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

[0], [1], [2], [3], [4],

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

Z

5

=

{0, 1, 2, 3, 4}

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 Z

5

element odwrotny wzgl¸edem mno˙ze-

nia, czyli dla ka˙zdego

x

∈ Z

5

− {0} istnieje x

−1

, taki ˙ze xx

−1

= 1:

1

−1

= 1,

2

−1

= 3,

3

−1

= 2,

4

−1

= 4.

Dlatego Z

5

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

wzgl¸edem mno˙zenia.

1.5.2

Pier´

scie ´

n Z

4

Rozwa˙zmy teraz pier´scie´n reszt modulo 4:

Z

4

=

{0, 1, 2, 3},

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

x 1

0

1

2

3

2

0

2

0

2

3

0

3

2

1

Z

4

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

4

mamy:

2

· 2 = 0,

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

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

m jest zło˙zona, m = pq dla 1 < p, q < m, to w

pier´scieniu Z

m

mamy

pq = 0 i ani p, ani q nie maj¸a elementów odwrotnych. Przypu´s´cmy

bowiem, ˙ze istnieje

p

−1

. Mamy wtedy:

0 = p

−1

0 = p

−1

(pq) = (p

−1

p)q = 1q = q,

10

Rozdział 1. Teoria liczb

czyli

q = 0, sprzeczno´s´c. Tak wi¸ec Z

m

nie jest ciałem, je˙zeli

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

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

m jest liczb¸a pierwsz¸a, to Z

m

jest

ciałem.

1.6

Najwi¸ekszy wspólny dzielnik

Dla dwóch liczb całkowitych

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

liczba całkowita

n, która dzieli a i b. Najwi¸ekszy wspólny dzielnik liczb a i b b¸edziemy

oznacza´c przez

N W D(a, b). Na przykład: N W D(4, 6) = 2, N W D(4, 0) = 4.

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

gorytmu Euklidesa, którego najprostsza wersja wygl ˛

ada nast˛epuj ˛

aco:

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

a, b,

powtarzamy a˙z do skutku:

• je˙zeli a = b, to koniec, NW D(a, b) = a,

• je˙zeli a > b, to a := a − b,

• je˙zeli a < b, to b := b − a.

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 poni˙zszej tabeli pokazano kolejne kroki działania algorytmu Euklidesa na parze

liczb 36 i 15:

p

q

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 powy˙zszego algorytmu wynika z prostego faktu, ˙ze para

a, b ma taki sam

zbiór wspólnych dzielników jak para

a

−b, b. Rzeczywi´scie, je˙zeli liczba r jest wspólnym

dzielnikiem pary

a, b, to r dzieli tak˙ze a

− b, czyli r jest wspólnym dzielnikiem pary

(a

− b), b. Na odwrót, je˙zeli liczba r jest wspólnym dzielnikiem pary (a − b), b, to r dzieli

tak˙ze

(a

− b) + b = a, czyli r jest wspólnym dzielnikiem pary a, b.

Je˙zeli zechcemy według tego uproszczonego algorytmu policzy ´c najwi˛ekszy wspólny

dzielnik dla pary

a = 2000001 i b = 2, to algorytm b˛edzie milion razy obliczał a = a

− b

i po tym wszystkim

a b˛edzie równe reszcie z dzielenia a przez b, czyli 1. Dlatego cz˛e-

´sciej stosuje si˛e algorytm, w którym zamiast odejmowania oblicza si˛e reszt˛e z dzielenia
wi˛ekszej liczby przez mniejsz ˛

a i robi si˛e to tak długo, a˙z otrzymamy zero.

1.7. Algorytm Euklidesa

11

1.7

Algorytm Euklidesa

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

a, b, powtarzamy a˙z do skutku:

• je˙zeli a = 0 lub b = 0 to koniec, NW D(a, b) = a + b,

• je˙zeli a > b, to a := a mod b,

• je˙zeli a < b, to b := b mod a.

Powy˙zszy algorytm oblicza reszt˛e z dzielenia wi¸ekszej liczby przez mniejsz¸a tak długo,
a˙z otrzyma zero. Wtedy wynikiem działania algorytmu jest ta druga liczba (je˙zeli

a = 0,

to

a + b = b, a je˙zeli b = 0, to a + b = a).

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

liczb 36 i 15:

p

q

36

15

6

15

6

3

0

3

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

W uproszczonej wersji j¸ezyka Pascal algorytm Euklidesa mo˙zna zapisa ´c w nast¸epuj¸acy

sposób:

p:=a;q:=b;

while p*q<>0 do

if p>q then p:=p mod q

else q:=q mod p;

NWD(a,b):=p+q

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

Lemat 1.16 Niech

p i q b¸ed¸a dwoma liczbami naturalnymi i niech 0 < q < p. Wtedy

para

p, q ma taki sam zbiór wspólnych dzielników jak para p mod q, q.

Dowód. Z definicji ilorazu i reszty mamy

p = (p

÷ q) · q + p mod q

Je˙zeli liczba

r jest wspólnym dzielnikiem pary p, q, to r dzieli tak˙ze reszt˛e p mod q, czyli

r jest wspólnym dzielnikiem pary (p mod q), q. Na odwrót, je˙zeli liczba r jest wspólnym
dzielnikiem pary

(p mod q), q, to r dzieli tak˙ze p, czyli r jest wspólnym dzielnikiem pary

p, q.

2

12

Rozdział 1. Teoria liczb

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

while

para

p, q 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

p = 0 lub

q = 0, N W D(p, q) = p + q, czyli jest równy tej drugiej liczbie.

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

a i b algorytm

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

while

liczba

max

{p, q}

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.

Twierdzenie 1.17 Niech

a i b b¸ed¸a dwoma dodatnimi liczbami naturalnymi i niech d =

N W D(a, b). Wtedy istniej¸a liczby całkowite x i y, takie ˙ze:

xa + yb = d,

lub mówi¸ac inaczej,

d jest kombinacj¸a całkowitoliczbow¸a liczb a i b.

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

p i q w trakcie wy-

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

a i b. Na

pocz¸atku, gdy

p = a i q = b, mamy:

p = 1a + 0b,

q = 0a + 1b.

Załó˙zmy teraz, ˙ze po

i-tej iteracji p¸etli p > q oraz ˙ze zachodzi:

p = x

p

a + y

p

b,

q = x

q

a + y

q

b.

Wtedy w

(i + 1) iteracji p b¸edzie pomniejszone o q

· (p ÷ q) i b¸edziemy mieli:

p = (x

p

− x

q

· (p ÷ q))a + (y

p

− y

q

· (p ÷ q))b

oraz

q = x

q

a + y

q

b.

Z tego wynika, ˙ze tak˙ze ostateczna warto´s´c

d jest całkowitoliczbow¸a kombinacj¸a liczb a

i

b.

2

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

dzielnika

N W D(a, b), wyliczał tak˙ze liczby x i y, takie ˙ze:

xa + yb = N W D(a, b).

Oto ten algorytm w j¸ezyku Pascal:

p:=a;q:=b;

xp:=1;yp:=0;

xq:=0;yq:=1;

while p<>q do

1.7. Algorytm Euklidesa

13

if p>q then

begin

p:=p-q;

xp:=xp-xq*(p div q);

yp:=yp-yq*(p div q)

end

else

begin

q:=q-p;

xq:=xq-xp*(q div p);

yq:=yq-yp*(q div p)

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:

p

q

xp

yp

xq

yq

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¸ec liczb¸e 3 mo˙zna przedstawi´c jako kombinacj¸e liczb 15 i 36 w nast¸epuj¸acy sposób:

3 = (

−2) · 36 + (5) · 15.

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

r dzieli liczby a i b, to dzieli tak˙ze ka˙zd¸a ich kombinacj¸e

całkowit¸a

xa + yb,

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

N W D(a, b). Udowodnili´smy poni˙zszy

lemat.

Lemat 1.18

N W D(a, b) jest podzielny przez ka˙zdy wspólny dzielnik liczb a i b.

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

N W D(a, b) mo˙ze by´c rów-

nowa˙znie zdefiniowany jako taki wspólny dzielnik liczb

a i b, który jest podzielny przez

ka˙zdy wspólny dzielnik

a i b.

Lemat 1.19 Liczba

d jest najwi¸ekszym wspólnym dzielnikiem liczb a i b wtedy i tylko

wtedy gdy

d b¸edzie wspólnym dzielnikiem a i b oraz istniej¸a liczby całkowite x i y, takie

˙ze

d = xa + yb.

14

Rozdział 1. Teoria liczb

Dowód Je˙zeli

N W D(a, b) = d to d

|a, d|b oraz (z twierdzenia 1.17) istniej¸a liczby cał-

kowite

x i y, takie ˙ze: d = xa + yb. Na odwrót, je˙zeli d dzieli a i b oraz xa + yb = d, to

ka˙zdy wspólny dzielnik

a i b dzieli d, a wi¸ec d jest najwi¸ekszym wspólnym dzielnikiem

a i b.

2

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

x i y, takie, ˙ze xa+yb = 1, to N W D(a, b) =

1.

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

N W D(1998, 2000). Poniewa˙z:

2000

− 1998 = 2

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

N W D(1998, 2000) = 2.

Zastanówmy si¸e teraz, ile wynosi

N W D(1999, 2001). Poniewa˙z:

2001

− 1999 = 2,

wi¸ec

N W D(1999, 2001) dzieli 2, a poniewa˙z 2 nie dzieli ani 1999, ani 2001, wi¸ec

N W D(1999, 2001) = 1.

1.8

Liczby pierwsze i wzgl¸ednie pierwsze

Dwie liczby naturalne

a i b s ˛

a wzgl¸ednie pierwsze, je˙zeli

N W D(a, b) = 1, a liczba

naturalna

p jest pierwsza, je˙zeli p > 1 i jedynymi dzielnikami naturalnymi p s¸a 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˙zona. Istniej ˛

a wtedy dwie liczby

k, m < n,

takie, ˙ze

n = k

· m.

1.9

Rozkład liczb na czynniki pierwsze

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

n > 1 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:

12 = 2

2

· 3

i

180 = 2

2

· 3

2

· 5.

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

n > 1 mo˙zna przedstawi´c jako iloczyn liczb

pierwszych (niekoniecznie ró˙znych):

n = q

1

q

2

· · · q

r

.

1.9. Rozkład liczb na czynniki pierwsze

15

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

n, której nie mo˙zna przed-

stawi´c jako iloczynu liczb pierwszych i ˙ze

n jest najmniejsz¸a tak¸a liczb¸a. n nie mo˙ze by´c

liczb¸a pierwsz¸a (bo wtedy

n = q

1

), wi¸ec

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

n = km

dla

k, m < n. Ale poniewa˙z k i m s¸a mniejsze od n, wi¸ec mo˙zna je rozło˙zy´c na czynniki

pierwsze

k = p

1

p

2

· · · p

s

oraz

m = r

1

r

2

· · · r

t

,

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

n na czynniki pierwsze:

n = p

1

p

2

· · · p

s

r

1

r

2

· · · r

t

.

2

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.23 Niech

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

Wtedy dla dowolnej liczby

c, je˙zeli a

|bc, to a|c.

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

x i y, takie ˙ze:

xa + yb = 1.

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

c:

xac + ybc = c,

i zauwa˙zmy, ˙ze

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

stron¸e, czyli

c.

2

Lemat 1.24 Je˙zeli liczba pierwsza

p dzieli iloczyn liczb pierwszych

q

1

q

2

· · · q

r

(niekoniecznie ró˙znych), to wtedy

p jest równe jednej z liczb q

i

.

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

r. Dla r = 1 mamy p

|q

1

, a poniewa˙z

q

1

jest

pierwsza i

p > 1, wi¸ec p = q

1

.

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

r i przypu´s´cmy, ˙ze p dzieli

q

1

q

2

· · · q

r

q

r

+1

.

Mamy dwa przypadki: albo

p dzieli q

r

+1

, albo nie. W pierwszym przypadku

p = q

r

+1

.

W drugim przypadku mamy

N W D(p, q

r

+1

) = 1, bo 1 i q

r

+1

to jedyne dzielniki liczby

q

r

+1

. Z lematu 1.23 wynika teraz, ˙ze

p dzieli q

1

q

2

· · · q

r

, a z zało˙zenia indukcyjnego, ˙ze

p = q

i

dla jakiego´s

1

≤ i ≤ r.

2.

16

Rozdział 1. Teoria liczb

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

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

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

stawi´c w postaci iloczynu:

n = p

α

1

1

p

α

2

2

. . . p

α

r

r

,

gdzie

α

i

s¸a dodatnimi liczbami naturalnymi,

p

i

s¸a liczbami pierwszymi oraz zachodzi

p

1

< p

2

< . . . < p

r

.

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

n = 2 jako liczba pierwsza ma jednoznaczny

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

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

n = p

α

1

1

p

α

2

2

. . . p

α

r

r

= q

β

1

1

q

β

2

2

. . . q

β

s

s

.

(1.1)

Wtedy z jednej strony

p

1

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

n/p

1

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

p

1

dzieli praw¸a

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

2

Lemat 1.26 Je˙zeli

a i b 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.27 Element

a

∈ Z

m

jest odwracalny, je˙zeli istnieje

b

∈ Z

m

, takie, ˙ze

a

· b = 1 (mod m).

b nazywamy elementem odwrotnym do a i oznaczamy przez a

−1

.

Przykład 1.28

3 jest odwracalna w Z

8

bo

3

· 3 = 1 (mod 8). Oprócz 3 w Z

8

odwra-

calne s ˛

a tak˙ze

1, 5 i 7.

Lemat 1.29 Liczba

a

∈ Z

m

jest odwracalna wtedy i tylko wtedy, gdy

N W D(a, m) = 1.

Dowód. Je˙zeli

N W D(a, m) = 1, to istniej¸a liczby całkowite x i y, takie ˙ze:

xa + ym = 1,

a wi¸ec

m dzieli ax

− 1, czyli:

ax = 1 (mod m).

Teraz wystarczy przyj¸a´c za

a

−1

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

m

− 1, która przystaje

do

x modulo m.

Z drugiej strony je˙zeli istnieje element

a

−1

odwrotny do

a to

a

−1

a = 1 (mod m)

1.10. Elementy odwracalne

17

czyli

a

−1

a

− 1 = k · m

dla jakiego´s

k. Mamy wi¸ec

a

−1

a + (

−k)m = 1

czyli

N W D(a, m) = 1 (wniosek 1.20).

2

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

a mo˙zna wyliczy ´c stosuj¸ac

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

17

.

Najpierw zastosujemy algorytm Euklidesa, aby obliczy´c

x i y, takie ˙ze:

12x + 17y = 1.

Kolejne kroki algorytmu przedstawiono w tabeli:

p

q

xp

yp

xq

yq

17

12

1

0

0

1

5

12

1

-1

0

1

5

2

1

-1

-2

3

1

2

5

-7

-2

3

1

0

5

-7

-12

17

Mamy wi¸ec:

5

· 17 + (−7)12 = 1,

czyli:

(

−7)12 = 1 (mod 17),

ale:

−7 = 10 (mod 17),

czyli 10 jest elementem odwrotnym do 12 w pier´scieniu Z

17

.

Definicja 1.30 Zbiór elementów odwracalnych w Z

n

oznaczamy przez Z

∗

n

.

Przykład 1.31 Z

∗

8

=

{1, 3, 5, 7}.

Lemat 1.32 Je˙zeli liczba

m jest pierwsza, to ka˙zdy element a

∈ Z

m

,

a

6= 0, jest odwra-

calny, czyli pier´scie´n Z

m

jest ciałem.

Lemat 1.33 Je˙zeli

a, b

∈ Z

∗

n

to

ab

∈ Z

∗

n

oraz

a

−1

∈ Z

∗

n

.

To oznacza, ˙ze Z

∗

n

z mno˙zeniem jest grup¸a.

Dowód: Elementem odwrotnym do iloczynu

ab jest b

−1

a

−1

, a elementem odrotnym do

a

−1

jest

a.

2

18

Rozdział 1. Teoria liczb

1.11

Funkcja liniowa

Zastanówmy si¸e jak w pier´scieniu Z

m

działa funkcja liniowa

f (x) = a

· x (mod m).

Rozpatrzmy najpierw przypadek, gdy

a i m s¸a wzgl¸ednie pierwsze, czyli gdy N W D(a, m) =

1. Dla m = 8 i a = 3 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

a

−1

element odwrotny do

a i funkcja g(x) = a

−1

x, która

jest odwrotna do

f . Rzeczywi´scie

f (g(x)) = aa

−1

x = x.

Z tego wynika, ˙ze

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

∈ Z

m

równanie

ax = b

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

m

, jest ono równe

x = a

−1

b.

Funkcja

f jest permutacj¸a w Z

m

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

permutowa´c) elementy Z

m

. Zauwa˙zmy, ˙ze

f jest tak˙ze permutacj ˛

a w Z

∗

m

. Rzeczywi´scie,

je˙zeli

x

∈ Z

∗

m

, to na podstawie lematu 1.33

f (x) = ax

∈ Z

∗

m

. Mamy wi¸ec

Lemat 1.34 Je˙zeli

N W D(a, m) = 1, to funkcja f (x) = ax jest funkcj¸a wzajemnie

jednoznaczn¸a w Z

m

i w Z

∗

m

.

Rozpatrzmy teraz przypadek, gdy

a i m nie s¸a wzgl¸ednie pierwsze, czyli gdy N W D(a, m) =

d > 1. Dla m = 8 i a = 6 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

b jest warto´sci¸a funkcji f , czyli gdy

ax = b (mod m)

to istnieje takie

k, ˙ze

ax

− b = km,

a poniewa˙z

d dzieli a i m, to d dzieli b, a wi¸ec warto´sciami funkcji f mog¸a by´c tylko

liczby podzielne przez

d.

Lemat 1.35 Je˙zeli

N W D(a, m) = d oraz d

|b, to równania

ax = b (mod m)

oraz

(a/d)x = (b/d) (mod m/d)

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

1.11. Funkcja liniowa

19

Dowód

ax = b (mod m)

wtedy i tylko wtedy, gdy istnieje

k takie ˙ze

ax

− b = km,

a to zachodzi wtedy i tylko wtedy, gdy istnieje

k takie, ˙ze

(a/d)x

− (b/d) = k(m/d),

czyli wtedy i tylko wtedy, gdy

(a/d)x = (b/d) (mod m/d).

2

Przypu´s´cmy teraz, ˙ze

d dzieli b i rozwi¸a˙zmy równanie

ax = b

(1.2)

w pier´scieniu Z

m

, czyli szukamy takich

x

∈ {0, . . . , m − 1}, ˙ze

ax = b (mod m)

(1.3)

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

(a/d)x = (b/d) (mod m/d)

(1.4)

Ale teraz

N W D(a/d, m/d) = 1 i równanie (1.4) ma dokładnie jedno rozwi¸azanie x

0

∈

{0, . . . , m/d − 1} takie ˙ze

(a/d)x

0

= (b/d) (mod m/d).

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

x

0

, x

0

+ m/d, x

0

+ 2m/d, . . . , x

0

+ (d

− 1)m/d.

S¸a to wszystkie liczby ze zbioru

{0, . . . , m − 1} spełniaj¸ace równania (1.4) i (1.3), czyli

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

m

.

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

6x = 9 (mod 15).

(1.5)

Poniewa˙z

N W D(6, 15) = 3, wi¸ec najpierw rozwi¸azujemy równanie

2x = 3 (mod 5)

W Z

5

mamy

2

−1

= 3 wi¸ec rozwi¸azaniem jest x

0

= 3

· 3 = 4. Tak wi¸ec rozwi¸azaniami

równaia (1.5) w Z

15

s¸a liczby

4, 9, 14.

20

Rozdział 1. Teoria liczb

1.12

Szyfry liniowe

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

a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z,

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

26

:

a = 0,

b = 1,

c = 2, . . . , z = 25,

wybieramy dwie liczby

a, b

∈ Z

26

, takie ˙ze

N W D(a, 26) = 1, i szyfrujemy litera po

literze według wzoru:

C(x) = ax + b (mod 26).

Funkcja deszyfruj¸aca jest okre´slona wzorem:

D(y) = a

−1

y

− a

−1

b (mod 26).

Rzeczywi´scie:

D(C(x)) = a

−1

(ax + b)

− a

−1

b = a

−1

ax + a

−1

b

− a

−1

b = x.

Z tego wynika, ˙ze funkcja szyfruj¸aca

C(x) jest wzajemnie jednoznaczna.

Przykład 1.37 Wybierzmy

a = 23 i b = 20 i zaszyfrujmy słowo

matematyka.

W tym celu musimy zaszyfrowa´c 6 liter:

m, a, t, e, y oraz k. Obliczenia przedstawiono w

tabeli:

litera

x

C(x)

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

matematyka po zaszyfrowaniu wygl¸ada tak:

kupikupaqu.

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.

1.13. Chi ´nskie twierdzenie o resztach

21

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

a = 1 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.38 (kontynuacja przykładu 1.37) W naszym drugim zaszyfrowanym tek´scie
litera

e wyst¸epuje cztery razy, a litery p i u po trzy razy. Mo˙ze to nam pomóc w odgadni¸eciu,

˙ze litera

e koduje liter¸e o, a litera p koduje liter¸e t. Mamy wi¸ec dwa równania:

15 = 19a + b (mod 26),

4 = 14a + b (mod 26).

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

11 = 5a (mod 26).

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

26

. Jest to 21, poniewa˙z:

(

−5)5 + 26 = 1

oraz

− 5 = 21 (mod 26),

tak wi¸ec:

a = 21

· 11 = 231 = 23 (mod 26).

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

b:

b = 15

− 19 · 23 = 20 (mod 26).

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:

m

1

= 3,

m

2

= 5,

m

3

= 7,

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:

m

1

= 2

m

2

= 3.

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

22

Rozdział 1. Teoria liczb

a

a (mod 2)

a (mod 3)

0

0

0

1

1

1

2

0

2

3

1

0

4

0

1

5

1

2

Ka˙zda z liczb od 0 do

5 = 2

· 3 − 1 ma inny zestaw reszt oraz dla ka˙zdej pary reszt

(a

1

, a

2

), spełniaj¸acych warunek 0

≤ a

1

< 2, 0

≤ a

2

< 3, istnieje liczba a, taka ˙ze:

a

1

= a (mod 2),

a

2

= a (mod 3).

Oczywi´scie 6 ma takie same reszty jak 0:

0 = 6 (mod 2),

0 = 6 (mod 3),

i ogólnie, je˙zeli dwie liczby

a i b ró˙zni¸a si¸e o wielokrotno´s´c liczby 6 = 2

· 3, czyli:

a = b + k

· 6

dla jakiego´s całkowitego

k, to

a (mod 2) = b (mod 2),
a (mod 3) = b (mod 3).

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

m

1

i

m

2

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

m

1

= 4 i m

2

= 6, to w´sród liczb od 0 do 23 = 4

· 6 − 1 istniej¸a takie, które maj¸a takie

same reszty, na przykład 1 i 13:

1 (mod 4) = 13 (mod 4) = 1,
1 (mod 6) = 13 (mod 6) = 1.

Ponadto nie istnieje taka liczba

a, dla której:

1 = a (mod 4),

0 = a (mod 6).

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

a powinno by´c nieparzyste, a z drugiej,

˙ze parzyste.

Je˙zeli jednak

m

1

i

m

2

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

m

1

· m

2

− 1 ma

inny zestaw reszt oraz dla ka˙zdej pary reszt

(a

1

, a

2

), spełniaj¸acych warunek 0

≤ a

1

<

m

1

,

0

≤ a

2

< m

2

, istnieje liczba

a, taka ˙ze:

a

1

= a (mod m

1

),

a

2

= a (mod m

2

),

zachodzi bowiem poni˙zsze twierdzenie.

1.13. Chi ´nskie twierdzenie o resztach

23

Twierdzenie 1.39 (chi ´

nskie twierdzenie o resztach) Niech

m

1

, m

2

, . . . , m

r

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

1

≤ i < j ≤ r

mamy

N W D(m

i

, m

j

) = 1, oraz niech

a

1

, a

2

, . . . , a

r

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

a, taka ˙ze:

a

1

= a (mod m

1

),

a

2

= a (mod m

2

),

(1.6)

. . .

a

r

= a (mod m

r

).

Ponadto je˙zeli liczby

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

a

− b dzieli si¸e przez iloczyn wszystkich liczb m

i

, czyli przez:

M =

r

Y

i

=1

m

i

.

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

1

≤ i ≤ r mamy:

a

i

= a (mod m

i

)

oraz

a

i

= b (mod m

i

).

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

0 = a

− b (mod m

i

),

czyli

m

i

|(a − b),

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

m

i

dzieli

a

−b, a skoro liczby m

1

. . . m

r

s¸a wzgl¸ednie pierwsze,

wi¸ec tak˙ze ich iloczyn

M dzieli a

− b. Rzeczywi´scie, przypu´s´cmy bowiem, ˙ze M ma

rozkład

M = p

α

1

1

p

α

2

2

· · · p

α

s

s

.

We´zmy teraz dowolne

p

α

i

i

. Poniewa˙z rozkłady liczb

m

1

, . . . , m

r

s¸a rozł¸aczne, wi¸ec

p

α

i

i

wyst˛epuje w rozkładzie jakiego´s

m

j

, czyli dzieli

m

j

oraz

a

− b, a wi¸ec w rozkładzie

liczby

a

− b, liczba p

i

wyst¸epuje z wykładnikiem

β

≥ α

i

. Dlatego

M dzieli a

− b.

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

M

i

= M/m

i

, czyli:

M

i

= m

1

· · · m

i

−1

m

i

+1

. . . m

r

.

Poniewa˙z

M

i

i

m

i

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

N W D(m

i

, M

i

) = 1 oraz istnieje N

i

,

takie ˙ze:

M

i

N

i

= 1 (mod m

i

).

24

Rozdział 1. Teoria liczb

We´zmy teraz:

a =

r

X

i

=1

a

i

M

i

N

i

.

Zauwa˙zmy, ˙ze je˙zeli

i

6= j, to m

i

|M

j

, oraz:

a

j

M

j

N

j

= 0 (mod m

i

),

co daje:

a = a

i

M

i

N

i

= a

i

(mod m

i

)

dla ka˙zdego

i, a wi¸ec a jest rozwi¸azaniem układu równa ´n (1.6).

2

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

104 = 3

· 5 · 7 − 1 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

x ˙zołnierzy i uzyskano reszty:

x

1

= x

(mod 3),

x

2

= x (mod 5),

x

3

= x

(mod 7),

a na apelu wieczornym było

y ˙zołnierzy i otrzymano reszty:

y

1

= y

(mod 3),

y

2

= y

(mod 5),

y

3

= y

(mod 7),

wtedy ró˙znica

x

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

x

1

− y

1

= x

− y (mod 3),

x

2

− y

2

= x

− y (mod 5),

x

3

− y

3

= x

− y (mod 7).

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.41 Zastanówmy si¸e, ile wynosi reszta z dzielenia liczby

M = 1 997 199 919

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

M = 4 (mod 5) oraz M = 1 (mod 3), a wi¸ec:

M = 4 (mod 15),

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

0, 1, 2, . . . , 14, która posiada reszty 4 = 1

(mod 3) oraz 4 = 4 (mod 5).

1.14. Pierwiastki kwadratowe

25

1.14

Pierwiastki kwadratowe

Definicja 1.42 Liczb¸e

y nazywamy pierwiastkiem kwadratowym liczby x w pier´scieniu

Z

m

, je˙zeli

x = y

2

(mod m).

Przykład 1.43 W Z

5

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

Zauwa˙zmy, ˙ze je˙zeli

y

2

= x

(mod m) to

(m

− y)

2

= m

2

− 2my + y

2

= y

2

= x (mod m),

czyli

m

− y = −y (mod m), te˙z jest pierwiastkiem x.

Lemat 1.44 Je˙zeli

m jest liczb¸a pierwsz¸a i x = y

2

, to

y i

−y s¸a jedynymi pierwiastkami

z

x.

Dowód Je˙zeli

z

2

= y

2

(mod m), to m dzieli z

2

− y

2

= (z

− y)(z + y), a poniewa˙z m

jest pierwsze to

m dzieli z

− y lub z + y. W pierwszym przypadku z = y (mod m), w

drugim

z =

−y (mod m).

2

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

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

15

mamy cztery pierwiastki z

1, s¸a to 1, 4, 11 i 14.

Ogólnie rozwa˙zmy liczb¸e

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

p > q > 2. We´zmy teraz dowoln¸a liczb¸e y, dla której

y mod p = 1 lub y mod p =

−1

oraz

y mod q = 1 lub y mod q =

−1

Wtedy

y

2

mod p = 1 oraz y

2

mod q = 1

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

y

2

= 1 (mod pq).

Poniewa˙z

p > q > 2, to 1

6= −1 (mod p) oraz 1 6= −1 (mod q) i mamy wtedy

cztery ró˙zne pierwiastki z 1,

y

1

, y

2

, y

3

, y

4

. S¸a to liczby dla których

y

1

mod p = 1,

y

1

mod q = 1,

y

2

mod p = 1,

y

2

mod q =

−1,

y

3

mod p =

−1,

y

3

mod q = 1,

y

4

mod p =

−1

y

4

mod q =

−1.

Zauwa˙zmy, ˙ze

y

1

= 1 (mod n) oraz y

4

=

−1 (mod n).

26

Rozdział 1. Teoria liczb

1.15

Funkcja Eulera

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

m przypisuje φ(m) liczb¸e

elementów odwracalnych w Z

m

. Z definicji przyjmujemy

φ(1) = 1.

Przykład 1.47

φ(8) = 4, bo w Z

8

odwracalne s ˛

a

{1, 3, 5, 7}.

Podobnie

φ(2) = 1, φ(3) = 2, φ(4) = 2, φ(6) = 2, φ(9) = 6.

Lemat 1.48

a) Je˙zeli

p jest liczb¸a pierwsz¸a, to dla dowolnego α

≥ 1, φ(p

α

) =

p

α

−1

(p

− 1). W szczególno´sci φ(p) = p − 1.

b) Je˙zeli

m i n s¸a wzgl¸ednie pierwsze, to φ(m

· n) = φ(m) · φ(n)

Dowód:

a)

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

0, . . . , p

α

wzgl¸ednie pierwsze z

p

α

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

dzielne przez

p, jest ich p

α

/p = p

α

−1

, czyli

φ(p

α

) = p

α

− p

α

−1

= p

α

−1

(p

− 1).

b)

Najpierw zauwa˙zmy, ze dla dowolnej liczby

x, 0

≤ x < mn

N W D(x, mn) = 1

wtedy i tylko wtedy gdy

N W D(x, m) = 1 oraz N W D(x, n) = 1

a to zachodzi wtedy i tylko wtedy gdy reszty

r

m

= x mod m oraz r

n

= x mod n

spełniaj¸a warunki

N W D(r

m

, m) = 1 oraz N W D(r

n

, n) = 1

(1.7)

Par reszt

(r

m

, r

n

) spełniaj¸acych warunek (1.7) jest φ(m)

·φ(n), a z chi´nskiego twierdzenia

o resztach ka˙zdej liczbie

x, 0

≤ x < mn 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

mn jest φ(m)

· φ(n).

2

1.16

Szybkie pot¸egowanie

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

a

k

mod n dla a

∈ Z

n

oraz

k

∈ N. Pierwszy nasuwaj¸acy si¸e algorytm pot¸egowania polega na k krotnym mno-

˙zeniu przez

a:

y:=1;

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

1.16. Szybkie pot¸egowanie

27

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

k mno˙ze ´n).

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

a

· a = a

2

,

a

2

· a

2

= a

4

i ogólnie

a

2

i

· a

2

i

= a

2

i+1

.

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

k = 2

j

nale˙zy

wykona´c

y:=a;

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

Przykład 1.49 Aby obliczy´c

2

16

w Z

13

obliczmy

2

2

= 2

· 2 = 4 (mod 13),

2

4

= 4

· 4 = 3 (mod 13),

2

8

= 3

· 3 = 9 (mod 13),

2

16

= 9

· 9 = 3 (mod 13).

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

k = 2

i

+ 2

j

, to

a

k

= a

2

i

· a

2

j

.

Przykład 1.50 Aby obliczy´c

2

19

mod 13 trzeba wymno˙zy´c 2

19

= 2

16

·2

2

·2

1

= 3

·4·2 =

11 (mod 13).

Zauwa˙zmy, ˙ze ka˙zda liczba naturalna

k jest sum¸a pot¸eg dwójki

k =

j

X

i

=1

d

i

· 2

i

,

gdzie

d

i

∈ {0, 1} to cyfry rozwini¸ecia dwójkowego k.

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

a

k

.

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

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

x = a = a

2

0

. Po

i tej iteracji p¸etli for x = a

2

i

. Je˙zeli

di = 1 to mno˙zymy y przez x = a

2

i

.

Na ko´ncu

y = a

d

0

a

d

1·2

1

· · · a

dj

·2

j

= a

k

.

28

Rozdział 1. Teoria liczb

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

2

19

(mod 13). 19

w zapisie dwójkowym ma posta´c

(10011)

2

. 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 Z

m

i algorytm nie potrzebuje

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

a

k

w liczbach

całkowitych, je˙zeli

k 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.

1.17

Małe twierdzenie Fermata

Twierdzenie 1.52 (Fermata) Niech

a

∈ Z

∗

m

, wtedy

a

φ

(m)

= 1 (mod m).

Dowód Niech

a

1

, a

2

, . . . , a

φ

(m)

to b¸ed¸a wszystkie elementy Z

∗

m

. Je˙zeli pomno˙zymy je przez

a

aa

1

, aa

2

, . . . , aa

φ

(m)

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

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

φ

(m)

Y

i

=1

a

i

=

φ

(m)

Y

i

=1

aa

i

= a

φ

(m)

φ

(m)

Y

i

=1

a

i

(mod m).

Po pomno˙zeniu przez odwrotno´s´c

Q

φ

(m)

i

=1

a

i

otrzymamy tez¸e twierdzenia.

2

Wniosek 1.53 Je˙zeli

p jest liczb¸a pierwsz¸a, to dla ka˙zdego a wzgl¸ednie pierwszego z p

mamy

a

p

−1

= 1 (mod p).

1.18. Szyfry RSA

29

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

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

ich iloczyn

n = pq. Funkcja Eulera φ(n) = (p

− 1)(q − 1). Nast¸epnie Alicja losuje liczb¸e

e, która jest wzgl¸ednie pierwsza z φ(n). Skoro N W D(e, φ(n)) = 1 to istnieje liczba
d, taka, ˙ze ed = 1 (mod φ(n)). Teraz para (e, n) jest jawnym kluczem Alicji i mo˙ze
by´c publicznie ogłoszona. Para

(n, d) jest kluczem prywatnym Alicji, nie powinna go ona

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

n na czynniki. Je˙zeli

kto´s zna

p i q, to mo˙ze wyliczy´c φ(n) oraz d.

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

x. Traktuje-

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

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

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

C

A

(x) = x

e

mod n

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

D

A

(y) = y

d

mod n.

Poka˙zemy teraz, ˙ze je˙zeli

N W D(x, n) = 1, to

D

A

(C

A

(x)) = x.

Mamy

D

A

(C

A

(x)) = x

ed

mod n.

Poniewa˙z

ed = 1 (mod φ(n)), wi¸ec istnieje k takie, ˙ze ed = 1 + kφ(n), czyli

D

A

(C

A

(x)) = x

1+kφ(n)

= x

· x

kφ

(n)

(mod n)

ale je˙zeli

N W D(x, n) = 1, to x

kφ

(n)

= (x

φ

(n)

)

k

= 1 (mod n). Tak wi¸ec D

A

(C

A

(x)) =

x. Do powy˙zszego potrzebne było zało˙zenie, ˙ze N W D(x, n) = 1. Ale gdy kto´s trafi na
wiadomo´s´c

x, która nie jest wzgl¸ednie pierwsza z n, to Alicja ma pecha, poniewa˙z wtedy

mo˙zna dokona´c rozkładu liczby

n i złama´c jej szyfr.

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

C

A

(D

A

(x)) = x.

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

m, Alicja szyfruje j¸a swoim szyfrem prywat-

nym

D

A

(m) i jest to podpis wiadomo´sci m. Alicja wysyła Bobowi par¸e (m, D

A

(m)).

˙

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

C

A

(D

A

(m)) = m.

30

Rozdział 1. Teoria liczb

1.19

Testy pierwszo´sci

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

n jest pierwsza.

Mo˙zemy sobie wyobrazi´c, ˙ze

n 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

n przez kolejne liczby (pierwsze) a˙z do

√

n. Jednak ten

test jest zupełnie niepraktyczny, je˙zeli

n ma kilkaset bitów.

1.19.2

Test Fermata

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

Losujemy liczb¸e

a < n i najpierw sprawdzamy, czy N W D(a, n) = 1. Je˙zeli a i n

nie s¸a wzgl¸ednie pierwsze, i

N W D(a, n) = d > 1, to d jest dzielnikiem n i n nie jest

pierwsza.

Je˙zeli

N W D(a, n) = 1, to obliczamy a

n

−1

mod n. Je˙zeli a

n

−1

6= 1 (mod n), to

mamy pewno´s´c, ˙ze

n nie jest liczb¸a pierwsz¸a.

Definicja 1.54 Tak¸a liczb¸e

a, dla której N W D(a, n) = 1 oraz a

n

−1

6= 1 (mod n)

b¸edziemy nazywa´c ´swiadkiem Fermata dla

n, poniewa˙z za´swiadcza ona, ˙ze n jest zło˙zona.

Je˙zeli

a

n

−1

= 1 (mod n), to orzekamy, ˙ze liczba n jest pierwsza. W tym przypadku

mo˙zemy si¸e pomyli´c. Liczba

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

a

n

−1

= 1 (mod n). Ale zachodzi nast¸epuj¸acy lemat.

Lemat 1.55 Je˙zeli istnieje takie

a

∈ Z

∗

n

, ˙ze

a

n

−1

6= 1 (mod n), to przynajmniej poło-

wa elementów Z

∗

n

jest ´swiadkiem Fermata dla

n.

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

{b

1

, . . . , b

k

}

s ˛

a to wszystkie elementy Z

∗

n

, dla których

b

n

−1

i

= 1 (mod n). Wtedy po pomno˙zeniu

przez

a otrzymamy k elementów

{ab

1

, . . . , ab

k

}

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

(ab

i

)

n

−1

= a

n

−1

b

n

−1

i

= a

n

−1

6= 1 (mod n).

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

2

Je˙zeli

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

Z lematu 1.55 wynika, ˙ze je˙zeli

n jest zło˙zona i istnieje ´swiadek Fermata dla n, to takich

´swiadków jest co najmniej połowa, i nasz algorytm pomyli si¸e z prawdopodobie ´nstwem
< 1/2. Prawdopodobie´nsto, to mo˙zna zmniejszy´c poprzez powtórzenie algorytmu r razy,
z ró˙znymi wylosowanymi

a.

1.19. Testy pierwszo´sci

31

Istniej¸a jednak liczby zło˙zone

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

n = 561. Kłopot bierze si¸e st¸ad, ˙ze 561 = 3

· 11 · 17, a 560 = 561 − 1 dzieli si¸e przez

2 = 3

− 1, 10 = 11 − 1 oraz przez 16 = 17 − 1. Dlatego dla dowolnego a, je˙zeli

N W D(a, 561) = 1, to a jest wzgl¸ednie pierwsze z 3, 11 i 17 oraz mamy

a

560

= (a

2

)

280

= 1 (mod 3)

a

560

= (a

10

)

56

= 1 (mod 11)

a

560

= (a

16

)

35

= 1 (mod 17)

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

a

560

= 1 (mod 561)

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.3

Test Millera-Rabina

Zakładamy, ˙ze

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

dzamy, czy

n jest pot¸eg¸a jakiej´s liczby naturalnej. Dla α od 2 do log

2

n sprawdzamy czy

n = k

α

, dla jakiego´s

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

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

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

Poniewa˙z

n jest nieparzyste, to n

− 1 mo˙zemy przedstawi´c w postaci

n

− 1 = m · 2

k

.

dla jakiego´s

m nieparzystego.

Losujemy

a < n. Sprawdzamy, czy N W D(a, n) = 1 (je˙zeli N W D(a, n) > 1, to n

jest zło˙zona).

Nast¸epnie obliczamy

a

m

mod n. Je˙zeli a

m

mod n = 1, to koniec, stwierdzamy, ˙ze n

jest pierwsza. Je˙zeli

a

m

mod n

6= 1, to obliczamy po kolei

a

m

2

mod n, a

m

2

2

mod n, . . . , a

m

2

k

mod n.

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

n jest zło˙zona, bo wtedy

a

m

2

k

= a

n

−1

6= 1 (mod n).

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

a

m

2

i

= 1 (mod n)

to patrzymy na poprzedni element

x = a

m

2

i−1

. Je˙zeli

x

6= −1, to znale˙zli´smy nietrywial-

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

n nie

jest pierwsze. Je˙zeli

x =

−1, to orzekamy, ˙ze n jest pierwsze.

32

Rozdział 1. Teoria liczb

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

n jest pierwsze, to test zawsze odpowie prawidłowo,

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

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

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

1/2 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

n, naj-

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

p

1

, p

2

, . . . , p

d

.

Dobór

d 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

x =

d

Y

i

=1

p

i

i sprawdzaj¸ac, czy

N W D(x, n) = 1 mo˙zemy za jednym razem sprawdzi´c, czy n dzieli

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

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

n 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.

1.19.4

Losowanie liczb pierwszych

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

n + 2, n +

4, ....

1.20

Zadania

1. Podziel (oblicz ilorazy i reszty) liczb

175 oraz 1754 przez 11.

2. Dla ka˙zdej z liczb:

x = 8,

−8, 120 oraz −120 znajd´z liczb˛e y ∈ {0, 1, 2, 3, 4} tak ˛a,

˙ze

x = y

(mod 5).

3. Oblicz: a)

(50

· 51 + 15) mod 7, b) 15 · 36 mod 7; c) 15

3

· (37)

3

mod 7.

4. Oblicz: a)

10

39

mod 11, b) 2

39

mod 5 c) 7

40

mod 10.

5. Przedstaw klasy abstrakcji relacji kongruencji dla

m = 6.

6. Jak wygl ˛

adaj ˛

a działania dodawania i mno˙zenia w pier´scieniu Z

6

7. W pier´scieniu Z

8

wykonaj działania

7 + 6 oraz 7

· 6.

8. W pier´scieniu Z

8

rozwi ˛

a˙z równania: a)

1 + x = 0, b) 1 + x = 2, c) 5 + x = 0, d)

5 + x = 2.

1.20. Zadania

33

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

7

. Podaj elementy odwrotne do 5 i

6 w Z

7

.

10. Dla liczb

a = 600 i b = 1050 oblicz N W D(a, b) oraz liczby całkowite x i y

spełniaj¸ace równanie

xa + yb = N W D(a, b).

11. Oblicz

N W D(667, 713).

12. Oblicz

N W D(199816, 199819).

13. W pier´scieniu Z

5

rozwi ˛

a˙z równania: a)

4

· x = 1, b) 4 · x = 2.

14. W pier´scieniu Z

8

rozwi ˛

a˙z równania: a)

3

· x = 1, b) 3 · x = 2.

15. W pier´scieniu Z

17

rozwi ˛

a˙z równania: a)

8x = 2,

b)

9x = 4.

16. W pier´scieniu Z

14

rozwi ˛

a˙z równania: a)

6x = 2, b) 6x = 9.

17. Znajd´z całkowite rozwi¸azanie

(x, y) spełniaj¸ace równanie: 17x + 40y = 1.

18. Podaj rozkład na czynniki pierwsze liczb

240 oraz 111.

19. Ile dzielników ma liczba

240?

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

12

.

21. Przedstaw tabel˛e funkcji

f (x) = 4

· x + 5 w pier´scieniu Z

13

.

22. Przedstaw tabel˛e funkcji

f (x) = 4

· x + 5 w pier´scieniu Z

12

.

23. Rozwi ˛

a˙z układ kongruencji:

3 = a (mod 5),
5 = a (mod 6).

24. Sprawd´z, czy

100136 = 200146 (mod 30)

25. Dla jakich par reszt

(a

1

, a

2

) istniej¸a liczby a spełniaj¸ace układ kongruencji:

a

1

= a (mod 4),

a

2

= a (mod 6).

26. Które elementy Z

12

s ˛

a resztami kwadratowymi?

27. Które elementy Z

13

s ˛

a resztami kwadratowymi?

28. Ile jest pierwiastków z

1 w Z

30

?

29. Poka˙z,˙ze w Z

105

jest osiem pierwiastków z

1.

30. Przy pomocy algorytmu szybkiego pot˛egowania oblicz: a)

3

100

mod 13; b)2

100

mod

15.

31. Oblicz: a)

φ(24); b) φ(120).

34

Rozdział 1. Teoria liczb

1.21

Problemy

1.21.1

Najwi˛ekszy wspólny dzielnik

1. Udowodnij, ˙ze ka˙zda liczba postaci

xa+yb, dla x i y całkowitych, jest wielokrotno´sci¸a

N W D(a, b), i na odwrót, ka˙zda wielokrotno´s´c N W D(a, b) jest postaci xa + yb,
dla jaki´s

x i y całkowitych.

2. Udowodnij, ˙ze

N W D(a, b) jest najmniejsz¸a dodatni¸a liczb¸a d, dla której istnieje x

i

y całkowite, takie ˙ze xa + yb = d.

3. Zaprojektuj algorytm obliczania najwi˛ekszego wspólnego dzielnika trzech (lub

k)

liczb.

4. Które z liczb całkowitych mo˙zna przedstawi´c w postaci

x

· 10 + y · 21 (x i y ∈ Z)?

5. Które z liczb całkowitych mo˙zna przedstawi´c w postaci

x

· 10 + y · 12 (x i y ∈ Z)?

1.21.2

Najmniejsza wspólna wielokrotno´

s´

c

Niech

N W W (a, b) oznacza najmniejsz¸a wspóln¸a wielokrotno´s´c liczb a i b.

1. Udowodnij, ˙ze

N W W (a, b) dzieli ka˙zd¸a inn¸a wspóln¸a wielokrotno´s´c liczb a i b.

2. Poka˙z, ˙ze

N W W (a, b)

· NW D(a, b) = a · b.

3. Jakie liczby całkowite dziel ˛

a si˛e jednocze´snie przez

24 i przez 54?

1.21.3

Liczby wzgl˛ednie pierwsze

Udowodnij, ˙ze je˙zeli

m jest wzgl¸ednie pierwsze z a i b, to m jest wzgl¸ednie pierwsze z

iloczynem tych liczb

ab.

Jako wniosek udowodnij, ˙ze je˙zeli

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

1

, ..., m

k

,

to

m jest wzgl¸ednie pierwsze z iloczynem tych liczb

k

Y

i

=1

m

i

.

1.21.4

Liczby pierwsze

1. Udowodnij, ˙ze dla ka˙zdego

k istnieje ci ˛

ag

k kolejnych liczb zło˙zonych.

2. Udowodnij, ˙ze liczb pierwszych jest niesko ´nczenie wiele.

3. Udowodnij, ˙ze je˙zeli dwie liczby

x i y spełniaj ˛

a warunki:

x

2

= y

2

(mod n) oraz

x

6= y (mod n) i x 6= −y (mod n), to NW D(x+y, n) = d jest nietrywialnym

dzielnikiem

n.

1.21. Problemy

35

1.21.5

Układ kongruencji

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

a

1

= a (mod 3),

(1.8)

a

2

= a (mod 5),

Najpierw szukamy dwóch liczb

a

01

i

a

10

spełniaj¸acych warunki

0 = a

01

(mod 3),

1 = a

01

(mod 5),

1 = a

10

(mod 3),

0 = a

10

(mod 5),

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

a = a

1

· a

10

+ a

2

· a

01

(mod 15).

Jak policzy´c

a

01

oraz

a

10

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

x i y takie,

˙ze

3x + 5y = 1

Poka˙z, ˙ze je˙zeli podstawimy

a

01

= 3x (mod 15) oraz a

10

= 5y

(mod 15), to b¸edzie

dobrze.

1.21.6

Chi ´

nskie twierdzenie o resztach

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

N W D(m, n) = 1, to funkcja

f (x) = (x mod m, x mod n)

stanowi wzajemnie jednoznaczne odwzorowanie pomi¸edzy Z

mn

a iloczynem kartezja ´n-

skim Z

m

× Z

n

.

Na iloczynie kartezja ´nskim Z

m

× Z

n

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

nia w nast¸epuj¸acy sposób:

(a, b) + (c, d) = (a + b, c + d)

(a, b)

· (c, d) = (a · b, c · d).

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

m

× Z

n

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

niem. Ponadto funkcja

f spełnia warunki f (x+y) = f (x)+f (y) oraz f (x

·y) = f(x)·(y).

1.21.7

System one-pad

System „one-pad” (porównaj rozdział o funkcjach boolowskich) mo˙ze by ´c stosowany
do ci¸agów liter alfabetu łaci ´nskiego. Wtedy uto˙zsamiamy litery z liczbami od 0 do 25 i
zamiast operacji

⊕ stosujemy:

x + k

(mod 26),

36

Rozdział 1. Teoria liczb

czyli reszt¸e z dzielenia

(x + k) przez 26. Jak wygl¸ada wtedy operacja deszyfrowania?

Poka˙z, ˙ze system one-pad z literami jest równie bezpieczny jak system z dwoma cyframi
0 i 1.

1.21.8

Przestrze ´

n liniowa

Zbiór

B =

{0, 1} z działaniami xor ⊕ oraz koniunkcji · jest ciałem Z

2

.

Udowodnij, ˙ze zbiór

B

n

jest przestrzeni¸a liniow¸a nad ciałem

{0, 1}, z ⊕ jako doda-

waniem oraz mno˙zeniem przez skalar zdefiniowanym przez:

• 0 · x = 0 (tutaj zero po lewej stronie jest zerem z ciała, a zero po prawej stronie jest

wektorem zerowym),

• 1 · x = x.

1.21.9

Uogólnienie małego twierdzenia Fermata

Udowodnij

Twierdzenie 1.56 Niech

G b˛edzie dowoln ˛

a grup ˛

a. Wtedy dla dowolnego

a

∈ G

a

|G|

= 1

.