Matematyka dyskretna 2004 06 Teoria liczb

Matematyka Dyskretna

Andrzej Szepietowski

25 marca 2004 roku

Rozdział 1

Teoria liczb

1.1

Dzielenie całkowitoliczbowe

Zacznijmy od przypomnienia szkolnego algorytmu dzielenia liczb naturalnych. Podziel-
my 174 przez 12.

2
5

8
6

W wyniku dzielenia otrzymali´smy iloraz 14 i reszt˛e 6 . Liczby te spełniaj ˛

a równanie

174 = 14

· 12 + 6

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

c. Iloraz

całkowitoliczbowy liczb a i b b˛edziemy oznacza´c przez

÷ b

lub

div b.

a reszt˛e przez

mod b.

Rozdział 1. Teoria liczb

Przykład 1.2

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

Powy˙zsze definicje zakładały, ˙ze a i b s ˛

a naturalne. W przypadku, gdy a i b s ˛

a liczba-

mi całkowitymi, iloraz i ró˙znice 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

c — zaokr ˛aglenie ilorazu

w dół, gdy

jest dodatnie i

a
b

e, — 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 a

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

wita z, taka ˙ze:

= az.

B˛edziemy to oznacza´c przez a

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

mod a = 0.

Liczb˛e a nazywamy dzielnikiem liczby b.

Przykład 1.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:

= ak

oraz

= am.

Mamy wi˛ec:

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

oraz

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

czyli a dzieli b

+ c oraz b

− c.

1.3. Relacja kongruencji

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

|(a − b).

B˛edziemy wtedy pisa´c:

= 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 na-

st˛epuj ˛

ace trzy warunki:

• zwrotno´s´c, dla ka˙zdego a zachodzi

= a (mod m),

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

= b (mod m),

= a (mod m),

• przechodnio´s´c, dla ka˙zdego a, b i c,

je˙zeli

= b (mod m)

= c (mod m),

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

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

Twierdzenie 1.7 Je˙zeli

= b (mod m)

oraz

= d (mod m),

to:

+ c = b + d (mod m),

− c = b − d (mod m),

= bd (mod m).

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

|(a − b)

oraz

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

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,

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

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

modulo 3, czyli:

= 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:

· 10

(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), 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

[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

= y

(mod m),

[x] = [y].

Dowód. Je˙zeli z

∈ [x], to

= x

(mod m)

i z przechodnio´sci relacji mamy

= y

(mod m),

czyli z

∈ [y], a wi˛ec pokazali´smy, ˙ze:

[x]

⊂ [y].

Identycznie pokazujemy zawieranie odwrotne

[y]

⊂ [x].

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

aczno´s´c.

Lemat 1.12 Je˙zeli

[x]

∩ [y] 6= ∅,

[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:

= x (mod m)

oraz

= y

(mod m).

Z przechodnio´sci mamy wtedy

= y

(mod m),

a z lematu 1.11

[x] = [y].

1.5

Pier´scie ´n Z

Klasy abstrakcji relacji modulo m wygl ˛

adaj ˛

a nast˛epuj ˛

aco:

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

− 1].

Dla dowolnego k z przedziału

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

[k] =

{jm + k | j ∈ Z}

Rozdział 1. Teoria liczb

(Z oznacza zbiór liczb całkowitych). Zbiór klas abstrakcji modulo m oznacza si˛e przez
Z

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

− u] = [y − w].

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

= y

(mod m)

oraz

= w

(mod m).

a z twierdzenia 1.7:

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

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

Przykład 1.14 Niech m

= 3. Dla dowolnych dwóch liczb x

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

+ 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],

1.5. Pier´scie´n Z

• 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 ˛

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.

1.5.1

Pier´scie ´n Z

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:

{0, 1, 2, 3, 4}

z dodawaniem i mno˙zeniem okre´slonym nast˛epuj ˛

acymi tabelami:

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

element odwrotny wzgl˛edem mno˙ze-

nia, czyli dla ka˙zdego x

∈ Z

− {0} istnieje x

−1

, taki ˙ze xx

−1

= 1:

−1

= 1,

−1

= 3,

−1

= 2,

−1

= 4.

Dlatego Z

jest ciałem, czyli pier´scieniem przemiennym z jedynk ˛

a i z odwrotno´sci ˛

wzgl˛edem mno˙zenia.

1.5.2

Pier´scie ´n Z

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

{0, 1, 2, 3},

gdzie dodawanie i mno˙zenie jest okre´slone nast˛epuj ˛

acymi tabelami:

Rozdział 1. Teoria liczb

x 1

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

mamy:

· 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

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

)q = 1q = q,

czyli q

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

nie jest ciałem, je˙zeli m jest liczb ˛

a zło˙zon ˛

W dalszej cz˛e´sci tego rozdziału zobaczymy, ˙ze je˙zeli m jest liczb ˛

a pierwsz ˛

a, to Z

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 naj-
wi˛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).

Przykład 1.16

N W D

(4, 6) = 2,

N W D

(4, 0) = 4,

N W D

(4,

−6) = 2.

1.7

Algorytm Euklidesa

Aby obliczy´c najwi˛ekszy wspólny dzielnik dwóch dodatnich liczb naturalnych a, b robi-
my co nast˛epuje

dopóki

· b 6= 0 wykonuj:

je˙zeli

≥ b, to

:= a mod b

w przeciwnym przypadku

:= b mod a;

NWD:=a+b

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:

1.7. Algorytm Euklidesa

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.17 Niech a i b b˛ed ˛

a dwoma liczbami naturalnymi i niech

0 < b

≤ a. Wtedy

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

mod b, b.

Dowód. Z definicji ilorazu i reszty mamy

= (a

÷ b) · b + a mod b.

Je˙zeli liczba r jest wspólnym dzielnikiem pary a, b, to r dzieli tak˙ze reszt˛e a

mod b, czyli

r jest wspólnym dzielnikiem pary

(a mod b), b. Na odwrót, je˙zeli liczba r jest wspólnym

dzielnikiem pary

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

a, b.

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

while

para a, b 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 a

= 0 lub

= 0, N W D = a + b, 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 dopóki liczba

max

{a, b}

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.18 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:

+ yb = d,

lub mówi ˛

ac inaczej, d jest kombinacj ˛

a całkowitoliczbow ˛

a liczb a i b.

Dowód. Niech a

i b

oznaczaj ˛

a pocz ˛

atkowe warto´sci zmiennych a i b, odpowiednio.

Poka˙zmy, ˙ze wszystkie warto´sci, jakie przyjmuj ˛

a zmienne a i b w trakcie wykonywania

algorytmu Euklidesa, s ˛

a całkowitoliczbowymi kombinacjami liczb a

i b

. Na pocz ˛

atku,

gdy a

= a

i b

= b

, mamy:

= 1a

+ 0b

= 0a

+ 1b

Załó˙zmy teraz, ˙ze po i-tej iteracji p˛etli a > b oraz ˙ze zachodzi:

= x

+ y

= x

+ y

Rozdział 1. Teoria liczb

Wtedy w

(i + 1) iteracji a b˛edzie pomniejszone o b

· (a ÷ b) i b˛edziemy mieli:

= (x

− x

· (a ÷ b))a

+ (y

− y

· (a ÷ b))b

oraz

= x

+ y

Z tego wynika, ˙ze tak˙ze ostateczna warto´s´c d jest kombinacj ˛

a liczb a

i b

1.7.1

Rozszerzony algorytm Euklidesa

Algorytm Euklidesa mo˙zna tak zmodyfikowa´c, aby oprócz najwi˛ekszego wspólnego dziel-
nika N W D

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

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

Oto ten algorytm

:= 1; y

:= 0;

:= 0; y

:= 1;

dopóki

· b 6= 0 wykonuj:

je˙zeli

≥ b, to

:= a mod b

:= x

− x

∗ (a ÷ b);

:= y

− y

∗ (a ÷ b)

w przeciwnym przypadku

:= b mod a;

:= x

− x

∗ (b ÷ a);

:= y

− y

∗ (b ÷ a)

N W D

:= a + b

je˙zeli

a >

0, to x := x

; y := y

;

je˙zeli

b >

0, to x := x

; y := y

;

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

desa na parze liczb 36 i 15:

-2

-12

-2

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.

1.8. Liczby pierwsze i wzgl˛ednie pierwsze

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 ˛

+ yb,

a wi˛ec dzieli tak˙ze najwi˛ekszy wspólny dzielnik N W D

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

lemat.

Lemat 1.19 N W D

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

Z lematu 1.19 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.20 Liczba naturalna d jest najwi˛ekszym wspólnym dzielnikiem liczb a i b wtedy
i tylko wtedy gdy d jest wspólnym dzielnikiem a i b oraz istniej ˛

a liczby całkowite x i y,

takie ˙ze d

= xa + yb.

Dowód Je˙zeli N W D

(a, b) = d to d

|a, d|b oraz (z twierdzenia 1.18) istniej ˛a liczby całko-

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

Wniosek 1.21 Je˙zeli istniej ˛

a liczby całkowite x i y, takie, ˙ze xa

+yb = 1, to N W D(a, b) =

Przykład 1.22 Poniewa˙z:

2000

− 1998 = 2

oraz 2 jest wspólnym dzielnikiem 1998 i 2000, wi˛ec N W D

(1998, 2000) = 2.

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.

Rozdział 1. Teoria liczb

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

· 3

180 = 2

· 3

· 5.

Przyjmujemy przy tym, ˙ze je˙zeli liczba jest pierwsza, to jej rozład składa si˛e tylko z jednej
liczby.

Twierdzenie 1.23 Ka˙zd ˛

a liczb˛e naturaln ˛

a n >

1 mo˙zna przedstawi´c jako iloczyn liczb

pierwszych (niekoniecznie ró˙znych):

= q

· · · q

Dowód nie wprost. 2 jako liczba pierwsza ma trywialny rozkład składaj ˛

acy si˛e z jednej

liczby. Przypu´s´cmy, ˙ze istnieje liczba naturalna n, której nie mo˙zna przedstawi ´c jako
iloczynu liczb pierwszych i ˙ze n jest najmniejsz ˛

a tak ˛

a liczb ˛

a. n nie mo˙ze by ´c liczb ˛

pierwsz ˛

a (bo wtedy n

= q

), wi˛ec n jest liczb ˛

a zło˙zon ˛

a, czyli jest postaci:

= 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

= p

· · · p

oraz

= r

· · · r

ale wtedy, wbrew zało˙zeniu, mamy rozkład liczby n na czynniki pierwsze:

= p

· · · p

· · · r

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.24 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.18, istniej ˛

a dwie liczby całkowite x i y, takie ˙ze:

+ 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 ˛

stron˛e, czyli c.

1.10. Elementy odwracalne

Lemat 1.25 Je˙zeli liczba pierwsza p dzieli iloczyn liczb pierwszych

· · · q

(niekoniecznie ró˙znych), to wtedy p jest równe jednej z liczb q

Dowód przez indukcj˛e ze wzgl˛edu na r. Dla r

= 1 mamy p

, a poniewa˙z q

jest

pierwsza i p >

1, wi˛ec p = q

Załó˙zmy teraz, ˙ze teza zachodzi dla r i przypu´s´cmy, ˙ze p dzieli

· · · q

Mamy dwa przypadki: albo p dzieli q

, albo nie. W pierwszym przypadku p

= q

W drugim przypadku mamy N W D

(p, q

) = 1, bo 1 i q

to jedyne dzielniki liczby

. Z lematu 1.24 wynika teraz, ˙ze p dzieli q

· · · q

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

= q

dla jakiego´s

≤ i ≤ r.

Udowodnimy teraz, ˙ze rozkład liczby na czynniki pierwsze jest jednoznaczny, z dokład-
no´sci ˛

a do kolejno´sci czynników.

Twierdzenie 1.26 Ka˙zd ˛

a liczb˛e naturaln ˛

a n >

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

stawi´c w postaci iloczynu:

= p

. . . p

gdzie α

s ˛

a dodatnimi liczbami naturalnymi, p

s ˛

a liczbami pierwszymi oraz zachodzi

< p

< . . . < p

Dowód. Twierdzenie 1.23 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:

= p

. . . p

= q

. . . q

(1.1)

Wtedy z jednej strony p

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 p

dzieli praw ˛

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

Lemat 1.27 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.28 Element a

∈ Z

jest odwracalny, je˙zeli istnieje b

∈ Z

, takie, ˙ze

· b = 1 (mod m).

b nazywamy elementem odwrotnym do a i oznaczamy przez a

−1

Rozdział 1. Teoria liczb

Przykład 1.29 Liczba

3 jest odwracalna w Z

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

odwracalne s ˛

a tak˙ze

1, 5 i 7.

Lemat 1.30 Liczba a

∈ Z

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:

+ ym = 1,

a wi˛ec m dzieli ax

− 1, czyli:

= 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

−1

= 1 (mod m)

czyli

−1

− 1 = k · m

dla jakiego´s k. Mamy wi˛ec

−1

+ (

−k)m = 1

czyli N W D

(a, m) = 1 (wniosek 1.21).

Z powy˙zszego dowodu wynika, ˙ze element odwrotny do a mo˙zna wyliczy ´c stosuj ˛

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

Najpierw zastosujemy algorytm Euklidesa, aby obliczy´c x i y, takie ˙ze:

12x + 17y = 1.

Kolejne kroki algorytmu przedstawiono w tabeli:

-1

-2

-7

-2

-7

-12

Mamy wi˛ec:

· 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

1.11. Funkcja liniowa

Definicja 1.31 Zbiór elementów odwracalnych w Z

oznaczamy przez Z

∗

Przykład 1.32 Z

∗

{1, 3, 5, 7}.

Lemat 1.33 Je˙zeli liczba m jest pierwsza, to ka˙zdy element a

∈ Z

, a

6= 0, jest odwra-

calny, czyli pier´scie´n Z

jest ciałem.

Lemat 1.34 Je˙zeli a, b

∈ Z

∗

to ab

∈ Z

∗

oraz a

−1

∈ Z

∗

To oznacza, ˙ze Z

∗

z mno˙zeniem jest grup ˛

Dowód: Elementem odwrotnym do iloczynu ab jest b

−1

, a elementem odrotnym do

−1

jest a.

1.11

Funkcja liniowa

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

działa funkcja liniowa

(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

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

(g(x)) = aa

−1

= x.

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

∈ Z

równanie

= b

ma dokładnie jedno rozwi ˛

azanie w pier´scieniu Z

, jest ono równe x

= a

−1

Funkcja f jest permutacj ˛

a w Z

i wykorzystuje si˛e j ˛

a, gdy trzeba wymiesza´c (prze-

permutowa´c) elementy Z

. Zauwa˙zmy, ˙ze f jest tak˙ze permutacj ˛

a w Z

∗

. Rzeczywi´scie,

je˙zeli x

∈ Z

∗

, to na podstawie lematu 1.34 f

(x) = ax

∈ Z

∗

. Mamy wi˛ec

Lemat 1.35 Je˙zeli N W D

(a, m) = 1, to funkcja f (x) = ax jest funkcj ˛

a wzajemnie

jednoznaczn ˛

a w Z

i w Z

∗

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

Rozdział 1. Teoria liczb

Zauwa˙zmy, ˙ze je˙zeli b jest warto´sci ˛

a funkcji f , czyli gdy

= b (mod m)

to istnieje takie k, ˙ze

− 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.36 Je˙zeli N W D

(a, m) = d oraz d

|b, to równania

= b (mod m)

oraz

a
d

(mod

)

s ˛

a równowa˙zne, czyli maj ˛

a ten sam zbiór rozwi ˛

aza´n w zbiorze liczb całkowitych.

Dowód

= b (mod m)

wtedy i tylko wtedy, gdy istnieje k takie ˙ze

− b = km,

a to zachodzi wtedy i tylko wtedy, gdy istnieje k takie, ˙ze

a
d

−

= k

czyli wtedy i tylko wtedy, gdy

a
d

(mod

Przypu´s´cmy teraz, ˙ze d dzieli b i rozwi ˛

a˙zmy równanie

= b

(1.2)

w pier´scieniu Z

, czyli szukamy takich x

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

= b (mod m)

(1.3)

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

(mod

)

(1.4)

1.12. Szyfry liniowe

Ale teraz N W D

(

a
d

) = 1 i równanie (1.4) ma dokładnie jedno rozwi ˛

azanie x

∈

{0, . . . ,

− 1} takie ˙ze

a
d

(mod

Ale równania (1.4) i (1.3) s ˛

a spełnione tak˙ze przez liczby

, x

+ 2

, . . . , x

+ (d

− 1)

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

Przykład 1.37 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

mamy

−1

= 3 wi˛ec rozwi ˛

azaniem jest x

= 3

· 3 = 4. Tak wi˛ec rozwi ˛

azaniami

równaia (1.5) w Z

s ˛

a liczby

4, 9, 14.

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

= 0,

= 1,

= 2, . . . , z = 25,

wybieramy dwie liczby a, b

∈ Z

, takie ˙ze N W D

(a, 26) = 1, i szyfrujemy litera po

literze według wzoru:

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

Funkcja deszyfruj ˛

aca jest okre´slona wzorem:

(y) = a

−1

− a

−1

(mod 26).

Rzeczywi´scie:

(C(x)) = a

−1

(ax + b)

− a

−1

= a

−1

+ a

−1

− a

−1

= x.

Z tego wynika, ˙ze funkcja szyfruj ˛

aca C

(x) jest wzajemnie jednoznaczna.

Rozdział 1. Teoria liczb

Przykład 1.38 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)

szyfr

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.

Szyfry liniowe s ˛

a bardzo starym wynalazkiem. W prostszej wersji z a

= 1 stosował je

ju˙z Juliusz Cezar. Ich wad ˛

a jest to, ˙ze bardzo łatwo daj ˛

a si˛e łama ´c. Czasami wystarcza od-

gadn ˛

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.39 (kontynuacja przykładu 1.38) 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˛e-
ciu, ˙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

. Jest to 21, poniewa˙z:

(

−5)5 + 26 = 1

oraz

− 5 = 21 (mod 26),

tak wi˛ec:

= 21

· 11 = 231 = 23 (mod 26).

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

= 15

− 19 · 23 = 20 (mod 26).

1.13. Chi ´nskie twierdzenie o resztach

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:

= 3,

= 5,

= 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:

= 2

= 3.

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

(mod 2)

(mod 3)

Ka˙zda z liczb od 0 do

5 = 2

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

, a

), spełniaj ˛

acych warunek

≤ a

2, 0

≤ a

3, istnieje liczba a, taka ˙ze:

= a (mod 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:

= b + k

· 6

dla jakiego´s całkowitego k, to

(mod 2) = b (mod 2),

(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ład-
no´sci ˛

a do pi˛eciu.

Rozdział 1. Teoria liczb

Sytuacja jest inna, je˙zeli m

i m

nie s ˛

a wzgl˛ednie pierwsze. Je˙zeli, na przykład,

= 4 i m

= 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

i m

s ˛

a wzgl˛ednie pierwsze, to ka˙zda z liczb od 0 do m

· m

− 1 ma

inny zestaw reszt oraz dla ka˙zdej pary reszt

, a

), spełniaj ˛

acych warunek

≤ a

< m

, istnieje liczba a, taka ˙ze:

= a (mod m

zachodzi bowiem poni˙zsze twierdzenie.

Twierdzenie 1.40 (chi ´nskie twierdzenie o resztach) Niech

, m

, . . . , m

b˛ed ˛

a dodatnimi liczbami wzgl˛ednie pierwszymi, to znaczy dla ka˙zdej pary

≤ i < j ≤ r

mamy N W D

, m

) = 1, oraz niech

, a

, . . . , a

b˛ed ˛

a dowolnymi resztami. Wtedy istnieje liczba całkowita a, taka ˙ze:

= a (mod m

(1.6)

. . .

= a (mod m

Ponadto je˙zeli liczby a i b s ˛

a rozwi ˛

azaniami układu kongruencji (??), to ich ró˙znica

− b dzieli si˛e przez iloczyn wszystkich liczb m

, czyli przez:

1.13. Chi ´nskie twierdzenie o resztach

Dowód. Najpierw udowodnimy drug ˛

a cz˛e´s´c twierdzenia. Dla ka˙zdego

≤ i ≤ r mamy:

= a (mod m

)

oraz

= b (mod m

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

0 = a

− b (mod m

czyli

|(a − b),

Druga cz˛e´s´c twierdzenia wynika z nast˛epuj ˛

acego lematu:

Lemat 1.41 Je˙zeli ka˙zda spo´sród liczb m

dzieli a

−b i liczby m

, . . . , m

s ˛

a wzgl˛ednie

pierwsze, to tak˙ze ich iloczyn M dzieli a

− b.

Dowód Lematu. Liczba m

dzieli a

− b, wi˛ec istnieje K

takie, ˙ze

− b = K

· m

Liczba m

te˙z dzieli a

− b, a poniewa˙z jest wzgl˛ednie pierwsza z m

, wi˛ec na podstawie

Lematu 1.24, m

dzieli K

i mamy

− b = K

· m

dla jakiego´s K

. Podobnie, liczba m

jest wzgl˛ednie pierwsza z m

, wi˛ec dzieli iloczyn

· m

, ale jest tak˙ze wzgl˛ednie pierwsza z m

, wi˛ec dzieli K

i mamy

− b = K

· m

dla pewnego K

. Powtarzaj ˛

ac to rozumowanie

razy dochodzimy do wniosku, ˙ze

istnieje takie K

, ˙ze

− b = K

· m

· · · m

Dowód Lematu, ci ˛

ag dalszy. Zobaczymy teraz, ˙ze układ (1.6) ma rozwi ˛

azanie. Niech

, czyli:

= m

· · · m

−1

. . . m

Poniewa˙z M

i m

maj ˛

a rozł ˛

aczne rozkłady, wi˛ec N W D

, M

) = 1 oraz istnieje N

takie ˙ze:

= 1 (mod m

Zauwa˙zmy, ˙ze je˙zeli i

6= j, to m

, oraz ˙ze ka˙zdy iloczyn m

ma nast˛epuj ˛

ac ˛

własno´s´c

= 1 (mod m

= 0 (mod m

)

dla

6= i,

Rozdział 1. Teoria liczb

We´zmy teraz:

Z powy˙zszej własno´sci wynika, ˙ze

= a

(mod m

)

dla ka˙zdego i, a wi˛ec a jest rozwi ˛

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

Przykład 1.42 W przypadku ukłau dwóch równa´n nasze rozumowanie mo˙zna troch˛e upro-
´sci´c. We´zmy, na przykład, układ

= a (mod 3),

(1.7)

= a (mod 5),

Poniewa˙z 3 i 5 s ˛

a wzgl˛ednie pierwsze, wi˛ec istniej ˛

a x i y takie, ˙ze

3x + 5y = 1

Za pomoc ˛

a rozszerzonego algorytmu mo˙zemy wyliczy´c x i y, mamy

· 2 + 5 · (−1) = 1

Teraz zauwa˙zmy, ˙ze iloczyny

· 2 oraz 5 · (−1) maj ˛

a nast˛epuj ˛

ace własno´sci

· 2 = 0 (mod 3),

· 2 = 1 (mod 5),

· (−1) = 1 (mod 3),

· (−1) = 0 (mod 5),

Dlatego liczba

· 3 · 2 + a

· 5 · (−1) = 1

jest rozwi ˛

azaniem układu 1.7

Przykład 1.43 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

(mod 3),

= x (mod 5),

= x

(mod 7),

a na apelu wieczornym było y ˙zołnierzy i otrzymano reszty:

= y

(mod 3),

= y

(mod 5),

= y

(mod 7),

wtedy ró˙znica x

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

− y

= x

− y (mod 3),

− y

= x

− y (mod 5),

− y

= x

− y (mod 7).

1.14. Obliczenia na du˙zych liczbach

1.14

Obliczenia na du˙zych liczbach

Chi´nskie twierdzenie o resztach pozwala wnioskowa´c o du˙zych liczbach za pomoc ˛

a ope-

racji na małych liczbach. Zobaczmy teraz kilka przykładów.

Przykład 1.44 Rozwa˙zmy nast˛epuj ˛

ace równanie.

58 721 569

· 54 567 769 = 71 900 738 · 41 312 424 + 14 969 161 · 15 626 209.

Chi´nskie twierdzenie o resztach daje mo˙zliwo´s´c sprawdzenia tego równania operuj ˛

ac tyl-

ko na stosunkowo małych liczbach. Sprawdzamy to równanie licz ˛

ac modulo kilka niedu-

˙zych liczb wzgl˛ednie pierwszych, na przykład: m

= 999, m

= 1000, m

= 1001,

= 1003, m

= 1007, m

= 1009. Je˙zeli lewa strona równa si˛e prawej modulo

wszystkie te liczby, to równa si˛e tak˙ze w liczbach całkowitych, poniewa˙z iloczyn tych liczb

(10

)

= 10

jest wi˛ekszy od lewej i prawej strony.

Inny sposob, to sprawdzenie tej równo´sci modulo wszystkie liczby pierwsze mniejsze

od 50. Ich iloczyn jest wi˛ekszy od

Przykład 1.45 Zastanówmy si˛e teraz nad rozwi ˛

azaniem równania

· 56 606 581 = 71 900 738 · 41 312 424 + 14 969 161 · 15 626 209.

Je˙zeli spodziewamy si˛e, ˙ze rozwi ˛

azaniem jest liczba naturalna, to znowu mo˙zemy wy-

korzysta´c obliczenia modulo. Wybieramy du˙z ˛

a liczb˛e pierwsz ˛

a p, wi˛eksz ˛

a od ka˙zdej liczby

wyst˛epuj ˛

acej w tym równaniu, a nast˛epnie rozwi ˛

azujemy to równanie w ciele Z

= (56 606581)

−1

· (71 900 738 · 41 312 424 + 14 969 161 · 15 626 209).

Tak otrzymane rozwi ˛

azanie mo˙zemy zweryfikowa´c metod ˛

a z poprzedniego przykładu.

Stosuj ˛

ac t ˛

a metod˛e unikamy zaokr ˛

agle´n, które przy bardziej skomplikowanych rachun-

kach mog ˛

a si˛e kumulowa´c. Mo˙zna, na przykład, w ten sposób rozwi ˛

azywa´c du˙ze układy

równa´n liniowych, w których wszystkie współczynniki i rozwi ˛

azania s ˛

a liczbami całkowi-

tymi.

Przykład 1.46 Zastanówmy si˛e, ile wynosi reszta z dzielenia liczby

= 1 997 199 919

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

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

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

Rozdział 1. Teoria liczb

1.15

Algorytm rosyjskich chłopów mno˙zenia liczb

W poprzednim podrozdziale obliczali´smy iloczyny typu

· y) (mod m).

Je˙zeli wyra˙zenie to b˛edziemy oblicza´c najpierw mno˙z ˛

ac, a potem licz ˛

ac reszt˛e, to wynik

po´sredni x

· y mo˙ze by´c du˙zo wi˛ekszy ni˙z m. W tym podrozdziale poka˙zemy jak oblicza´c

takie wyra˙zenia bez du˙zych wyników po´srednich. W tym celu rozwa˙zmy nast˛epuj ˛

acy

algorytm mno˙zenia dwóch liczb. Algorytm ten był stosowany w Rosji.

Aby pomno˙zy´c dwie liczby a i b naturalne post˛epujemy w nast˛epuj ˛

acy sposób:

• Na pocz ˛atku dwóch kolumn wpisujemy a oraz b

• Powtarzamy nast˛epuj ˛acy ci ˛ag instrukcji dopóki na ko´ncu drugiej kolumny pojawi

si˛e 0.

Ostatni wyraz w pierwszej kolumnie mno˙zymy przez dwa,
Ostatni wyraz drugiej kolumny dzielimy przez 2 (bez reszty).

• Nast˛epnie dodajemy te wyrazy pierwszej kolumny, dla których w drugiej kolumnie

jest liczba nieparzysta.

Przykład 1.47 Poni˙zsza tabela ilustruje działanie algorytmu podczas obliczania

∗ 20.

Do kolumn z wart´sciami a i b dodali´smy na pocz ˛

atku kolumn˛e z numerem rz˛edu.

192

384

768

Teraz nale˙zy doda´c warto´sci z pierwszej kolumny, które znajduj ˛

a si˛e w drugim i czwartym

rz˛edzie, czyli

∗ 20 = 96 + 384 = 480.

Zauwa˙zmy, ˙ze rz˛edy s ˛

a numerowane od zera.

Poprawno´s´c algorytmu wynika z faktu, ˙ze b mo˙ze by´c przedstawione w postaci dwój-

kowej

Poniewa˙z cyfry d

∈ {0, 1}, wi˛ec b jest sum ˛a pot˛eg dwójki. Na przykład

20 = 16 + 4 = 2

+ 2

1.16. Szybkie pot˛egowanie

Pot˛ega

wyst˛epuje w takiej sumie, je˙zeli w rozwini˛eciu dwójkowym b cyfra d

= 1.

Mno˙z ˛

24 przez 20 mamy

· 20 = 24 · (2

+ 2

) = 24

· 2

+ 24

· 2

czyli iloczyn

· 20 jest sum ˛a wszystkich liczb postaci 24 · 2

, dla których d

= 1. Tak

wła´snie liczy algorytm rosyjskich chłopów. W i-tym rz˛edzie pierwszej kolumny mamy
warto´s´c a

∗ 2

. Je˙zeli wyraz w drugiej kolumnie jest nieparzysty to i-ty bit rozwini˛ecia b

jest równy d

= 1.

Zastosujmy teraz algorytm rosyjskich chłopów do obliczania iloczynu

·b (mod m).

Algorytm mno˙zenia

Dane wej´sciowe: czynniki mno˙zenia a oraz b.
Dane wyj´sciowe: Iloczyn a

· b mod m

iloczyn

:= 0

dopóki

b >

0 wykonuj

je˙zeli

mod 2 = 1 to

iloczyn

:= (iloczyn + a) mod m;

:= (2

∗ a) mod m;

:= b

÷ 2;

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

a do Z

i algorytm nie potrzebuje

zbyt du˙zej pami˛eci.

1.16

Szybkie pot˛egowanie

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

mod n dla a

∈ Z

oraz k

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

˙zeniu przez a:

:= 1;

dla

wykonuj
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 k mno˙ze ´n).

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

· a = a

· a

= a

i ogólnie

· a

= a

i+1

Dlatego, aby obliczy´c pot˛eg˛e o wykładniku, który jest pot˛eg ˛

a dwójki k

= 2

nale˙zy

wykona´c

Rozdział 1. Teoria liczb

:= a;

dla

wykonuj
y

:= (y

∗ y) mod n

Przykład 1.48 Aby obliczy´c

w Z

obliczmy

= 2

· 2 = 4 (mod 21),

= 4

· 4 = 16 (mod 21),

= 16

· 16 = 4 (mod 21),

= 4

· 4 = 16 (mod 21).

Je˙zeli wykładnik jest sum ˛

a pot˛eg dwójki k

= 2

+ 2

, to

= a

· a

Przykład 1.49 Aby obliczy´c

mod 21 trzeba wymno˙zy´c

= 2

· 2

· 4 = 16 · 16 = 4 (mod 21).

Zauwa˙zmy, ˙ze ka˙zda liczba naturalna k jest sum ˛

a pot˛eg dwójki

· 2

gdzie d

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

Powy˙zsze uwagi sugeruj ˛

a nast˛epuj ˛

acy algorytm obliczania pot˛egi

(mod m).

• Na pocz ˛atku dwóch kolumn wpisujemy a oraz k

• Powtarzamy nast˛epuj ˛acy ci ˛ag instrukcji dopóki na ko´ncu drugiej kolumny pojawi

si˛e 0.

Ostatni wyraz w pierwszej kolumnie podnosimy do kwadratu modulo m
Ostatni wyraz drugiej kolumny dzielimy przez 2.

• Nast˛epnie wymna˙zamy te wyrazy pierwszej kolumny, dla których w drugiej ko-

lumnie jest liczba nieparzysta.

Jak wida´c algorytm ten jest podobny do algorytmu mno˙zenia z poprzedniego rozdziału.

Przykład 1.50 Poni˙zsza tabela ilustruje działanie algorytmu podczas obliczania

(mod 21).

Do kolumn z wart´sciami a i k dodali´smy na pocz ˛

atku kolumn˛e z numerem rz˛edu.

1.17. Pierwiastki kwadratowe

Teraz nale˙zy wymno˙zy´c warto´sci z pierwszej kolumny, które znajduj ˛

a si˛e w zerowym, i

drugim rz˛edzie, czyli

= 8

· 1 = 8 (mod 5).

Zauwa˙zmy, ˙ze w i-tym wierszu pierwszej kolumny mamy pot˛eg˛e

. Je˙zeli wyraz w drugiej

kolumnie jest nieparzysty to i-ty bit rozwini˛ecia k jest równy d

= 1.

Poni˙zej mamy powy˙zszy algorytm w pseudo Pascalu.

Algorytm szybkiego pot˛egowania

Dane wej´sciowe: podstawa a oraz wykładnik k.

Dane wyj´sciowe: Pot˛ega a

mod n

potega

:= 1

dopóki

b >

0 wykonuj

je˙zeli

mod 2 = 1 to

iloczyn

:= (potega

· a) mod n;

:= (a

∗ a) mod n;

:= b

÷ 2;

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

a do Z

i algorytm nie potrzebuje

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

w liczbach

całkowitych, je˙zeli k jest du˙ze. Wtedy 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

Pierwiastki kwadratowe

Definicja 1.51 Liczb˛e y nazywamy pierwiastkiem kwadratowym liczby x w pier´scieniu
Z

, je˙zeli

= y

(mod m).

Przykład 1.52 W Z

pierwiastkami 4 s ˛

a 2 i 3, poniewa˙z

= 3

= 4 (mod 5)

liczba 2 nie posiada pierwiastka.

Zauwa˙zmy, ˙ze je˙zeli y

= x

(mod m) to

− y)

= m

− 2my + y

= y

= x (mod m),

czyli m

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

Lemat 1.53 Je˙zeli m jest liczb ˛

a pierwsz ˛

a i x

= y

, to y i

−y s ˛

a jedynymi pierwiastkami

z x.

Dowód Je˙zeli z

= y

(mod m), to m dzieli z

− y

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

Rozdział 1. Teoria liczb

Przykład 1.54 Tak nie musi by´c, je˙zeli m nie jest liczb ˛

a pierwsz ˛

a. Na przykład w Z

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

mod p = 1 lub y mod p =

−1

oraz

mod q = 1 lub y mod q =

−1

Wtedy

mod p = 1 oraz y

mod q = 1

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

= 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

, y

. S ˛

a to liczby dla których

mod p = 1,

mod q = 1,

mod p = 1,

mod q =

−1,

mod p =

−1,

mod q = 1,

mod p =

−1

mod q =

−1.

Zauwa˙zmy, ˙ze y

= 1 (mod n) oraz y

−1 (mod n).

1.18

Funkcja Eulera

Definicja 1.55 Funkcja Eulera, jest to funkcja, która liczbie m przypisuje φ

(m) liczb˛e

elementów odwracalnych w Z

. Z definicji przyjmujemy φ

(1) = 1.

Przykład 1.56 φ

(8) = 4, bo w Z

odwracalne s ˛

{1, 3, 5, 7}.

Podobnie φ

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

Lemat 1.57

a) Je˙zeli p jest liczb ˛

a pierwsz ˛

a, to dla dowolnego α

≥ 1, φ(p

) =

−1

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

b) Je˙zeli m i n s ˛

a wzgl˛ednie pierwsze, to φ

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

Dowód:

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

−1

, czyli

) = p

− p

−1

= p

−1

− 1).

1.19. Małe twierdzenie Fermata

Najpierw zauwa˙zmy, ze dla dowolnej liczby x,

≤ 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

= x mod m oraz r

= x mod n speł-

niaj ˛

a warunki

N W D

, m

) = 1 oraz N W D(r

, n

) = 1

(1.8)

Par reszt

, r

) spełniaj ˛

acych warunek (1.8) jest φ

(m)

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

o resztach ka˙zdej liczbie x,

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

1.19

Małe twierdzenie Fermata

Twierdzenie 1.58 (Fermata) Niech a

∈ Z

∗

, wtedy

(m)

= 1 (mod m).

Dowód Niech

, a

, . . . , a

(m)

to b˛ed ˛

a wszystkie elementy Z

∗

. Je˙zeli pomno˙zymy je przez a

, aa

, . . . , aa

(m)

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

Wymnó˙zmy teraz elemnty obu ci ˛

agów

(m)

= a

(m)

(mod m).

Po pomno˙zeniu przez odwrotno´s´c

(m)

otrzymamy tez˛e twierdzenia.

Wniosek 1.59 Je˙zeli p jest liczb ˛

a pierwsz ˛

a, to dla ka˙zdego a wzgl˛ednie pierwszego z p

mamy

−1

= 1 (mod p).

Rozdział 1. Teoria liczb

1.20

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

(x) = x

mod n

i przesyła j ˛

a Alicji. Alicja odszyfrowuje za pomoc ˛

a funkcji deszyfruj ˛

acej

(y) = y

mod n.

Poka˙zemy teraz, ˙ze je˙zeli N W D

(x, n) = 1, to

(x)) = x.

Mamy

(x)) = x

mod n.

Ale

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

(x)) = x

1+kφ(n)

= x

· x

kφ

(n)

(mod n)

ale poniewa˙z N W D

(x, n) = 1, wi˛ec mamy

kφ

(n)

= (x

(n)

)

= 1 (mod n).

Tak wi˛ec D

(x)) = x. W powy˙zszym rozumowaniu zakładali´smy, ˙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

(x)) = x.

1.21. Testy pierwszo´sci

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

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

(m)).

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

(m)) = m.

1.21

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.21.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.21.2

Test Fermata

Drugi test jest algorytmem probabilistycznym i opiera si˛e na twierdzeniu Fermata 1.58.

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

−1

mod n. Je˙zeli a

−1

6= 1 (mod n), to

orzekamy, ˙ze n jest liczb ˛

a zło˙zon ˛

a. Je˙zeli a

−1

= 1 (mod n), to orzekamy, ˙ze liczba n

jest pierwsza.

Zauwa˙zmy, ˙ze je˙zeli wylosujemy liczb˛e a, dla której a

−1

6= 1 (mod n), to wte-

dy mamy pewno´s´c, ˙ze n nie jest liczb ˛

a pierwsz ˛

a. Wynika to bezpo´srednio z twierdze-

nia Fermata1.58. Je˙zeli jednak wylosujemy liczb˛e a wzgl˛ednie pierwsz ˛

a z n, dla której

−1

= 1 (mod n), to wtedy mo˙zemy popełni´c bł ˛

ad. Liczba n mo˙ze by´c zło˙zona, a

mimo to wylosujemy pechowo i a

−1

= 1 (mod n).

Przykład 1.60 W przykładzie 1.50 pokazano, ˙ze

= 8 (mod 21). Z tego wynika,

˙ze

= 8

= 1 (mod 21) oraz , ˙ze 8

= 1 (mod 21).

Definicja 1.61 Tak ˛

a liczb˛e a, dla której N W D

(a, n) = 1 oraz a

−1

6= 1 (mod n) b˛e-

dziemy nazywa´c ´swiadkiem zło˙zono´sci dla n, poniewa˙z za´swiadcza ona, ˙ze n jest zło˙zona.

Przykład 1.62 Jak pokazano wy˙zej

8 nie jest ´swiadkiem zło˙zono´sci dla 21. W przykła-

dzie 1.49 pokazali´smy, ˙ze

= 4 (mod 21), czyli 2 jest ´swiadkiem zło˙zono´sci

liczby

21.

Zachodzi nast˛epuj ˛

acy lemat.

Rozdział 1. Teoria liczb

Lemat 1.63 Je˙zeli istnieje takie a

∈ Z

∗

, ˙ze a

−1

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

wa elementów Z

∗

jest ´swiadkiem Fermata dla n.

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

, . . . , b

}

s ˛

a to wszystkie elementy Z

∗

, dla których b

−1

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

przez a otrzymamy k elementów

{ab

, . . . , ab

}

ró˙znych mi˛edzy sob ˛

a (lemat 1.35), z których ka˙zdy jest ´swiadkiem Fermata. Rzeczywi-

´scie

(ab

)

−1

= a

−1

= a

−1

6= 1 (mod n).

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

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

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

Istniej ˛

a jednak liczby zło˙zone n, które nie maj ˛

a ´swiadków zło˙zono´sci. Na przykład

= 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

560

= (a

)

280

= 1 (mod 3)

560

= (a

)

= 1 (mod 11)

560

= (a

)

= 1 (mod 17)

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

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

n sprawdzamy czy

= 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

− 1 = m · 2

1.21. Testy pierwszo´sci

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

mod n. Je˙zeli a

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

jest pierwsza. Je˙zeli a

mod n

6= 1, to obliczamy po kolei

mod n, a

mod n, . . . , a

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

−1

6= 1 (mod n).

Je˙zeli w tym ci ˛

agu jest jedynka, na przykład

= 1 (mod n)

to patrzymy na poprzedni element x

= a

i−1

. Je˙zeli x

6= −1, to orzekamy, ˙ze n jest

liczb ˛

a zło˙zon ˛

a. Znale˙zli´smy nietrywialny pierwiastek z 1, a z twierdzenia 1.53 wynika,

˙ze jest to mo˙zliwe tylko wtedy gdy n nie jest pierwsze. Je˙zeli x

−1, to orzekamy, ˙ze n

jest pierwsze.

Ł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 liczby

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.

Przykład 1.64 Prze´sled´zmy algorytm Millera-Rabina dla n

= 21 i a = 8.

− 1 = 20 = 5 · 2

W przykładzie 1.50 pokazali´smy, ˙ze

= 8 (mod 21).

Teraz podnosimy

8 do kwadratu i otrzymujemy

5·2

= 8

= 1 (mod 21).

W tym momencie algorytm znalazł nietrywialny pierwiastek 1 i orzeka, ˙ze

21 jest liczb ˛

zło˙zon ˛

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

, . . . , p

Dobór d zale˙zy od tego jak du˙ze liczby sprawdzamy. W ten sposób eliminujemy du˙z ˛

cz˛e´s´c liczb. Zauwa˙zmy, ˙ze obliczaj ˛

ac iloczyn tych liczb

Rozdział 1. Teoria liczb

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 stosujemy 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.21.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.22

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

· (37)

mod 7.

4. Oblicz: a)

∗ 18 + 2002) mod 5,

5. Oblicz: a)

mod 11, b) 2

mod 5 c) 7

mod 10.

6. Przedstaw klasy abstrakcji relacji kongruencji dla m

= 6.

7. Jak wygl ˛

adaj ˛

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

8. W pier´scieniu Z

wykonaj działania

7 + 6 oraz 7

· 6.

9. W pier´scieniu Z

rozwi ˛

a˙z równania: a)

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

5 + x = 2.

10. Podaj tabliczk˛e dodawania i mno˙zenia w ciele Z

. Podaj elementy odwrotne do 5 i

6 w Z

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

12. Oblicz N W D

(667, 713).

13. Oblicz N W D

(199816, 199819).

14. W pier´scieniu Z

rozwi ˛

a˙z równania: a)

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

15. W pier´scieniu Z

rozwi ˛

a˙z równania: a)

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

16. W pier´scieniu Z

rozwi ˛

a˙z równania: a)

8x = 2,

9x = 4.

17. W pier´scieniu Z

rozwi ˛

a˙z równania: a)

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

1.22. Zadania

18. Znajd´z liczby całkowite x i y spełniaj ˛

ace równanie:

17x + 40y = 1.

19. Podaj rozkład na czynniki pierwsze liczb

240 oraz 111.

20. Ile dzielników ma liczba

240?

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

22. Udowodnij, ˙ze dla ka˙zdego a

∈ Z

istnieje co najwy˙zej jeden element odwrotny

−1

23. Przedstaw tabel˛e funkcji f

(x) = 4

· x + 5 w pier´scieniu Z

24. Przedstaw tabel˛e funkcji f

(x) = 4

· x + 5 w pier´scieniu Z

25. Rozwi ˛

a˙z układ kongruencji:

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

26. Sprawd´z, czy

100136 = 200146 (mod 30)

27. Dla jakich par reszt

, a

) istniej ˛

a liczby a spełniaj ˛

ace układ kongruencji:

= a (mod 4),

= a (mod 6).

28. Które elementy Z

s ˛

a resztami kwadratowymi?

29. Które elementy Z

s ˛

a resztami kwadratowymi?

30. Ile jest pierwiastków z

1 w Z

31. Poka˙z, ˙ze w Z

105

jest osiem pierwiastków z

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

mod 15; b)8

mod

65; c) 12

mod 65; d)14

mod 65; e) 10

mod 33.

33. Przeprowad´z test Fermata dla: a) n

= 15 oraz a = 4; b) n = 65 oraz a = 8; c)

= 65 oraz a = 12.

34. Przeprowad´z test Millera-Rabina dla: a) n

= 39 oraz a = 5; b) n = 65 oraz

= 8; a) n = 65 oraz a = 12.

35. Oblicz: a) φ

(24); b) φ(120).

36. Niech

Ω =

{0, 1, . . . , 59}, b˛edzie przestrzeni ˛a zdarze´n elementarnych z jednostaj-

nym rozkładem prawdopodobie ´nstwa. Okre´slmy na

Ω trzy zmienne losowe

(ω) = ω mod 4

(ω) = ω mod 5

(ω) = ω mod 6

Poka˙z, ˙ze zmienne X

i X

s ˛

a niezale˙zne, a zmienne X

i X

nie s ˛

a niezale˙zne.

Rozdział 1. Teoria liczb

37. Niech

Ω =

{0, 1, . . . , 104}, b˛edzie przestrzeni ˛a zdarze´n elementarnych z jedno-

stajnym rozkładem prawdopodobie ´nstwa. Okre´slmy na

Ω trzy zmienne losowe

(ω) = ω mod 3

(ω) = ω mod 5

(ω) = ω mod 7

Poka˙z, ˙ze zmienne X

, X

i X

s ˛

a niezale˙zne.

1.23

Problemy

1.23.1

Najwi˛ekszy wspólny dzielnik

1. Udowodnij, ˙ze ka˙zda liczba postaci xa

+ yb, dla x i y całkowitych, jest wielo-

krotno´sci ˛

a N W D

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

+ 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)?

6. Niech r

, ... , r

b˛edzie ci ˛

agiem kolejnych reszt uzyskiwanych w alorytmie Eukli-

desa. Poka˙z, ˙ze dla ka˙zdego i

≤ k − 2, mamy r

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

, ..., m

to m jest wzgl˛ednie pierwsze z iloczynem tych liczb

k
i

1.23. Problemy

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

= y

(mod n) oraz

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

dzielnikiem n.

1.23.5

Chi ´nskie twierdzenie o resztach

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

(m, n) = 1, to funkcja

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

stanowi wzajemnie jednoznaczne odwzorowanie pomi˛edzy Z

a iloczynem kartezja ´n-

skim Z

× Z

Na iloczynie kartezja ´nskim Z

× Z

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

× Z

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

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:

+ k

(mod 26),

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

Przestrze ´n liniowa

Zbiór B

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

Udowodnij, ˙ze zbiór B

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.

Rozdział 1. Teoria liczb

1.23.8

Uogólnienie małego twierdzenia Fermata

Udowodnij

Twierdzenie 1.65 Niech G b˛edzie dowoln ˛

a grup ˛

a. Wtedy dla dowolnego a

∈ G

|G|

= 1

1.23.9

Algorytm Euklidesa dla wielomianów

Rozwa˙zmy zbiór wielomianów, którego współczynniki s ˛

a elementami jakiego´s ciała, na

przykład zbioru liczb rzeczywistych lub Z

. W pierwszym rozdziale pokazali´smy jak

mo˙zna dzieli´c wielomiany i dla dwóch wielomianów p i q wyliczy´c iloraz i reszt˛e z dzie-
lenia. Mówimy, ˙ze wielomian p dzieli wielomian q, je˙zeli istnieje wielomian r taki, ˙ze
p

· r = q. Mo˙zna te˙z dla wielomianów p i q zdefiniowa´c najwi˛ekszy wspólny dzielnik,

jako taki wielomian d, który dzieli p i q oraz jest podzielny przez ka˙zdy wspólny dzielnik
wielomianów p i q. Poka´z, ˙ze

1. Algorytm Euklidesa oblicza najwi˛ekszy wspólny dzielnik dla wielomianów.

2. Je˙zeli N W D

(p, q) = d, to istniej ˛

a wielomiany x i y, takie, ˙ze

· x + q · y = d.

3. Mo˙zna zdefiniowa´c w pier´scieniu wielomianów relacj˛e przystawania modulo wie-

lomian m, która ma podobne własno´sci do relacji kongruencji modulo w liczbach
całkowitych.