Arytmetyka modularna [version 4 Jul 2016 ed.] [PDF]

Zitiervorschau

ARYTMETYKA MODULARNA Grzegorz Szkibiel Wiosna 2015/16

Spis tre±ci 1 Denicja kongruencji i jej podstawowe wªasno±ci

3

2 Systemy pozycyjne

8

3 Elementy odwrotne

12

4 Pewne zastosowania elementów odwrotnych

17

5 Maªe Twierdzenie Fermata

20

6 Twierdzenie Eulera

23

7 Twierdzenie Lagrange'a

27

8 Chi«skie Twierdzenie o Resztach

30

9 RSA i gra w orªa i reszk¦ przez telefon

36

10 Kongruencje wy»szych stopni

40

11 Liczby pseudopierwsze

46

12 Pierwiastki pierwotne

51

13 Istnienie pierwiastków pierwotnych

55

14 Logarytm dyskretny

60

15 Pewne zastosowania pierwiastków pierwotnych

63

2

Wykªad 1 Denicja kongruencji i jej podstawowe wªasno±ci Podstawow¡ ide¡ arytmetyki modularnej jest zredukowanie skomplikowanych oblicze«. Jednym ze sposobów jest zast¡pienie dziaªa« na liczbach przez dziaªania na resztach z dzielenia tych liczb przez inn¡ liczb¦. Na przykªad, aby stwierdzi¢ jaka jest ostatnia cyfra sumy

145328 + 334245

nie trzeba wyko-

nywa¢ caªego dodawania, tylko doda¢ ostatnie cyfry tych liczb, tj. reszty z dzielenia przez 10. Otrzymujemy

8 + 5 = 13, czyli ostatni¡ cyfr¡ naszej sumy

jest 3.

223837653 jest kwadratem innej liczby. Je±li tak, to jej ostatni¡ cyfr¡ jest jedna z ostatnich cyfr liczb 0 · 0 = 0, 1 · 1 = 1, 2 · 2 = 4, 3 · 3 = 9, 4 · 4 = 16, 5 · 5 = 25, 6 · 6 = 36, 7 · 7 = 49, 8 · 8 = 64, 9 · 9 = 81, czyli 0, 1, 4, 5, 6 lub 9 (dodatkowo zauwa»my, »e je±li liczba n jest kwadratem i jej ostatni¡ cyfr¡ jest zero, to liczba zer na ko«cu jest Sprawd¹my teraz, czy liczba

parzysta). Poniewa» cyfry 3 nie ma na powy»szej li±cie, wi¦c 223837653 nie jest kwadratem liczby caªkowitej.

m mod n dla reszty z dzielenia liczby caªkon ró»n¡ od zera. Z dziaªania tego korzystamy

Wprowad¹my teraz oznaczenie witej

m przez

liczb¦ caªkowit¡

cz¦sto w »yciu codziennym: Je±li teraz jest godzina 10.45, to za póª godziny b¦dzie godzina 11 minut

(45 + 30) mod 60,

czyli 15.

Symbol ,, mod  oznacza dziaªanie arytmetyczne. tego dziaªania ustalimy liczb¦

m,

Kiedy w nast¦pniku

a za poprzednik b¦dziemy brali kolejne

liczby caªkowite, to zauwa»ymy, »e wynik dziaªania powtarza si¦ co

m

liczb.

Liczby, które daj¡ ten sam wynik, gdy podziaªa si¦ na nie t¡ sam¡ liczb¡ nazywamy przystaj¡cymi modulo

m.

Przypu±¢my, »e

3

m,

a, b, m 6= 0 s¡ liczbami

a przystaje do b modulo m,

caªkowitymi. Mówimy, »e

co zapisujemy

a ≡ b (mod m), m | a − b. Zapis moduªem kongruencji. je±li

1.1 Przykªad.

kongruencj¡.

(1.1) nazywamy

Poniewa»

23 ≡ 14 (mod 3).

9 | 23 − 14,

(1.1)

wi¦c

Liczb¦

m

nazywamy

23 ≡ 14 (mod 9). Mamy te» {. . . , −4, 5, 14, 23, 32, . . . }

Ka»de dwie liczby ze zbioru

przystaj¡ do siebie modulo 9.

a oraz b przystaj¡ do siebie modulo 1 oraz a ≡ b (mod 1) oraz a ≡ b (mod −1). Dlatego nie

Ka»de dwie liczby caªkowite modulo

−1.

Mamy wi¦c

warto rozwa»a¢ kongruencji o module 1. Poniewa»

a ≡ b (mod m)

implikuje

a ≡ b (mod −m),

wi¦c rozwa»amy

tylko dodatnie moduªy. Od tej pory zakªadamy, »e moduª kongruencji jest liczb¡ caªkowit¡ dodatni¡ wi¦ksz¡ od 2. Przypomnimy teraz znany fakt o dzieleniu z reszt¡.

1.2 Twierdzenie. Je±li a, m ∈ Z oraz m 6= 0, to istniej¡ jednoznacznie zdeniowane liczby q ∈ Z oraz r ∈ {0, 1, . . . , m − 1}, takie »e a = q · m + r. Dowód.

Je±li

m = 1,

to

a = a·m+0

a oraz m = −1:

i liczby

jednoznacznie. Podobnie mamy w sytuacji, gdy

0 s¡ wyznaczone

a = (−a)m + 0. Zaªó»my wi¦c, »e rze

R

| m| > 1

i rozwa»my zbiór

R = {a − xm : x ∈ Z}.

istnieje przynajmniej jedna liczba dodatnia.

W zbio-

Aby to zauwa»y¢, wy-

gdy a < 0 oraz m > 0, to za x a − xm ≥ | a|. Niech y b¦dzie najmniejsz¡ liczb¡ nieujemn¡ nale»¡c¡ do R. Wówczas a − xm = y , czyli a = xm + y . Poka»emy, »e y < m. Istotnie, gdyby y byªo wi¦ksze od m − 1, to y − m ≥ 0 oraz y − m = a − (x + 1)m, czyli y − m ∈ R i y − m < y , sk¡d sprzeczno±¢. Zatem pokazali±my istnienie liczb q oraz r . Zaªó»my, »e istniej¡ dwa ró»ne zapisy a = q1 m + r1 oraz a = q2 m + r2 , przy czym r1 , r2 ∈ R. Wówczas (q1 − q2 )m = r2 − r1 . Ale | r2 − r1 | < m oraz m | r2 − r1 , wi¦c r2 − r1 = 0. Dalej, (q1 − q2 )m = 0, wi¦c skoro m 6= 0, tak»e q1 − q2 = 0. starczy rozwa»y¢ kilka przypadków, np. mo»na wzi¡¢ liczb¦

a.

Wtedy

4

Z powy»szego twierdzenia wynika, »e kongruencja (1.1) oznacza, »e oraz

b

daj¡ takie same reszty przy dzieleniu przez

m,

a

czyli

a mod m = b mod m. m - a − b, to fakt ten zapisujemy a 6≡ b (mod m) i mówimy, »e a nie przystaje do b modulo m. Ustalmy teraz liczb¦ m i zdeniujmy na zbiorze Z relacj¦ ρ nast¦puj¡co: Je»eli

aρb ⇐⇒ a ≡ b (mod m)

(1.2)

1.3 Twierdzenie.

Relacja zdeniowana w (1.2) jest relacj¡ równowa»no±ci. Klasy abstrakcji tej relacji tworz¡ zbiór reszt modulo m.

Dowód.

Wystarczy pokaza¢, »e relacja (1.2) jest zwrotna, symetryczna i prze-

chodnia, czyli »e 1.

a ≡ a (mod m);

2. je±li

a ≡ b (mod m),

3. Je±li

a ≡ b (mod m)

to

b ≡ a (mod m);

oraz

b ≡ c (mod m),

to

a ≡ c (mod m).

a − a = 0, zatem m | a − a. Symetryczno±¢, czyli 2, wynika z faktu, »e b − a = −(a − b), wi¦c je±li m | a − b, to m | b − a. Aby pokaza¢ 3, zapiszmy m | a − b oraz m | b − c. St¡d m | (a − b) + (b − c), czyli m | a − c. Aby pokaza¢ 1, zauwa»my, »e

Zbiór ilorazowy relacji (1.2) oznaczamy

Z/mZ

lub

Zm .

Zatem

Z5

skªada

si¦ z nast¦puj¡cych zbiorów:

[0] = {. . . , −10, −5, 0, 5, 10, 15, . . . } , [1] = {. . . , −9, −4, 1, 6, 11, 16, . . . } , [2] = {. . . , −8, −3, 2, 7, 12, 17, . . . } , [3] = {. . . , −7, −2, 3, 8, 13, 18, . . . } , [4] = {. . . , −6, −1, 4, 9, 14, 19, . . . } . Zazwyczaj uto»samiamy elementy

0, 1, 2, 3, 4 z klasami abstrakcji, Z5 = {0, 1, 2, 3, 4}.

które s¡

przez nie reprezentowane. Piszemy wi¦c

Okazuje si¦, »e kongruencjami mo»na manipulowa¢ bez wyra»ania liczb za pomoc¡ reszt i ilorazów cz¦±ciowych. Przy ustalonym module mo»na dodawa¢, odejmowa¢ i mno»y¢ stronami.

5

m, kongruencje

1.4 Twierdzenie.

Dla dowolnych liczb caªkowitych a, b, c, d oraz m 6= 0 je±li a ≡ b (mod m) oraz c ≡ d (mod m), to równie» (a) a + c ≡ b + d (mod m), (b) a − c ≡ b − d (mod m), (c) ac ≡ bd (mod m). Dowód.

m | a − b oraz m | c − d, wi¦c m | a − b + c − d, co dowodzi (a), oraz m | a − b − (c − d), co dowodzi (b). Aby pokaza¢ (c), zapiszmy ms = a − b oraz mr = c − d i rozwa»my ac − bd. Mamy Poniewa»

ac − bd = ac − ad + ad − bd = a(c − d) + d(a − b) = mra + msd = m(ra + sd). St¡d

m | ac − bd,

Poniewa»

czyli teza

(c)

c ≡ c (mod m),

jest prawdziwa.

wi¦c punkt

(c)

powy»szego twierdzenia impli-

kuje nast¦puj¡cy wniosek.

1.5 Wniosek.

Dla dowolnych liczb caªkowitych a, b, c oraz m 6= 0, je»eli a ≡ b (mod m), to ac ≡ bc (mod m).  Pot¦gowanie o wykªadniku naturalnym jest wielokrotnym mno»eniem. Dlatego mamy kolejny wniosek.

1.6 Wniosek.

Dla dowolnych liczb caªkowitych a, b, m 6= 0 oraz liczby naturalnej k , je»eli a ≡ b (mod m), to ak ≡ bk (mod m).  Twierdzenie 1.4 oraz wnioski po nim implikuj¡ nast¦puj¡ce twierdzenie, które b¦dziemy pó¹niej cz¦sto u»ywa¢.

1.7 Twierdzenie.

Przypu±¢my, »e dany jest wielomian f (x) o wspóªczynnikach w zbiorze liczb caªkowitych. Je±li a ≡ b (mod m) jest prawdziwa, to zachodzi te» kongruencja f (a) ≡ f (b) (mod m). 

6

Przykªady 1.8.

Jaka jest ostatnia cyfra liczby

323 ?

Poniewa»

32 ≡ 9 34 ≡ 7 · 3 ≡ 1

3 ≡ 3 (mod 10), 3 3 ≡ 9 · 3 ≡ 7 (mod 10), 35 ≡ 1 · 3 ≡ 3 (mod 10),

(mod 10), (mod 10),

wi¦c cyfry w kolejnych pot¦gach liczby 3 powtarzaj¡ si¦ cyklicznie co cztery. 23 3 Zatem 3 ma ostatni¡ cyfr¦ tak¡ sam¡ jak 3 , czyli 7.

1.9.

232 mod 17. Zauwa»my, »e 24 ≡ −1 (mod 17). Zatem 28 = 2 · 2 ≡ (−1) · (−1) = 1 (mod 17). Podobnie dostajemy 216 ≡ 1 (mod 17) 32 oraz 2 ≡ 1 (mod 17). Zatem 232 mod 17 = 1. 4

Znajdziemy 4

Kongruencji nie mo»na dzieli¢ stronami. Istotnie, zauwa»my »e zachodz¡ kongruencje

48 ≡ 30 (mod 6)

oraz

8 ≡ 2 (mod 6),

7

ale

6 6≡ 15 (mod 6).

Wykªad 2 Systemy pozycyjne Warsztatem pracy dla arytmetyka jest zbiór liczb caªkowitych. Liczby caªkowite mo»emy przedstawia¢ w rozmaity sposób, ale najlepszym zdecydowanie sposobem jest zapis pozycyjny.

Przypomnijmy, »e stosowany powszechnie

system zapisu liczb nazywamy systemem pozycyjnym, poniewa» znaczenie cyfry zale»y od pozycji, na której si¦ owa cyfra znajduje.

Poza tym nasz

system liczenia nazywamy dziesi¦tnym, poniewa» mamy dokªadnie 10 cyfr. Liczba cyfr w systemie pozycyjnym zale»y od podstawy. Dokªadnie, dowoln¡ liczb¦ caªkowit¡ nieujemn¡

n

zapisujemy przy podstawie

b≥2

w postaci

(dk−1 dk−2 . . . d1 d0 )b , gdzie

dk−1 , dk−2 , . . . , d1 , d0

nymi oraz niewi¦kszymi od

(2.1)

s¡ liczbami caªkowitymi (dziesi¦tnymi) nieujem-

b − 1.

Liczby te nazywamy cyframi. Zapis (2.1)

oznacza, »e

n = dk−1 bk−1 + · · · + d1 b + d0 . Je»eli

n

jest liczb¡ ujemn¡ to wyra»enie po prawej stronie równo±ci (2.2)

zacz¦liby±my od znaku liczb¡

(2.2)

k -cyfrow¡

−.

Je»eli

dk−1

n jest b = 10 to

nie jest zerem, to mówimy, »e

w systemie pozycyjnym o podstawie

b.

Je»eli

nawiasy w (2.1) opuszczamy, gdy» wtedy mamy do czynienia ze zwykªym dziesi¦tnym systemem pozycyjnym. Podobnie opu±cimy nawiasy gdy wybór podstawy jasno wynika z kontekstu. liczby

n

przy podstawie

Je»eli

b > 10,

Zapis (2.2) nazywamy rozwini¦ciem

b.

to pisownia niektórych cyfr jest uci¡»liwa (wymaga dodat-

kowych nawiasów) lub niejasna ((101)b mo»na rozumie¢ na dwa sposoby). Dlatego dla oznaczenia cyfr 10, 11, 12,

8

...

u»ywamy liter:

A, B , C , . . .

Oczywi±cie, mo»na u»ywa¢ liter lub innych znaków dla oznaczenia wszystkich cyfr. Na przykªad, podstawa 26 (liczba liter w alfabecie ªaci«skim) jest u»ywana w kryptograi i cyframi s¡ po prostu litery alfabetu. Przypiszmy ka»dej literze alfabetu liczb¦, która jest jej pozycj¡ w alfabecie. Otrzymujemy: 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 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Wówczas przeksztaªcenie stu. Tutaj

n

stawie 26, a

k l > 0. oraz

f (n) = n + k mod BAl

jest szyfrowaniem tek-

s¡ liczbami caªkowitymi zapisanymi w systemie o podKiedy

Cezara. Dla przykªadu, cza J. Mamy

l = 1,

to nasz szyfr nazywamy

zaszyfrujmy sªowo

ARYTMETYKA

cyklicznym

lub

za pomoc¡ klu-

A + J = J, E + J = N, K + J = T, M + J = V, R + J = BA, BA mod BA = A, T + J = BC, BC mod BA = C, Y + J = BH, BH mod BA = H. Zatem szyfrem sªowa

ARYTMETYKA

jest

JAHCVNCHTJ.

Wykorzystuj¡c twierdzenie o podzielno±ci, poka»emy »e istnieje dokªadnie jedno rozwini¦cie liczby caªkowitej nieujemnej w systemie pozycyjnym o pod-

b ≥ 2. Istotnie, je±li dana jest liczba n ≥ 0, to istnieje dokªadnie jedna reszta d0 z dzielenia n przez b, wi¦c n = bq0 + d0 , gdzie 0 ≤ d0 ≤ b − 1. Dalej mamy istnienie dokªadnie jednej liczby 0 ≤ d1 ≤ b − 1, takiej »e q0 = bq1 + d1 , 2 lub »e n = b q1 + bd1 + d0 . Post¦puj¡c tak dalej otrzymamy jednoznacznie okre±lone liczby d0 , d1 , . . . , dk−1 , dla których zachodzi równo±¢ (2.2). Po-

stawie

dobnie, a w zasadzie identycznie pokazujemy, »e rozwini¦cie liczby caªkowitej ujemnej w systemie o podstawie

b

te» jest jednoznaczne.

Podane powy»ej rozumowanie jest te» algorytmem na zmian¦ podstawy systemu na

b.

Aby przej±¢ do podstawy 10, wystarczy jedynie obliczy¢ war-

to±¢ wyra»enia po prawej stronie (2.2). Zatem sprawa si¦ tu znacznie upraszcza.

Zademonstrujemy na przykªadzie, jak przej±¢ z zapisu w systemie o

podstawie 10 do zapisu w systemie o podstawie 3.

2.1 Przykªad.

Zapiszemy liczb¦ 346 w systemie trójkowym, czyli przy pod-

346 = 115·3+1. 2 St¡d 346 = 38 · 3 + 1 · 3 + 1.

stawie 3. Dzielimy 346 na 3 otrzymuj¡c 115, reszta 1. Zatem Teraz dzielimy 115 na 3 otrzymuj¡c 38, reszta 1. Kontynuuj¡c ten proces otrzymamy

346 = 35 + 34 + 2 · 32 + 31 + 1, 9

czyli

346 = (110211)3 .

Je»eli przechodzimy od podstawy

b1 6= 10 do podstawy b2 6= 10, to mo»na

tu przechodzi¢ po±rednio przez podstaw¦ 10. Czasem jednak bardziej efek-

b1

tywne jest zapisanie

i cyfr w systemie o podstawie

pogrupowanie. Je»eli dodatkowo

b1

jest pot¦g¡

b2 ,

b2

oraz odpowiednie

to sposób ten jest bardzo

szybki.

Przykªady 2.2.

(548)16 w systemie dwójkowym. 2 1 · 2 + 1, 4 = 1 · 22 oraz 8 = 1 · 23 , mamy Zapiszemy

Poniewa»

16 = 24 , 5 =

(548)16 = 5 · 162 + 4 · 16 + 8 = 1 · 210 + 1 · 28 + 1 · 26 + 1 · 23 = (10101001000)2 .

2.3.

Zapiszemy n = (212021)3 w systemie o podstawie 9. Grupujemy cyfry 2 po 2 (bo 9 = 3 ) zaczynaj¡c od prawej strony: 21, 20, 21. (Je±li ,,nie starcza cyfr na ostatni¡ grup¦, dodajemy z przodu odpowiedni¡ liczb¦ zer. Poniewa»

(21)3 = 2 · 3 + 1 = 7,

a

(20)3 = 2 · 3 = 6,

wi¦c

n = (767)9 .

Zajmiemy si¦ teraz uogólnieniem pewnych cech podzielno±ci jakie maj¡ liczby w systemie o podstawie 10. Zauwa»my, »e liczba

n

(w systemie dzie-

si¦tnym)

• •

dzieli si¦ przez 2, je»eli jej ostatnia cyfra dzieli si¦ przez 2, dzieli si¦ przez 4, je»eli liczba zªo»ona z dwóch ostatnich cyfr

n

dzieli

si¦ przez 4,

•

ogólnie, liczba cyfr liczby

n

n

dzieli si¦ przez

dzieli si¦ przez

2s ,

je»eli liczba zªo»ona z

s

ostatnich

n.

Podobne reguªy obowi¡zuj¡ przy dzieleniu przez pot¦gi liczby 5, a zachodz¡ one dlatego, »e zarówno 2 jak i 5 s¡ dzielnikami podstawy systemu, czyli 10. Udowodnimy twierdzenie, które uogólnia powy»sze fakty.

2.4 Twierdzenie. Przypu±¢my, »e d|b. Wówczas liczba n zapisana w systemie pozycyjnym o podstawie b dzieli si¦ przez ds (s ≥ 1) wtedy i tylko wtedy, gdy liczba zªo»ona z s ostatnich cyfr liczby n dzieli si¦ przez ds . Dowód ⇒. Przypu±¢my, ds | n. Zapiszmy (2.2) w

»e

n

jest zapisana w systemie o podstawie

troch¦ inny sposób, mianowicie

n = ns bs + ds−1 bs−1 + · · · + d1 b + d0 , {z } | n0

10

b

oraz

n a ns liczb¡ zªo»on¡ z pozos s staªych cyfr n (je±li n ma mniej ni» s cyfr, to ns = 0). Poniewa» b | n − ns b , s s s wi¦c n ≡ ns b (mod d ), sk¡d d | n0 . ⇐. Korzystaj¡c z oznacze« wprowadzonych w pierwszej cz¦±ci dowodu zas s s s ªó»my »e d | n0 . Poniewa» d | b , wi¦c d |n. gdzie

n0

jest liczb¡ zªo»on¡ z

s

ostatnich cyfr

Rozwa»ymy jeszcze cech¦ podzielno±ci przez odpowiedniki liczb 3 i 9 w systemie o podstawie

b.

2.5 Twierdzenie.

Zaªó»my, »e d | b − 1. Liczba d dzieli liczb¦ n zapisan¡ w systemie o podstawie b wtedy i tylko wtedy, gdy d dzieli sum¦ cyfr liczby n. Dowód.

Skorzystamy z kongruencji b ≡ 1 (mod d) danej w zaªo»eniu oraz z f (x) = dk−1 xk−1 + dk−2 xk−2 + · · · + d1 x + d0 , gdzie d0 , d1 , . . . ,

wielomianu

dk−1 f (1)

s¡ cyframi liczby

n

w systemie o podstawie

jest sum¡ cyfr liczby

zatem

d | f (b)

n.

b.

Z twierdzenia 1.7 mamy

wtedy i tylko wtedy, gdy

n = f (b), a f (b) ≡ f (1) (mod d),

Wówczas

d | f (1).

Dziaªania arytmetyczne na liczbach w systemie o podstawie bez anga»owania w to podstawy 10.

b wykonujemy

Dodawanie, odejmowanie i mno»enie

pisemne przeprowadzamy tak jak dotychczas, przy czym przy ,,po»yczaniu bierzemy nie 10 lecz

b.

Tak»e uªamki mo»na rozwija¢ przy dowolnej podstawie. Maj¡ one (sko«czon¡ lub niesko«czon¡ posta¢

(dk−1 dk−2 . . . d1 d0 , d−1 d−2 . . . )b .

Warto tu za-

uwa»y¢, »e przy zmianie podstawy, mog¡ te» zmieni¢ si¦ uªamki okresowe. Na przykªad

0, 33333 · · · = (0, 1)3 ,

a

0, 5 = (0, 11111 . . . )3 .

11

Wykªad 3 Elementy odwrotne Jak do tej pory, zauwa»yli±my, »e kongruencje mo»na dodawa¢, odejmowa¢ i mno»y¢ stronami. Zauwa»yli±my te», »e, ogólnie, nie mo»na dzieli¢ kongruencji stronami. Co wi¦cej, nie zachodzi te» prawo skracania: ale

4 ≡ 12 (mod 8),

1 6≡ 3 (mod 8).

3.1 Twierdzenie.

Przypu±¢my, »e c jest dodatni¡ liczb¡ caªkowit¡ oraz ac ≡ bc (mod m) dla pewnych liczb a, b oraz m > 0. Wówczas zachodzi kongrum ). encja a ≡ b (mod NWD(m, c)

Dowód. Oznaczmy d = NWD(m, c) i zapiszmy c = dc0 , m = dm0 . Wówczas 0 0 0 0 NWD(c , m ) = 1. Z drugiej strony, m | c(a − b), czyli dm | dc (a − b), st¡d m0 | c0 (a − b). Poniewa» NWD(c0 , m0 ) = 1, wi¦c m0 | a − b. Skoro jednak m0 = md , wi¦c mamy tez¦. Wracaj¡c do przykªadu poprzedzaj¡cego powy»sze twierdzenie, docelowa kongruencja, to

1 ≡ 3 (mod 2),

poniewa»

8/NWD(4, 8) = 4.

Zauwa»my

jeszcze dwa nast¦puj¡ce fakty. 1. Ka»d¡ kongruencj¦ mo»na skraca¢ przez liczb¦ wzgl¦dnie pierwsz¡ z moduªem, np. wiadomo, »e

48 ≡ 12 (mod 9),

wówczas

12 ≡ 3 (mod 9).

2. Je±li moduª dzieli si¦ przez liczb¦, przez któr¡ chcemy skróci¢ kongruencj¦, to równie» skracamy moduª, np. wiadomo, »e wówczas

48 ≡ 12 (mod 9),

16 ≡ 4 (mod 3).

Cz¦sto si¦ zdarza, »e trzeba ª¡czy¢ kongruencje o ró»nych moduªach. Je±li

a ≡ b (mod m) oraz a ≡ b (mod n), to nie musi koniecznie zachodzi¢ kongruencja a ≡ b (mod mn). Na przykªad, 2 ≡ 10 (mod 8), 2 ≡ 10 (mod 4), ale 2 6≡ 10 (mod 32). Potrzebne jest tu dodatkowe zaªo»enie. 12

3.2 Twierdzenie.

Przypu±¢my, »e

(m, n) = 1. Wówczas

NWD

a ≡ b (mod m) oraz a ≡ b (mod n)

⇔

a ≡ b (mod mn).

Dowód ⇒. Poniewa» m | a − b, wi¦c istnieje taka liczba caªkowita k , »e mk = a − b. Skoro n | mk oraz NWD(m, n) = 1, wi¦c n | k . Zatem istnieje taka liczba k1 , »e nk1 = k . St¡d mnk1 = a − b, czyli a ≡ b (mod mn). ⇐. Skoro a ≡ b (mod mn), wi¦c a ≡ b (mod d) dla dowolnego dzielnika d liczby mn. W szczególno±ci dla m oraz n. Powy»sze twierdzenie pozwala rozbija¢ kongruencje o du»ych zªo»onych moduªach na kongruencje o ni»szych moduªach pierwszych.

Jest to o tyle

istotne, »e ªatwiej jest wydedukowa¢ co± na temat podzielno±ci przez liczb¦ pierwsz¡ ni» przez liczb¦ zªo»on¡.

Na przykªad, aby sprawdzi¢, czy 1729

przystaje do 1 modulo 12, wystarczy sprawdzi¢, czy zachodz¡ kongruencje

1729 ≡ 1 (mod 3)

oraz

1729 ≡ 1 (mod 4).

Jest to ªatwe, poniewa» cechy

podzielno±ci przez 3 i 4 s¡ ªatwe w zastosowaniu. Poniewa» liczba 1728 dzieli si¦ zarówno przez 3 jak i przez 4, wi¦c wspomniane kongruencje zachodz¡. Podobnie jak równania mo»na te» rozwi¡zywa¢ kongruencje. Generalnie,

m

je»eli dany jest moduª

f

oraz funkcja

okre±lona w zbiorze liczb caªkowi-

x, aby speªniona f (x) ≡ 0 (mod m). W tym podrozdziale zajmiemy si¦ kongruencjami liniowymi, czyli takimi, dla których f (x) = ax + b, gdzie a oraz b s¡ liczbami caªkowitymi. Aby upro±ci¢ zapis b¦dziemy dalej pisa¢

tych i o warto±ciach caªkowitych, to pytamy jak znale¹¢ byªa kongruencja

kongruencje liniowe w postaci

ax ≡ b (mod m)

(3.1)

Przypomnijmy, »e w zbiorze liczb rzeczywistych, aby rozwi¡za¢ równanie

ax = b,

mno»ymy obie jego strony przez liczb¦ odwrotn¡ do

istnieje, a nie istnieje tylko dla

a = 0).

w przypadku kongruencji liniowych. odwracalnymi modulo Liczb¦

a

3.3 Przykªad.

m. odwracaln¡ modulo m

Poniewa»

(o ile taka

Dlatego zajmiemy si¦ teraz liczbami

nazywamy

aa0 ≡ 1

a

Podobnie b¦dziemy post¦pujemy

je»eli istnieje taka liczba

(mod m).

2 · 6 ≡ 1 (mod 11),

a0 ,

»e

(3.2)

wi¦c liczby 6 oraz 2 s¡ odwra-

calne modulo 11. Zauwa»my, »e tak»e liczby ró»ni¡ce si¦ od 2 i 6 o wielokrotno±¢ 11 s¡ odwracalne modulo 11. Istotnie, mamy

2 · (6 + 11k) ≡ 2 · 6 ≡ 1 13

(mod 11).

0 Liczba 2 nie jest odwracalna modulo 8, poniewa» je±li 2a ≡ 1 (mod 8), to 0 oznacza to, »e 8 | 2a − 1, czyli 8 dzieli liczb¦ nieparzyst¡, co nie jest prawd¡. Liczby odwracalne modulo

m maj¡ bardzo wygodn¡ charakteryzacj¦ przed-

stawion¡ w twierdzeniu 3.5. Dowód tego twierdzenia dostarcza nam te» me0 tody, jak szuka¢ elementu a . Potrzebny nam jednak b¦dzie lemat.

3.4 Lemat.

Je±li d = NWD(a, b), to istniej¡ liczby caªkowite x oraz y , takie »e ax + by = d. Odwrotnie, dla dowolnych liczb caªkowitych x oraz y ,

(a, b) | ax + by.

NWD

Dowód.

Oznaczmy

S = {am + bn : m, n ∈ Z}.

Zauwa»my, »e w zbiorze

S

s¡

S najmniejsza q . Poka»emy, »e q jest dzielnikiem a. Istotnie, zapiszmy a = eq + t, gdzie 0 ≤ t < q . Poniewa» q = am0 + bn0 dla pewnych m0 , n0 , wi¦c t = (1 − em0 )a + (−n0 )b ∈ S . Zatem t = 0 gdy» w przeciwnym wypadku mieliby±my sprzeczno±¢ z wyborem liczby q . Podobnie pokazujemy, »e t | b. Zauwa»ymy teraz, »e q jest najwi¦kszym wspólnym dzielnikiem liczb a i b. W tym celu przypu±¢my, »e c > 0, c | a oraz c | b. Wówczas c | am + bn dla dowolnych m i n, wi¦c w szczególno±ci, c | q . Zatem c ≤ q . W ostateczno±ci, q = NWD(a, b) i q ∈ S co dowodzi pierwszej cz¦±ci twierdzenia. Z drugiej strony, skoro NWD(a, b) jest dzielnikiem a oraz b, wi¦c jest te» dzielnikiem dowolnego elementu zbioru S . liczby dodatnie. Zatem, zgodnie z zasad¡ minimum, istnieje w liczba dodatnia.

Oznaczmy j¡ przez

3.5 Twierdzenie. Liczba caªkowita a jest odwracalna modulo m wtedy i tylko wtedy, gdy

NWD

(a, m) = 1.

Dowód ⇒.

0 0 Skoro istnieje taka liczba a , »e aa ≡ 1 (mod 0 0 taka liczba caªkowita k , »e aa − 1 = km, albo aa − km =

m) = 1. ⇐. Je±li NWD(a, m) = 1, to istniej¡ ax + my = 1, czyli m | ax − 1. Zatem a

m), to istnieje te» 1. Z poprzedniego

lematu wynika, »e NWD(a,

liczby caªkowite

x

oraz

jest odwracalna modulo

y takie, m.

»e

a0 , nale»y znale¹¢ takie liczby x oraz y , »eby zachodziªa równo±¢ ax + my = 1. Liczby te znajdujemy stosuj¡c algo0 0 rytm Euklidesa. Wówczas a = x. Dla przykªadu, znajd¹my 11 modulo 31. Aby obliczy¢ liczb¦ odwrotn¡ do

W tym celu wykonujemy nast¦puj¡ce obliczenia:

31 = 3 · 11 − 2 11 = 5 · 2 + 1

2 = 3 · 11 − 31 1 = 11 − 5 · 2. 14

1 = 11 − 5 · 2 = 11 − 5 · (3 · 11 − 31) = 5 · 31 − 14 · 11. Zatem 11 = −14 + 31 = 17. Zauwa»my, »e je±li liczba caªkowita a jest odwracalna modulo m, to ist0 nieje niesko«czenie wiele liczb a , które speªniaj¡ kongruencj¦ (3.2). Mówi¡c o

Tak wi¦c 0

elementach odwracalnych, chcieliby±my tak»e zdeniowa¢ element odwrotny 0 do danego. Nale»y wi¦c wyró»ni¢ jeden z elementów a . Poka»emy, »e w zbio0 rze wszystkich elementów a speªniaj¡cych (3.2) zachodzi pewna regularno±¢.

3.6 Twierdzenie.

Je±li aa0 ≡ 1 (mod m), oraz aa00 ≡ 1 (mod m), to liczby a0 i a00 ró»ni¡ si¦ o wielokrotno±¢ m. Dowód. Przypu±¢my, »e a0 − a00 = qm + r dla q ∈ Z oraz 0 ≤ r ≤ m − 1. 0 00 0 00 Mamy aa − aa = aqm + ar , albo aa − aa ≡ ar (mod m). Zatem zachodzi 0 ≡ ar (mod m), czyli m | ar. Skoro jednak NWD(a, m) = 1, wi¦c m | r, a to oznacza, »e r = 0. Z powy»szego twierdzenia wynika, »e je±li liczba

jest odwracalna mo-

a modulo m. Tak wi¦c, je±li a ∈ Z jest odwracalny modulo m, to elementem odwrotnym do a modulo m nazywamy liczb¦ b ∈ {0, 1, . . . , m − 1}, tak¡ »e ab ≡ 1 (mod m). −1 B¦dziemy przy tym pisa¢ b = a mod m. Zdeniujmy dodawanie +m oraz ·m modulo m w nast¦puj¡cy sposób:

dulo

m,

a

to mo»emy mówi¢ o elemencie odwrotnym do

a +m b = a + b mod m, a ·m b = a · b mod m. Z tak zdeniowanymi dziaªaniami dodawania i mno»enia, zbiór

Zm

speªnia

wszystkie aksjomaty ciaªa z wyj¡tkiem szóstego. Aksjomat szósty (istnienie elementu odwrotnego do ka»dego niezerowego elementu ciaªa) jest speªniony tylko dla liczb pierwszych dziaªaniami

+m i ·m

m,

co wynika z twierdzenia 3.5. Zatem zbiór

Zp

z

Ma ona rozwi¡zanie, je±li liczba

a

jest ciaªem.

Wró¢my teraz do kongruencji (3.1). jest odwracalna modulo

m.

Aby znale¹¢ to rozwi¡zanie, nale»y pomno»y¢

obie strony kongruencji (3.1) przez liczb¦ odwrotn¡ do

3.7 Przykªad.

Euklidesa, otrzymujemy modulo 13.

3x ≡ 5 (mod 13). 3 · 9 − 13 · 2 = 1. Zatem 9

Rozwi¡»emy

a.

Wykorzystuj¡c algorytm jest liczb¡ odwrotn¡ do 3

Mno»¡c obie strony naszej kongruencji przez 9 otrzymujemy

x ≡ 9 · 5 ≡ 6 (mod 13).

Zatem 6 (i ka»da liczba, która si¦ ró»ni od 6

o wielokrotno±¢ 13) jest rozwi¡zaniem naszej kongruencji.

15

Je±li nie b¦dzie powiedziane inaczej, to od tej chwili b¦dziemy rozwa»a¢ tylko te rozwi¡zania kongruencji (3.1), które nale»¡ do

Zm = {0, 1, . . . , m − 1}. jest ono jed-

Je±li w tym zbiorze jest tylko jedno rozwi¡zanie, to mówimy, »e

noznaczne lub jednoznaczne modulo m. Je»eli a nie jest odwracalna modulo m,

to rozwi¡zanie te» mo»e istnie¢.

Przedstawimy teraz twierdzenie, które mówi o istnieniu i jednoznaczno±ci rozwi¡za«.

3.8 Twierdzenie.

Kongruencja (3.1) ma dokªadnie d = NWD(a, m) rozwi¡za« je±li d | b oraz nie ma rozwi¡zania je±li d - b. Je»eli d | b oraz x0 jest rozwi¡zaniem, to d ró»nych rozwi¡za« wyra»a si¦ wzorem x0 + md i mod m dla i ∈ {0, 1, . . . , d − 1}. Dowód.

d = 1, to jak ju» zauwa»yli±my, kongruencja (3.1) ma rozwi¡zax1 oraz x2 s¡ dwoma rozwi¡zaniami (3.1). Zatem ax1 ≡ ax2 (mod m). Z twierdzenia 3.2 wynika kongruencja x1 ≡ x2 (mod m), czyli x1 = x2 . Zaªó»my teraz, »e d 6= 1. Je±li d - b, to poniewa» d | a, wi¦c d - ax − b dla »adnego x ∈ Z, a co za tym idzie, m - ax − b dla »adnej liczby x. Zatem Je±li

nie. Aby pokaza¢ jego jednoznaczno±¢, przypu±¢my, »e

kongruencja (3.1) nie ma rozwi¡zania. Przypu±¢my wi¦c, »e

d 6= 1

oraz

b a x≡ d d

d | b.

Rozwa»my kongruencj¦

(mod

m ) d

(3.3)

a m Skoro NWD , = 1, wi¦c kongruencja (3.3) ma rozwi¡zanie x0 . Zapiszmy d d a b m x − d = d k dla pewnej liczby caªkowitej k . Mno»¡c obie strony tego d 0 równania przez d otrzymujemy, »e x0 jest rozwi¡zaniem kongruencji (3.1).




x0

Ale

jest rozwi¡zaniem (3.3), a ka»de dwie liczby speªniaj¡ce t¦ konm . Zatem w Zm jest tych rozwi¡za« gruencj¦ ró»ni¡ si¦ o wielokrotno±¢ d m dokªadnie d i ka»de z nich mo»emy zapisa¢ w postaci x0 + i mod m dla d i ∈ {0, 1, . . . , d − 1}. S¡ to wi¦c wszystkie rozwi¡zania kongruencji (3.1). Tak wi¦c kongruencja z przykªadu 3.7 ma dokªadnie jedno rozwi¡zanie. Podamy jeszcze jeden przykªad ilustruj¡cy powy»sze twierdzenie.

3.9 Przykªad. NWD

(4, 30) = 2

Rozwi¡»emy kongruencj¦

oraz

2 | 10,

4x ≡ 10 (mod 30).

Poniewa»

wi¦c nasza kongruencja ma dwa rozwi¡zania. Re-

dukujemy caª¡ kongruencj¦ przez 2 otrzymuj¡c

2x ≡ 5 (mod 15), a nast¦pnie

znajdujemy liczb¦ odwrotn¡ do 2 modulo 15. jest ni¡ 8. Otrzymujemy wi¦c

x0 = 10.

Jest to pierwsze rozwi¡zanie. Drugim jest

16

x1 = 10 + 15 = 25.

Wykªad 4 Pewne zastosowania elementów odwrotnych Zajmiemy si¦ teraz ukªadami dwóch kongruencji z dwiema niewiadomymi.

( a1 x + b 1 y ≡ c 1 a2 x + b 2 y ≡ c 2 gdzie

(mod (mod

m) m),

(4.1)

m > 1. Dla skupienia uwagi rozwa»my nast¦puj¡ce dwa przykªady: ( ( 5x + 2y ≡ 7 (mod 14) 3x + 2y ≡ 4 (mod 12) 8x + 3y ≡ 4 (mod 14), 8x + 4y ≡ 6 (mod 12).

Pierwszy z powy»szych ukªadów rozwi¡zujemy zgodnie z intuicj¡ i bez przeszkód, tj.

z pierwszej kongruencji, po pomno»eniu jej przez 3 (liczba od-

x ≡ 7+8y (mod 14). Po podstawieniu do drugiej kongruencji i uproszczeniu, dostajemy 11y ≡ 4 (mod 14). St¡d ju» szybko otrzymujemy y ≡ 8 (mod 14), a zaraz potem x ≡ 1 (mod 14). Zatem jedynym rozwi¡zaniem (modulo 14) pierwszej kongruencji jest para (1, 8).

wrotna do 5 modulo 14), wyznaczamy

Drugiego (prawego) ukªadu nie jeste±my w stanie rozwi¡za¢ stosuj¡c ten sam algorytm. Po przeksztaªceniu pierwszej kongruencji, dostajemy

3x ≡ 4 − 2y Poniewa» NWD(3,

(mod 12).

12) = 3, wi¦c zgodnie z twierdzeniem 3.8, aby nasza (pierw3 | 4 − 2y . Zatem y ∈ {2, 5, 8, 11}. Podstawiaj¡c ka»d¡ z tych liczb za y , zauwa»amy, »e druga kongruencja przyjmuje zawsze posta¢ 8x ≡ 10 (mod 12). Ale NWD(8, 12) = 4 oraz 4 - 10, wi¦c sza) kongruencja miaªa rozwi¡zanie,

17

twierdzenie 3.8 pozbawia nas zªudze«: kongruencja ta, a wi¦c i caªy ukªad kongruencji nie ma rozwi¡zania. Do ukªadu (4.1) zastosujemy algorytm Cramera. Po pomno»eniu pierwszej kongruencji przez

−a2 ,

a drugiej przez

a1

oraz dodaniu ich stronami,

otrzymujemy

(a1 b2 − b1 a2 )y ≡ a1 c2 − c2 a1

(mod m).

(4.2)

W = a1 b2 − b1 a2 , Wy = a1 c2 − c2 a1 oraz Wx = c1 b2 − b1 c2 . Po pomno»eniu pierwszej kongruencji przez b2 , drugiej przez −b1 oraz dodaniu

Oznaczmy

stronami, wykorzystuj¡c wprowadzone oznaczenia mamy

(

W x ≡ Wx (mod m) W y ≡ Wy (mod m).

(4.3)

Zatem rozwi¡zania ukªadu (4.1) zawieraj¡ si¦ w zbiorze rozwi¡za« ukªadu (4.3). Ka»d¡ z kongruencji tego ukªadu rozwi¡zujemy (je±li to mo»liwe) stosuj¡c twierdzenie 3.8. Ostatecznie otrzymujemy nast¦puj¡cy rezultat.

4.1 Twierdzenie.

Oznaczmy d = NWD(W, m). Ukªad kongruencji (4.1) nie ma rozwi¡za« je±li d - Wx lub d - Wy . W przeciwnym wypadku, ukªad ten ma modulo m co najwy»ej d2 rozwi¡za«, których pierwsze oraz drugie wspóªrz¦dne  przystaj¡ do siebie modulo md . Podobny rezultat otrzymamy uogólniaj¡c powy»sze twierdzenie na przy-

padek wi¦kszej liczby kongruencji. mamy

W = −1

Zauwa»my, »e w naszych przykªadzie

(modulo 14) dla lewego ukªadu, co oznacza, »e ma on do-

W = −4, Wx = 4 oraz Wy = −14 12) = 4 i 4 - −14, wi¦c ukªad ten nie

kªadnie jedno rozwi¡zanie. Natomiast

dla

prawego ukªadu. Poniewa» NWD(W,

ma

rozwi¡zania. Jako przykªad zastosowa« powy»szych idei, opiszemy szyfr aniczny. Podobnie jak w Rozdziale 2, ka»dej literze alfabetu przypiszemy liczb¦, która jest pozycj¡ danej litery w alfabecie. 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 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Przeksztaªcenie szyfruj¡ce tzw.

kodu anicznego

E(p) = ap + b mod N. 18

ma posta¢

(a, b). ›eby rozszyfrowa¢ wiadomo±¢ u»ywamy 0 0 0 innego klucza. Dokªadnie, D(c) = a c + b mod N , gdzie a jest liczb¡ od0 0 wrotn¡ do a modulo N , a b = −a b w ZN . Aby E byªo odwzorowaniem 0 szyfruj¡cym, NWD(a, N ), wi¦c i NWD(a , N ) jest równe 1. Kiedy a = 1, kod aniczny staje si¦ kodem cyklicznym. Gdy b = 0, kod aniczny nazywamy

Naszym kluczem jest tu para

szyfrem liniowym.

ma 312 (=

W przypadku alfabetu 26-literowego, przestrze« kluczy

12 · 26)

elementów.

Nie jest to du»a liczba z kryptoanalitycz-

nego punktu widzenia, ale rozwa»enie takiej liczby przypadków mo»e stworzy¢ pewne trudno±ci. Zademostrujemy metod¦ ªamania kodów anicznych, która ogranicza istotnie liczb¦ rozwa»anych przypadków.

4.2 Przykªad.

vqtmx ozdtg hgjqm aqhcx bgkgt ag. W g, a nast¦pn¡ jest q. Podejrzewamy, »e g a (pozycja 0), natomiast q (pozycja 16), to e

Zªamiemy szyfr

szyfrze tym najcz¦stsz¡ liter¡ jest (pozycja 6) to zaszyfrowane (pozycja 4). Mamy wi¦c

6a0 +b0 ≡0( mod 26) 16a0 +b0 ≡4( mod 26)

(4.4)

10a0 ≡ 4 (mod 26), a 8 i mamy klucz deszynam tekst jawny Ten szyfr

Odejmuj¡c obie kongruencje stronami otrzymujemy 0 0 st¡d natychmiast a = 3. Chwil¦ potem mamy b = fruj¡cy. Zastosowanie tego klucza, tj.

(3, 8)

nadaje si¦ do zªamania.

daje

Wykorzystuj¡c twierdzenie 4.1 do ukªadu (4.4) otrzymujemy

W = 22, W = 24, a0

b0

(W, 26) = 2,

NWD

W = 16,

wi¦c ukªad kongruencji (4.4) ma 4 po-

(3, 8), (3, 21), (16, 8) oraz (16, 21). 0 NWD(a , N ) ma by¢ równy 1. Odpada

tencjalne rozwi¡zania modulo 26. S¡ to pary Dwie ostanie pary odpadaj¡, poniewa» te» para

(3, 21), bo po sprawdzeniu zauwa»amy, »e nie jest ona rozwi¡zaniem

ukªadu (4.4).

19

Wykªad 5 Maªe Twierdzenie Fermata W czerwcu 1640 roku Fermat napisaª list do Mersenne'a, w którym stwierp dziª, »e je±li p jest liczb¡ pierwsz¡, to 2 − 2 jest wielokrotno±ci¡ 2p, a je±li q jest pierwszym dzielnikiem 2p − 1, to q − 1 jest wielokrotno±ci¡ p. Jak zwykle, Fermat nie napisaª dowodu tego stwierdzenia. Zrobiª to dopiero Euler w 1730 u»ywaj¡c rozwini¦cia dwumianowego, a w 1758 opublikowaª on inny dowód, który pozwoliª uogólni¢ twierdzenie Fermata.

To uogólnione

twierdzenie nosi nazw¦ twierdzenia Eulera. W rozdziale tym przytoczymy i udowodnimy obydwa te twierdzenia.

5.1 Twierdzenie

Twierdzenie Fermata  MTF ). Je»eli p jest liczb¡ pierwsz¡, to a ≡ a (mod p) dla dowolnej liczby caªkowitej a oraz ap−1 ≡ 1 (mod p) dla wszystkich liczb caªkowitych a, takich »e p - a. (Maªe

p

Oryginalny dowód Eulera z 1730 roku.

Przypu±¢my, »e

dukcji matematycznej. Twierdzenie jest prawdziwe dla »e twierdzenie jest prawdziwe dla tak»e dla zachodzi

a = n + 1. relacja p |

a = n.

a ≥ 0. a = 0.

U»yjemy inPrzypu±¢my,

Poka»emy, »e jest ono prawdziwe

W tym celu zauwa»my, »e dla dowolnego
p . Istotnie, m

  p p! , = m!(p − m)! m

1 ≤ m ≤ p−1

(5.1)

ale w mianowniku uªamka po prawej stronie równo±ci (5.1) znajduj¡ si¦ liczby
p mniejsze od p, a jest liczb¡ naturaln¡, wi¦c m!(p−m)! musi dzieli¢ (p−1)! m
p Zatem p | . m 20

Dalej mamy

      p p−1 p p−2 p (n + 1) ≡ n + n + n + ··· + n+1 1 2 p−1 ≡ n + 1 + p · (co±) ≡n+1 p

p

(mod p) (mod p) (mod p).

Na podstawie indukcji matematycznej wnioskujemy, »e twierdzenie jest prawdziwe dla wszystkich liczb nieujemnych

p > 2,

a.

Je±li

a

jest liczb¡ ujemn¡ oraz

to

ap ≡ −(−a)p ≡ −(−a) = a (mod p), czyli twierdzenie jest prawdziwe i w tym przypadku. Przypadek

p=2

jest

trywialny. Zaªó»my teraz, »e p - a. Zatem NWD(a, p) = 1 i a posiada element od−1 p wrotny a modulo p. Po pomno»eniu obu stron kongruencji a ≡ a (mod p) −1 p−1 przez a , otrzymamy a ≡ 1 (mod p). Podamy teraz przykªady zastosowa« MTF.

5.2 Przykªad. 50 = 4 · 12 + a = 3. Zatem

Poka»emy, »e

250 + 350

jest podzielne przez 13. Poniewa» 2, wi¦c z twierdzenia 5.1 mamy a50 ≡ a2 (mod 13) dla a = 2 i

250 + 350 ≡ 22 + 32 = 13 ≡ 0 wi¦c

(mod 13),

13 | 250 + 350 .

5.3 Przykªad.

2 Poka»emy, »e 7 nie dzieli n + 1 dla »adnej liczby n ∈ N. 2 2 Istotnie, gdyby n + 1 ≡ 0 (mod 7), to wówczas n ≡ −1 (mod 7), czyli n6 ≡ −1 (mod 7), co jest sprzeczne z twierdzeniem 5.1. Poniewa»

2340 ≡ 1 (mod 341)

wrotne do 5.1 nie nie s¡ pierwszymi

341 = 11 · 31, wi¦c twierdzenie odjest prawdziwe. Liczby n, które speªniaj¡ tez¦ MTF, ale nazywamy pseudopierwszymi. Wi¦cej o liczbach pseudooraz

pierwszych powiemy w dalszej cz¦±ci wykªadu.

5.4 Twierdzenie.

Przypu±¢my, »e ar ≡ 1 (mod p) dla pewnej liczby pierwszej p oraz liczby caªkowitej a, która nie dzieli si¦ przez p. Je±li d = NWD(r, p − 1), to ad ≡ 1 21

(mod p).

Dowód. Z lematu 3.4 mamy rx + (p − 1)y = d. Zatem

istnienie takich liczb caªkowitych

ad ≡ arx+(p−1)y r x

x

oraz

y,

»e

(mod p)


p−1 y

≡ (a ) a ≡1·1=1

(mod p) (mod p).

Kilka zastosowa« udowodnionego przed chwil¡ twierdzenia zobrazujemy w nast¦puj¡cych przykªadach.

5.5 Przykªad.

Przypu±¢my, »e p oraz q s¡ nieparzystymi liczbami pierwp p szymi oraz q | 2 − 1. Wówczas 2 ≡ 1 (mod q) i je»eli d = NWD(p, q − 1), d to 2 ≡ 1 (mod q). Ale, poniewa» p jest liczb¡ pierwsz¡, wi¦c d = p, gdy»

d = 1 implikuje nieprawdziw¡ kongruencj¦ 2 ≡ 1 (mod q). Zatem p | q − 1, a poniewa» liczba p jest nieparzysta, a q − 1 jest parzysta, wi¦c 2p | q − 1. Wynika st¡d, »e aby sprawdzi¢ czy liczba 2p − 1 jest pierwsza wystarczy rozwa»y¢, jako potencjalne dzielniki, tylko liczby postaci 2kp + 1, √ p 1 2 − 1. dla 1 ≤ k ≤ 2

przypadek

5.6 Przykªad. postaci

4k + 1.

Poka»emy, »e istnieje niesko«czenie wiele liczb pierwszych Aby tego dokona¢, przypu±¢my, »e jest ich tylko sko«czona

p1 , p2 , . . . , pr s¡ wszystkimi liczbami pierwszymi tej postaci. 2 Rozwa»my liczb¦ N = (2p1 p2 . . . pr ) +1 i przypu±¢my, »e p | N . Wynika st¡d 2 4 kongruencja (2p1 p2 . . . pr ) ≡ −1 (mod p) oraz (2p1 p2 . . . pr ) ≡ 1 (mod p). Oznaczmy d = NWD(4, p − 1). Zatem liczba d jest dzielnikiem liczby 4, czyli d nale»y do zbioru {1, 2, 4}. Poniewa» (2p1 p2 . . . pr ) ≡ 1 (mod p), wi¦c d nie mo»e by¢ równa 1 ani 2. Zatem d = 4, czyli 4 | p − 1 i p jest postaci 4k + 1. Ale p | N , wi¦c p nie mo»e by¢ »adn¡ z liczb p1 , p2 , . . . , pr . St¡d sprzeczno±¢.

liczba, czyli »e

22

Wykªad 6 Twierdzenie Eulera Jak ju» zauwa»yli±my (tw. 3.5), liczba tylko wtedy, gdy NWD(a, liczbie naturalnej modulo

n

n,

n) = 1.

a

Funkcja

jest odwracalna modulo

ϕ,

n

ilo±¢ dodatnich i niewi¦kszych od

nazywamy

funkcj¡ Eulera.

n

wtedy i

która przyporz¡dkowuje ka»dej liczb odwracalnych

Zatem

ϕ(n) = # {0 < x ≤ n : NWD(x, n) = 1} .

6.1 Przykªad. ϕ(8) = 4,

poniewa» tylko liczby nieparzyste s¡ wzgl¦dnie

p jest liczb¡ pierwϕ(p) = p − 1, gdy» ka»da liczba dodatnia mniejsza od p jest wzgl¦dnie r pierwsza z p. Je»eli p jest pot¦g¡ liczby pierwszej, to jedynymi liczbami, r które nie s¡ wzgl¦dnie pierwsze z p , s¡ wielokrotno±ci p, czyli liczby p, 2p, r−1 3p, . . . , (p − 1)p. Tych liczb jest w sumie pr−1 − 1, zatem pierwsze z 8 oraz 8 nie ma dzielników nieparzystych. Je±li

sz¡, to

r

r

ϕ(p ) = p − 1 − (p

r−1

r

− 1) = p − p

Poka»emy, »e przy pewnym zaªo»eniu,

ϕ

r−1

=p

r



1 1− p

 .

(6.1)

jest funkcj¡ multyplikatywn¡.

Pozwoli nam to wyprowadzi¢ do±¢ por¦czny wzór na warto±ci

ϕ

uogólnia-

j¡cy (6.1).

6.2 Twierdzenie. Dowód.

Je±li

(m, n) = 1, to ϕ(mn) = ϕ(m)ϕ(n).

NWD

m, n jest równa 1, to teza m > 1 i n > 1. Wypiszmy

Zauwa»my najpierw, »e je±li jedna z liczb

jest prawdziwa.

Mo»emy zatem zaªo»y¢, »e

23

wszystkie liczby niewi¦ksze od

mn

1, 2, n + 1, n + 2, 2n + 1, 2n + 2, . . . . . . . . . . . . ., . . . . . . . . . . . . ., (m − 1)n + 1, (m − 1)n + 2,

w nast¦puj¡cy sposób:

..., r, ..., n + r, ..., 2n + r, ..., ............ , . . . , (m − 1)n + r,

..., n, . . . , 2n, . . . , 3n, ..., ..., . . . , mn.

(6.2)

m od . . . , m − 1 tylko porz¡dkiem. Istotnie, je±li istniej¡ liczby q1 , q2 , oraz r , takie »e q1 n + r ≡ q2 n + r (mod m), to poniewa» m i n s¡ wzgl¦dnie pierwsze, wi¦c z ostatniej kongruencji wynika q1 ≡ q2 (mod m) (tw. 3.1). Ale poniewa» q1 i q2 s¡ nieujemnymi liczbami mniejszymi od m, wi¦c q1 = q2 . Zauwa»my, »e liczby ka»dej z kolumn tablicy (6.2) ró»ni¡ si¦ modulo liczb 1, 2,

Znacznie ªatwiej jest zauwa»y¢, »e w ka»dym wierszu tablicy (6.2) mamy liczby przystaj¡ce modulo

n,

odpowiednio, do 1, 2,

Tak wi¦c w ka»dym wierszu jest w ka»dej kolumnie jest

ϕ(m)

ϕ(n)

. . . , n − 1,

0.

liczb wzgl¦dnie pierwszych z

liczb wzgl¦dnie pierwszych z

m.

n,

a

Co wi¦cej,

zauwa»my, »e je»eli w pewnej kolumnie (6.2) mamy liczb¦, która nie jest wzgl¦dnie pierwsza z

n,

to wszystkie liczby tej kolumny nie s¡ wzgl¦dnie

n. Z drugiej strony, je±li jaka± liczba jest wzgl¦dnie pierwsza z mn, to jest ona wzgl¦dnie pierwsza z m i wzgl¦dnie pierwsza z n. Wykre±lmy zatem z (6.2) wszystkie liczby, które nie s¡ wzgl¦dnie pierwsze z mn. Wówczas w ka»dym wierszu pozostanie nam ϕ(n) liczb, przy czym wykre±limy caªe kolumny. Pozostanie wi¦c ϕ(n) kolumn z ϕ(m) liczb w ka»dej z nich. Zatem ϕ(mn) = ϕ(n)ϕ(m). Q k αi Rozwa»my liczb¦ n = i=1 pi . Poniewa» wszystkie czynniki w tym pierwsze z

iloczynie s¡ parami wzgl¦dnie pierwsze, wi¦c po zastosowaniu twierdzenia 6.2, dostajemy

ϕ(n) =

k Y i=1 k Y

ϕ (pαi i )

 1 = 1− pi i=1  k  Y 1 =n 1− pi i=1 pαi i



Udowodnili±my wi¦c nast¦puj¡cy wniosek.

24

6.3 Wniosek.

Je±li n =

αi i=1 pi , to ϕ(n) = n

Qk

Qk  i=1 1 −

1 pi



.



U»ywaj¡c wniosku 6.3, dostajemy

ϕ(29 · 52 ) = (29 − 1)(25 − 5) = 560. Poniewa» ró»nica

p=2

oraz

pk − pk−1

k = 1,

jest liczb¡ parzyst¡, z wyj¡tkiem przypadku gdy

wi¦c jedyn¡ nieparzyst¡ warto±ci¡ funkcji

jest przyjmowana dla argumentów

1

oraz

2.

ϕ

jest

1,

która

Dla liczb wi¦kszych od 3, funk-

cja Eulera przyjmuje tylko warto±ci parzyste. Co wi¦cej, je±li w rozkªadzie k−1 liczby n wyst¦puje dokªadnie k pot¦g liczb pierwszych, to 2 | ϕ(n).

6.4 Przykªad.

Znajdziemy wszystkie liczby

n,

dla których

ϕ(n) = 6.

W

tym celu rozwa»ymy kilka przypadków.

• n = pα .

6 = pα−1 (p − 1). Rozwa»aj¡c n = 32 = 9, lub n = 7.

Zatem

zauwa»amy, »e

• n = pα q β .

Wówczas

kolejne liczby pierwsze,

6 = (pα − pα−1 )(q β − q β−1 ).

Zauwa»my, »e ró»nica

dwóch kolejnych pot¦g »adnej liczby pierwszej nie jest równa 3, wi¦c α α−1 β β−1 jedna z liczb p − p , q − q musi by¢ równa 1, czyli p = 2, a druga  6. Rozwa»aj¡c kolejne liczby pierwsze jako kandydatki na 2 otrzymujemy n = 2 · 3 = 18 lub n = 2 · 7 = 14.

•

Z uwagi umieszczonej tu» przed przykªadem, wynika, »e

q,

n nie mo»e by¢

iloczynem wi¦cej ni» dwóch pot¦g liczb pierwszych. U»ywaj¡c funkcji Eulera

ϕ, sformuªujemy i udowodnimy uogólnienie Ma-

ªego Twierdzenia Fermata. Zauwa»my przy tym, »e je±li NWD(a, n) 6= 1, to ak 6≡ 1 (mod n) dla »adnego k > 1. Istotnie, gdyby tak byªo, to n byªaby k k−1 dzielnikiem a −1, czyli istniaªaby liczba caªkowita x, taka »e xn+a·a = 1. Z lematu 3.4 wynika zatem, »e NWD(a,

n) = 1, sk¡d sprzeczno±¢. Tak wi¦c, aby otrzyma¢ kongruencj¦, w której pot¦ga a przystaje do 1, nale»y rozwa»a¢ tylko te liczby a, które s¡ wzgl¦dnie pierwsze z n. Je±li n jest liczb¡ pierwsz¡, to sprowadza si¦ to do liczb, które nie s¡ podzielne przez n, st¡d zaªo»enia drugiej cz¦±ci MTF. Zauwa»my, »e owa druga cz¦±¢ MTF jest zawarta w nast¦puj¡cym twierdzeniu.

6.5 Twierdzenie

(Eulera )

.

witej a oraz n > 2. Wówczas

Przypu±¢my, »e

aϕ(n) ≡ 1 25

(a, n) = 1 dla liczby caªko-

NWD

(mod n)

(6.3)

Dowód.

Wypiszmy wszystkie elementy odwracalne modulo

datnie i mniejsze od modulo

n,

n.

S¡ to

wi¦c tak»e elementy

r1 , r2 . . . , rϕ(n) . ar1 , ar2 . . . , arϕ(n)

Skoro

a

n,

które s¡ do-

jest odwracalna

s¡ odwracalne modulo

n,

oraz »adne dwa z nich nie s¡ równe. Zatem

r1 r2 . . . rϕ(n) ≡ ar1 ar2 . . . arϕ(n)

(mod n).

Korzystaj¡c z prawa przemienno±ci mno»enia dostajemy

aϕ(n) (r1 r2 . . . rϕ(n) ) ≡ (r1 r2 . . . rϕ(n) )

(mod n).

Ostatnia kongruencja implikuje (6.3).

31234 1234 ≡ 2 (mod 8).

Dla przykªadu, znajdziemy ostatni¡ cyfr¦ liczby nastkowym.

(mod 16)

Mamy tu

ϕ(16) = 8,

a

w ukªadzie szest1234 Zatem 3 ≡ 9

i ostatni¡ cyfr¡ jest 9.

a w Twierdzeniu Eulera jest cz¦sto ϕ(n). Na przykªad ϕ(105) = 48, ale dla a wzgl¦dnie pierwszych 12 mamy a ≡ 1 (mod 105). Istotnie, 105 = 3 · 5 · 7 oraz

Okazuje si¦, »e najni»sza pot¦ga liczby mniejsza ni» ze 105

a6 − 1 | a12 − 1

a4 | a12 − 1

wi¦c z Maªego Twierdzenia Fermata, pokazuje jak ulepszy¢ pot¦g¦

a2 − 1 | a12 − 1,

105 | a12 − 1.

Poni»sze twierdzenie

a.

6.6 Twierdzenie.

Przypu±¢my, »e m = pα1 1 pα2 2 . . . pαk k , gdzie wszystkie liczby pierwsze pi s¡ ró»ne i pαi i jest najwi¦ksz¡ poteg¡ liczby pi , która dzieli m. Niech n = NWW(ϕ (pα1 1 ) , ϕ (pα2 2 ) , . . . , ϕ (pαk k )). Wtedy mamy an ≡ 1 (mod m) dla ka»dego a wzgl¦dnie pierwszego z m. αi

Dowód. Z twierdzenia Eulera wynika aϕ(pi ) ≡ 1 (mod pαi i ) dla ka»dego i ∈ {1, 2, . . . , k}. Mno»¡c t¦ kongruencj¦ stronami przez siebie n/ϕ(pαi i ) razy αi n otrzymujemy a ≡ 1 (mod pi ) dla ka»dego i. St¡d bezpo±rednio wynika, αi n n »e dla dowolnego i mamy pi | a − 1. Zatem i m | a − 1, a to nam daje tez¦. Wracaj¡c do uwagi przed twierdzeniem 6.6, zauwa»my, »e oraz

12 = NWW(ϕ(3), ϕ(5), ϕ(7)) = NWW(2, 4, 6).

26

105 = 3 · 5 · 7

Wykªad 7 Twierdzenie Lagrange'a Podstawowe twierdzenie algebry mówi, »e wielomian stopnia

n

o wspóªczyn-

n pierwiastków. Podobne twiern, ale tylko modulo liczba pierwsza. 4 2 Dla przykªadu, rozwa»my kongruencje x ≡ 1 (mod 5) oraz x ≡ 1 (mod 8). nikach zespolonych mo»e mie¢ co najwy»ej

dzenie zachodzi dla kongruencji stopnia

Z twierdzenia 5.1, tj. z Maªego Twierdzenia Fermata, mamy, »e pierwsza z tych kongruencji ma dokªadnie 4 pierwiastki modulo 5 (s¡ to liczby wzgl¦dnie pierwsze z 5). Je±li chodzi o drug¡ kongruencj¦, to ma ona 4 pierwiastki: 1, 3, 5 i 7.

7.1 Twierdzenie

.

Niech p b¦dzie liczb¡ pierwsz¡ i niech f (x) b¦dzie wielomianem stopnia n ≥ 1 o wspóªczynnikach caªkowitych, którego wspóªczynnik przy najwy»szej pot¦dze x nie dzieli si¦ przez p. Wówczas kongruencja f (x) ≡ 0 (mod p) ma co najwy»ej n pierwiastków modulo p.

Dowód.

(Lagrange'a )

Zastosujemy tu indukcj¦ ze wzgl¦du na stopie« wielomianu. Zaªó»my

f (x) jest wielomianem stopnia 1. Oznacza to, »e f (x) = ax + b, p - a. Zatem a jest liczb¡ odwracaln¡ modulo p, czyli kongruencja ax + b ≡ 0 (mod p) ma dokªadnie jedno rozwi¡zanie.

zatem, »e

przy czym

Przypu±¢my, »e teza twierdzenia jest prawdziwa dla wszystkich wielomia-

f (x) b¦dzie wielomianem stopnia n. Je±li f (x) nie ma pierwiastków, to twierdzenie jest udowodnione jako »e 0 ≤ n. Przypu±¢my wi¦c, »e f (x) ma pierwiastek a. Z twierdzenia o podzielno±ci dla wielomianów, wynika, »e istniej¡ wielomiany q(x) oraz r(x), takie »e f (x) = (x − a)q(x) + r(x), przy czym deg r(x) < deg(x − a) = 1. Oznacza to, w szczególno±ci, »e r(x) jest liczb¡ r . Poniewa» f (a) ≡ 0 (mod p), wi¦c nów stopnia mniejszego od

n.

(a − a)q(a) + r ≡ 0

Niech

(mod p), 27

st¡d

r≡0

(mod p).

Otrzymujemy wi¦c, »e

f (x) ≡ (x − a)q(x) (mod p).

Ale wielomian

q(x)

n − 1 pierwiastków (z zaªo»enia indukcyjnego). Co wi¦cej, b jest pierwiastkiem wielomianu f (x), to (b − a)q(b) ≡ 0 (mod p), czyli p | (b − a)q(b), wi¦c b ≡ a (mod p) lub b jest te» pierwiastkiem q(x). Zatem f (x) ma, co najwy»ej, o jeden pierwiastek wi¦cej ni» q(x), czyli co najwy»ej n. ma co najwy»ej je»eli

Na podstawie indukcji matematycznej, twierdzenie jest prawdziwe. Powy»sze twierdzenie okre±la tylko maksymaln¡ liczb¦ pierwiastków wielomianu modulo to sprawa ªatwa.

p.

Nie mówi ono nic na temat ich znajdywania, a nie jest

Udowodnimy teraz wniosek, który wypªywa z twierdze«

Lagrange'a i Fermata.

7.2 Wniosek.

Przypu±¢my, »e p jest liczb¡ pierwsz¡ oraz d | p − 1. Wówczas kongruencja x − 1 ≡ 0 (mod p) ma dokªadnie d pierwiastków modulo p. d

Dowód.

xp−1 − 1 ≡ 0 (mod p) ma . . . , p − 1. Zapiszmy p − 1 = kd.

Z Maªego Twierdzenia Fermata wynika, »e

dokªadnie

p−1

rozwi¡za«, którymi s¡ 1, 2,

Mamy

xp−1 − 1 = (xd − 1)(xd(k−1) + xd(k−2) + · · · + xd + 1).

(7.1)

d Z twierdzenia Lagrange'a wynika, »e x − 1 ma co najwy»ej d pierwiastków, d(k−1) d(k−2) d a (x +x + · · · + x + 1) ma co najwy»ej d(k − 1) pierwiastków. Zatem prawa strona (7.1) ma co najwy»ej ma dokªadnie

p−1

p−1

pierwiastków, a strona lewa

pierwiastków. Dlatego ka»dy z wielomianów po prawej

stronie (7.1) ma maksymaln¡ mo»liw¡ liczb¦ pierwiastków. W szczególno±ci, xd − 1 ma dokªadnie d pierwiastków. Z Maªego Twierdzenia Fermata oraz z poprzedniego wniosku wynika nast¦puj¡ce twierdzenie, które wykorzystamy przy rozwa»aniu tak zwanych liczb silnie pseudopierwszych.

7.3 Twierdzenie. Przypu±¢my, »e p jest liczb¡ pierwsz¡ i d oznacza najwi¦k-

szy wspólny dzielnik liczb s i p − 1. Wówczas wielomian xs − 1 ma dokªadnie d pierwiastków modulo p. Dowód.

Zauwa»my najpierw, »e poniewa» d Z wniosku 7.2 wynika, »e kongruencja x

d

d | s, wi¦c tak»e xd − 1 | xs − 1. − 1 ≡ 0 (mod p) ma dokªadnie

pierwiastków. Z uwagi poczynionej na pocz¡tku dowodu, mamy, »e pierxs − 1 ≡ 0 (mod p). Oznacza to,

wiastki te s¡ te» pierwiastkami kongruencji

»e ostatnia kongruencja ma przynajmniej d pierwiastków i s¡ to pierwiastki d wielomianu x − 1 modulo p. Przypu±¢my, »e y jest pierwiastkiem modulo p

28

d ale nie jest on pierwiastkiem kongruencji x − 1 ≡ 0 p−1 (mod p). Jednak»e p - y , wi¦c y − 1 ≡ 0 (mod p). Zatem z twierdzed d nia 5.4 wynika, »e y − 1 ≡ 0 (mod p), czyli y jest pierwiastkiem x − 1 i wielomianu

xs − 1,

mamy sprzeczno±¢.

7.4 Przykªad.

Poniewa» 4 jest dzielnikiem liczby 12, wi¦c kongruencja

x4 ≡ 1 (mod 13)

ma oprócz oczywistych pierwiastków 1 i

−1

jeszcze dwa

pierwiastki.

7.5 Przykªad.

p ≡ 1 (mod 4). Wówczas istnieje pierwia2 stek z −1 modulo p, czyli kongruencja x ≡ −1 (mod p) ma rozwi¡zanie. Aby to zauwa»y¢, zapiszmy p = 4k + 1. Z twierdzenia 5.1, kongruencja x4k ≡ 1 (mod p) ma dokªadnie 4k (czyli p − 1) pierwiastków. Poniewa» x4k − 1 = (x2k − 1)(x2k + 1), wi¦c wielomiany x2k − 1 oraz x2k + 1 maj¡ 2k po 2k pierwiastków. Ale je±li a jest pierwiastkiem x + 1, to x = ak jest 2 rozwi¡zaniem x + 1, czyli pierwiastkiem z −1. Przypu±¢my, »e

29

Wykªad 8 Chi«skie Twierdzenie o Resztach Twierdzenie, które tu przedstawimy zostaªo odkryte i wykorzystywane w ±redniowiecznych Chinach. Przyczyn¡ tego odkrycia byªy trudno±ci z mno»eniem i dodawaniem du»ych liczb  ªatwiej jest nauczy¢ si¦ na pami¦¢ kilku kombinacji, ni» wykonywa¢ dziaªania arytmetyczne w pami¦ci.

A dokªad-

nie, kiedy dowódca chciaª zliczy¢ swoje wojsko, kazaª ustawi¢ si¦ »oªnierzom w dwu-szeregu, nast¦pnie w trzy-szeregu, potem w pi¦cio-szeregu itd. Liczba ,,niesparowanych »oªnierzy w ka»dym z tych ustawie« (czyli reszty z dzielenia ogólnej liczby »oªnierzy przez 2, 3, 5, . . . )

dawaªy liczb¦ wszystkich

»oªnierzy. ›eby skonkretyzowa¢ nasze my±lenie, rozwa»my nast¦puj¡cy przykªad.

8.1 Przykªad.

Po ustawieniu caªego wojska w 3-, 5- i 7-szeregu dostali±my,

odpowiednio 2, 1 oraz 6 niesparowanych »oªnierzy. Jaka jest liczebno±¢ oddziaªu, je»eli wiadomo, »e »oªnierzy jest mniej ni» 100? Formalizuj¡c zadanie, niech lenia

x

x b¦dzie liczb¡ »oªnierzy.

Zatem reszty z dzie-

przez 3, 5 oraz 7, to 2, 1 i 6. St¡d

x≡2 x≡1 x≡6

(mod 3) (mod 5) (mod 7)

(8.1) (8.2) (8.3)

Powy»szy ukªad trzech kongruencji rozwi¡»emy w nast¦puj¡cy sposób. Z kon-

x = 3k + 2. Podstawiaj¡c do (8.2), otrzymujemy 3k + 3k ≡ −1 (mod 5). Znajdujemy liczb¦ odwrotn¡ do 3 modulo 5 i rozwi¡zujemy ostatni¡ kongruencj¦ otrzymuj¡c k ≡ −2 (mod 5). Zatem k = 5r −2 oraz x = 3·(5r −2)+2 = 15r −4. Podstawiaj¡c t¦ posta¢ x

gruencji (8.1) mamy

2 ≡ 1 (mod 5),

czyli

30

15r − 4 ≡ 6 (mod 7), a nast¦pnie r ≡ 3 (mod 7). St¡d r = 7s + 3, czyli x = 15 · (7s + 3) − 4 = 105s + 41. Zatem wszystkich

do (8.3) dostajemy mamy

»oªnierzy jest 41 (nast¦pna mo»liwo±¢ to 146, ale jak zaznaczyli±my, »oªnierzy jest mniej ni» 100). Dowódca, oczywi±cie, nie musiaª przeprowadza¢ powy»szych rachunków, a jedynie zapami¦ta¢, »e ukªadowi 2-1-6 odpowiada liczba 41. Pami¦taª on te» zapewne, jakim ukªadom odpowiadaj¡ s¡siednie liczby: ukªad

liczba

ukªad

liczba

2-0-0

35

2-1-6

41

0-1-1

36

0-2-0

42

1-2-2

37

1-3-1

43

2-3-3

38

2-4-2

44

0-4-4

39

0-0-3

45

1-0-5

40

1-1-4

46

Ide¦ powy»szego przykªadu uogólnimy i podamy w dowodzie nast¦puj¡cego twierdzenia.

8.2 Twierdzenie

.

Przypu±¢my, »e m1 , m2 , . . . , mr s¡ parami wzgl¦dnie pierwsze. Wówczas ukªad kongruencji (Chi«skie twierdzenie o resztach)

x ≡ a1 (mod m1 ) x ≡ a2 (mod m2 ) .................. x ≡ ar (mod mr )

(8.4)

ma jednoznaczne rozwi¡zanie modulo m1 m2 . . . mr . Dowód. Wprowad¹my nast¦puj¡ce oznaczenia: M = m1 m2 . . . mr , Mi = −1 oraz xi = Mi mod mi dla 1 ≤ i ≤ r. Rozwa»my teraz liczb¦

M , mi

x = a1 M1 x1 + a2 M2 x2 + · · · + ar Mr xr . j 6= i zachodzi Mj ≡ 0 (mod mi ), wi¦c x ≡ ai Mi xi (mod mi ) dla ka»dego i. Ale Mi xi ≡ 1 (mod mi ), wi¦c x ≡ ai (mod mi ) dla 1 ≤ i ≤ r . 0 00 Pozostaje jeszcze udowodni¢ jednoznaczno±¢. Niech x oraz x b¦d¡ 0 00 dwoma rozwi¡zaniami ukªadu (8.4). Zatem x ≡ x (mod mi ) dla 1 ≤ i ≤ r . 0 00 St¡d mi | x − x , a poniewa» m1 , m2 , . . . mr s¡ parami wzgl¦dnie pierw0 00 sze, wi¦c M | x − x . Zatem dwa rozwi¡zania ukªadu (8.4) ró»ni¡ si¦ o wielokrotno±¢ M i ukªad ten ma jednoznaczne rozwi¡zanie modulo M . Poniewa» dla

31

W odró»nieniu od dowodów wielu innych podobnych twierdze«, dowód chi«skiego twierdzenia o resztach daje wzór na rozwi¡zanie ukªadu kongruencji typu (8.4).

8.3 Przykªad.

Rozwa»my ukªad kongruencji z przykªadu 8.1.

oznaczenia dowodu twierdzenia 8.2, mamy

M = 105

i

mi

ai

Mi

xi

1

3

2

35

2

2

5

1

21

1

3

7

6

15

1

Stosuj¡c

oraz

St¡d

x ≡ 2 · 35 · 2 + 1 · 21 · 1 + 6 · 15 · 1 ≡ 140 + 21 + 90 ≡ 251 ≡ 41

(mod (mod (mod (mod

105) 105) 105) 105).

Zaªo»enie o kopierwszo±ci moduªów jest do±¢ istotnym ograniczeniem. Rozwa»my dla przykªadu, ukªad kongruencji

x≡3 x≡7

(mod 8) (mod 12).

(8.5)

Nie mo»na go rozwi¡za¢ stosuj¡c twierdzenie 8.2, poniewa» 8 oraz 12 nie s¡ wzgl¦dnie pierwsze. Nie oznacza to jednak, »e ukªad ten nie ma rozwi¡zania. Rozwi¡»emy go w nast¦pnym przykªadzie.

8.4 Przykªad. 12 = 4 · 3

Aby rozwi¡za¢ ukªad kongruencji (8.5) zapiszmy najpierw

i rozbijmy drug¡ kongruencj¦ ukªadu na dwie kongruencje

x≡7≡3

(mod 4)

i

x≡7≡1

(mod 3).

Mamy zatem ukªad trzech kongruencji

x ≡ 3 (mod 8) x ≡ 3 (mod 4) x ≡ 1 (mod 3). 32

(8.6)

Ale rozwi¡zanie pierwszej kongruencji ukªadu (8.6) speªnia te» drug¡ kongruencj¦, wi¦c druga kongruencja jest niepotrzebna. Otrzymujemy wi¦c równowa»ny (8.5) ukªad kongruencji

x≡3 x≡1

(mod 8) (mod 3).

Ostatni ukªad rozwi¡zujemy stosuj¡c chi«skie twierdzenie o resztach (8.2) i otrzymujemy

x ≡ 19 (mod 24).

Podamy teraz uogólnienie chi«skiego twierdzenia o resztach, które pozwala rozwi¡zywa¢ ukªady kongruencji podobne do (8.5).

8.5 Twierdzenie. Przypu±¢my, »e m1 , m2 . . . , mr s¡ liczbami naturalnymi. Wówczas ukªad kongruencji (8.4) ma rozwi¡zanie wtedy i tylko wtedy, gdy NWD(mi , mj ) | ai − aj dla i 6= j . Otrzymane rozwi¡zanie jest jednoznaczne modulo NWW(m1 , m2 , . . . , mr ). Dowód.

Rozwa»my najpierw przypadek, gdy

mi = pei , gdzie 1 ≤ i ≤ r, ei jest

p jest liczb¡ pierwsz¡. Mo»emy, oczywi±cie, zaªo»y¢, »e e1 ≥ e2 ≥ · · · ≥ er . Przypu±¢my teraz, »e taki ukªad kongruencji ma e rozwi¡zanie x0 i niech i < j . Zatem NWD(mi , mj ) = mj = p j . Skoro zachodz¡ ei ej e kongruencje x0 ≡ ai (mod p ) oraz x0 ≡ aj (mod p ), wi¦c p j dzieli x0 −aj e e e e oraz, poniewa» p j | p i , p j dzieli tak»e x0 − aj . St¡d p j | ai − aj . e W drug¡ stron¦, je±li i < j , to rozwi¡zanie kongruencji x0 ≡ ai (mod p i ) ej jest te» rozwi¡zaniem kongruencji x0 ≡ aj (mod p ), wi¦c, w szczególno±ci, e rozwi¡zanie pierwszej kongruencji (jednoznaczne modulo p 1 ) jest te» rozwi¡liczb¡ nieujemn¡, a

zaniem pozostaªych kongruencji. Aby zako«czy¢ t¦ cz¦±¢ dowodu, zauwa»my e jeszcze, »e p 1 = NWW(m1 , m2 , . . . , mr ). Przejd¹my teraz do ogólnego przypadku. Zapiszmy

m1 = pe111 pe212 . . . pek1k m2 = pe121 pe222 . . . pek2k .................. mr = pe1r1 p2er2 . . . pekrk . Wówczas ukªad kongruencji (8.4) jest równowa»ny ukªadowi, skªadaj¡cemu

33

si¦ z podukªadów postaci

x ≡ a1 (mod pes1s ) x ≡ a2 (mod pes2s ) .................. x ≡ ar (mod pesrs ),

es = max {ets : 1 ≤ t ≤ r}. Ka»dy z pode ukªadów (8.7) ma jednoznaczne modulo pss rozwi¡zanie wtedy i tylko wtedy, eis ejs
gdy NWD ps , ps | ai − aj dla i 6= j , co wynika z pierwszej cz¦±ci dowodu. Co wi¦cej, rozwi¡zanie ys tego podukªadu jest rozwi¡zaniem kongruencji o e module pss , wi¦c ukªad (8.4) jest równowa»ny ukªadowi gdzie

1 ≤ s ≤ k.

(8.7)

Oznaczmy

x ≡ y1 (mod pe11 ) x ≡ y2 (mod pe22 ) .................. x ≡ yk (mod pekk ).

(8.8)

Ostatni ukªad ma rozwi¡zanie z uwagi na chi«skie twierdzenie o resztach oraz, je±li rozwi¡zanie istnieje, to jest ono jednoznaczne modulo

pe11 pe22 . . . pekk = NWW(m1 , m2 , . . . , mr ). Poniewa» rozwi¡zanie ukªadu (8.4) przy zaªo»eniach dowodzonego twierdzenia jest równowa»ne rozwi¡zaniu ukªadu (8.8), wi¦c twierdzenie jest udowodnione.

Powy»szy dowód podaje te» sposób na rozwi¡zanie ukªadu kongruencji. Sposób ten zostaª ju» zademonstrowany w przykªadzie (8.4). Dla utrwalenia rozwi¡»my jeszcze jeden ukªad kongruencji.

8.6 Przykªad.

Ukªad kongruencji

x ≡ 5 (mod 8) x ≡ 7 (mod 14) x ≡ 21 (mod 35) 34

ma rozwi¡zanie, poniewa» zachodzi NWD(8,

(8, 14) | 5 − 7.

NWD

35) = 1,

(14, 35) | 7 − 21

NWD

oraz

Aby rozwi¡za¢ nasz ukªad zapisujemy

8 = 23 · 50 · 70 14 = 21 · 50 · 71 35 = 20 · 51 · 71 i zast¦pujemy ukªadem równowa»nym (przy czym pomijamy kongruencje o module 1)

x ≡ 5 (mod 8) x ≡ 7 (mod 2)

x ≡ 21

(mod 5)

x≡7 x ≡ 21

(mod 7) (mod 7)

Rozwi¡zaniami trzech podukªadów s¡ odpowiednio 5, 1 oraz 0. Zatem nasz ukªad kongruencji sprowadza si¦ do ukªadu

x ≡ 5 (mod 8) x ≡ 1 (mod 5) x ≡ 0 (mod 7), który rozwi¡zujemy stosuj¡c chi«skie twierdzenie o resztach i otrzymujemy rozwi¡zanie

x = 21

jednoznaczne modulo 280.

35

Wykªad 9 RSA i gra w orªa i reszk¦ przez telefon W rozdziale tym poka»emy kilka zastosowa« rozkªadu liczb na czynniki. System kryptograczny RSA (od nazwisk twórców: Rivest  Shamir  Adleman), który tu przedstawimy, oparty jest na problemie znalezienia rozkªadu liczby zªo»onej na czynniki pierwsze. Niejako efektem ubocznym jest tu zwi¡zana z rozwi¡zywaniem kongruencji kwadratowych gra w orªa i reszk¦ przez telefon. Na pocz¡tek, zauwa»my »e, pomno»enie dwóch dwu-cyfrowych liczb pierwszych, powiedzmy 23 i 47 nie powinno sprawi¢ nam wi¦kszego problemu. Natomiast pytanie o rozkªad liczby 2047 (wiemy, »e jest ona iloczynem dwóch dwu-cyfrowych liczb pierwszych) jest raczej trudne.

n = pq , gdzie p oraz q s¡ liczbami pierwszymi, to znajomo±¢ warto±ci funkcji Eulera ϕ(n) = n + 1 − p − q jest równowa»na znajomo±ci liczb p oraz q . Istotnie, je±li znamy n, p oraz q , bez problemu mo»emy obliczy¢ ϕ(n) = n + 1 − p − q . Je»eli natomiast znamy n oraz ϕ(n), to znamy te» n = pq oraz n + 1 − ϕ(n) = p + q i »eby obliczy¢ p oraz q , rozwi¡zujemy w Je±li

miar¦ prosty ukªad równa« stopnia drugiego. W przypadku systemu RSA, kluczem szyfruj¡cym (jawnym) jest

(n, e),

n jest iloczynem dwóch liczb pierwszych, a e jest liczb¡ wzgl¦dnie pierwsz¡ z ϕ(n). Kluczem deszyfruj¡cym (tajnym) jest natomiast (n, d), gdzie d jest liczb¡ odwrotn¡ do e modulo ϕ(n). Znajomo±¢ rozkªadu liczby n oraz liczba ϕ(n) nie s¡ potrzebne do szyfrowania ani do deszyfrowania, wi¦c lepiej gdzie

o tym zapomnie¢. Najpopularniejsz¡ metod¡ ªamania RSA jest wªa±nie znajdywanie rozkªadu liczby

n.

Je±li

n jest liczb¡ 300 bitow¡, lub krótsz¡ (tj.

ma

co najwy»ej 300 bitów w rozwini¦ciu dwójkowym - okoªo 100 cyfr dziesi¦t-

36

nych), to mo»na j¡ rozªo»y¢ w kilka godzin u»ywaj¡c domowego komputera z powszechnie dost¦pnym (darmowym) oprogramowaniem. O kluczach 512 bitowych wiadomo od roku 1999, »e s¡ one ªamalne przy u»yciu klastra zªo»onego z kilkuset komputerów pracuj¡cych nieprzerwanie kilka tygodni. Teoretyczny komputer TWIRL opisany przez A. Shamira i E. Tromera w 2003 roku zakwestionowaª bezpiecze«stwo kluczy 1024 bitowych. Obecnie rekomendowan¡ dªugo±ci¡ klucza jest przynajmniej 2048 bitów. Istotnym zagro»eniem bezpiecze«stwa szyfrów RSA s¡ obecnie komputery kwantowe. Wracaj¡c szczegóªów zwi¡zanych z RSA, przeksztaªceniem szyfruj¡cym f : Zn → Zn okre±lona wzorem f (P ) = P e mod n. Przeksztaª−1 odwrotna do f i okre±lona wzorem ceniem deszyfruj¡cym jest funkcja f −1 d f (C) = C mod n. Teksty jawne i zaszyfrowane s¡ zapisane za pomoc¡

jest funkcja

tego samego alfabetu licz¡cego N symboli. Wybieramy liczby k i l tak, aby N k < n < N l . Jako jednostki tekstu jawnego bierzemy bloki po k liter, które traktujemy jako liczby

k cyfrowe

w systemie o podstawie

nostkami zaszyfrowanymi b¦d¡ bloki po

l

N.

Podobnie, jed-

Zatem ka»dy blok tekstu l zaszyfrowanego ma przypisan¡ warto±¢ liczbow¡ mi¦dzy 0 i N − 1.

9.1 Przykªad.

Przyjmiemy

liter.

N = 26, k = 3 i l = 4.

Zatem jednostki tekstu

jawnego s¡ trigramami, a jednostki tekstu zaszyfrowanego  tetragramami. Chcemy przesªa¢ wiadomo±¢ TAK do u»ytkownika j¡cy

A, który ma klucz szyfru-

(46927, 39423).

W tym celu szukamy najpierw odpowiednika liczbowego 2 sªowa TAK. Jest to 19 · 26 + 0 · 26 + 10 = 12854. Nast¦pnie obliczamy 1285439423 mod 46927 otrzymuj¡c w wyniku

14251 = 0 · 263 + 21 · 262 + 2 · 26 + 3, a to daje nam kryptotekst tekst uzyskuj¡c kryptogram

avbc. Tym samym kluczem zaszyfrowano inny bc. Czy jeste± w stanie, odtworzy¢ tekst jawny?

Adresat ma swój klucz rozszyfrowuj¡cy (46927, 26767), który pozwala mu 26767 obliczy¢ 14251 mod 46927 = 12854, a to mu daje sªowo TAK. U»ytkownik systemu RSA z powy»szego przykªadu wygenerowaª swoje klucze u»ywaj¡c liczb pierwszych 281 i 167. Oczywi±cie, u»yli±my tutaj bardziej ,,wyobra»alne liczby ni» to si¦ zwykle stosuje.

›eby podnie±¢ du»¡

liczb¦ do (cz¦sto jeszcze wi¦kszej) pot¦gi stosujemy algorytm iterowanego podnoszenia do kwadratu. Dla przykªadu obliczymy

348171

mod 1019. 37

W tym celu zapisujemy 7 +25 +23 +2+1

348171 = 3482  = 



2 !2  2 2 2
2 3482 · 348 · 348  · 348 · 348.

Nasze pot¦gowanie sprowadza si¦ zatem do podnoszenia do kwadratu lub mno»enia przez 348, przy czym za ka»dym razem wynik dziaªania jest redukowany modulo 1019. Po wykonaniu oblicze« otrzymujemy 127. Funkcja szyfruj¡ca w systemie RSA jest typowym przykªadem

jednokierunkowej, tj.

funkcji

takiej której warto±ci mo»na bez problemu obliczy¢, ale

znaj¡c warto±¢, nie mo»na obliczy¢ argumentu, dla którego ta warto±¢ jest przyjmowana. Dodatkowo funkcja ta jest ró»nowarto±ciowa (1-1). Podobn¡ funkcj¦, tyle »e 2-1 mo»na wykorzysta¢ przy grze w orªa i reszk¦ przez telefon. Zaªó»my, »e Alicja i Stefan s¡ krótko po rozwodzie i zdecydowali si¦ rzuci¢ monet¡ by zdecydowa¢, do kogo ma nale»e¢ samochód. Jedno nie chce widzie¢ drugiego, wi¦c spotkanie w celu dokonania rzutu nie wchodzi w rachub¦. Aby im pomóc, wykorzystamy stosunkowo maªe liczby, »eby caªy czas kontrolowa¢ przebieg gry. Niech wi¦c

n = 341 = 11 · 31.

Liczby 11 oraz 31

s¡ znane Alicji, a Stefan zna tylko ich iloczyn, tj. 341.

2 1. Stefan wybiera losowo liczb¦ 0 < x ≤ 340 i oblicza warto±¢ x . Zaªó»my, 2 »e x = 134, wi¦c x = 224. Alicja otrzymuje tylko liczb¦ 224.

y = 224 oraz wiedz¡c, »e 341 = 11 · 31, oblicza 2 cztery pierwiastki równania x = 224 modulo 341. Robi to w nast¦pu2 j¡cy sposób. Poniewa» x ≡ 224 (mod 341), wi¦c

2. Alicja po otrzymaniu

x2 ≡ 224 ≡ 4 x2 ≡ 224 ≡ 7

(mod 11) (mod 31)

st¡d mamy jedn¡ z czterech mo»liwo±ci

x ≡ ± 2 (mod 11) x ≡ ± 10 (mod 31) Stosuj¡c oznaczenia z dowodu chi«skiego twierdzenia o resztach roz-

a1 = 2, m1 = 11, a2 = 10, M1 = 31 oraz M2 = 11. Stosuj¡c

wi¡zujemy powy»szy ukªad nast¦puj¡co:

m2 = 31, M = 341.

Obliczamy teraz

38

algorytm Euklidesa lub w inny sposób obliczamy

N1 = 6

i

N2 = 17.

Teraz ju» bez trudu otrzymujemy

x = 2 · 31 · 6 + 10 · 11 · 17 = 2242, co modulo 341 daje 196. Alicja mo»e t¦ liczb¦ potraktowa¢ jako swoj¡ szcz¦±liw¡ i wysªa¢ j¡ Stefanowi, lub te» obliczy¢ trzy pozostaªe liczby rozwi¡zuj¡c nast¦puj¡ce ukªady kongruencji

x ≡ −2 (mod 11); x ≡ 2 (mod 11); x ≡ −2 x ≡ 10 (mod 31); x ≡ −10 (mod 31); x ≡ −10 Wówczas do dyspozycji b¦dzie miaªa liczby i

−134,

196

oraz

134

(mod 11); (mod 31). (tak»e

−196

ale to si¦ nie liczy) i b¦dzie w prawdziwej rozterce decyduj¡c,

czy ma wysªa¢ 3. Je±li wysªaªa

x2 = 196,

x1 = 134

czy te»

x1 = 134.

Stefan ma pecha, poniewa» nie zna on liczby

196, której Alicja natychmiast za»¡da. 4. Je»eli jednak Alicja wysªaªa

x2 = 196,

wygrywa Stefan i na dowód

wygranej przesyªa Alicji liczb¦ 134. Zauwa»my, »e mo»emy tu zastosowa¢ ka»d¡ liczb¦ dwóch liczb pierwszych

p i q,

n, która jest iloczynem

przy czym je±li gramy faktycznie o samochód

to liczby te musz¡ by¢ na tyle du»e i tak dobrane, »eby nie mo»na byªo zbyt szybko znale¹¢ rozkªadu liczby

n.

Liczby

p = 11

oraz

q = 31

z powy»-

szego przykªadu mog¡ co najwy»ej sªu»y¢ do gry o rozbite lusterko boczne. Zauwa»my te», »e w punkcie 4, Stefan mo»e udowodni¢ swoj¡ wygran¡ znajduj¡c bez problemu rozkªad liczby

n,

poniewa» NWD(x1

od 1, czyli stanowi nietrywialny dzielnik liczby

39

n.

− x2 , n)

jest wi¦kszy

Wykªad 10 Kongruencje wy»szych stopni Jak ju» zauwa»yli±my, teza twierdzenia Lagrange'a (7.1) nie zachodzi w przypadku, gdy moduªem jest liczba zªo»ona. ›eby rozwa»a¢ moduªy zªo»one, potrzebne jest jeszcze chi«skie twierdzenie o resztach (8.2). Zajmiemy si¦ kongruencjami typu

f (x) ≡ 0 (mod m),

gdzie

f (x)

jest wielomianem o wspóª-

czynnikach caªkowitych. Stopie« tego wielomianu jest stopniem kongruencji. Rozwa»my nast¦puj¡cy przykªad.

10.1 Przykªad.

Chcemy znale¹¢ wszystkie liczby n, których ostatnie trzy n2 . Od razu zauwa»amy, »e takimi liczbami s¡

cyfry s¡ takie same jak w 0 oraz 1.

Po chwili zauwa»amy te», »e 1000, 1001 i wszystkie liczby ko«-

cz¡ce si¦ na 000 lub 001 maj¡ wymagan¡ wªasno±¢.

Dochodzimy wi¦c do

kongruencji

n ≡ n2

(mod 1000),

(10.1)

której rozwi¡zanie da nam wszystkie szukane liczby. Jest to kongruencja 2 drugiego stopnia (f (n) = n − n ). Jej rozwi¡zaniami (modulo 1000) s¡ 0, 1, 376, 625. Gdyby w przykªadzie 10.1 moduª zaliby±my podstawiaj¡c za od

m.

n

m byª maªy, to kongruencj¦ 10.1 rozwi¡-

wszystkie nieujemne liczby caªkowite mniejsze

Metoda ta nie pracuje, je±li

m jest du»¡ liczb¡.

W rozdziale tym poka-

»emy, »e kongruencje o moduªach zªo»onych mo»na zredukowa¢ do kongruencji o moduªach pierwszych. To pozwoli nam rozwi¡za¢ niektóre kongruencje.

pierwiastkiem modulo m wielomianu f (x) o wspóªczynnikach caªkowitych nazywamy tak¡ liczb¦ r , »e f (r) ≡ 0 (mod m). Je±li r 0 jest pierwiastkiem wielomianu f (x) modulo m oraz r ≡ r (mod m), to z Przypomnijmy, »e

40

f (r) ≡ f (r0 ) (mod m), czyli r0 te» jest pierwiastkiem wielomianu f (x) modulo m. Nasze rozwa»ania na temat pierwiastków b¦dziemy ogranicza¢ do Zm i mówi¡c rozwi¡zanie, mamy na my±li rozwi¡zanie modulo m.

twierdzenia 1.7 wynika, »e

Przykªady. 10.2. Wielomian x2 + 2 podstawiaj¡c za

10.3.

x

Wielomian

nie ma pierwiastków modulo 7.

Sprawdzamy to

kolejne liczby 0, 1, 2, 3, 4, 5, 6.

x2 − 2

ma w

Z7

dokªadnie dwa pierwiastki: 3 i 4.

Zauwa»my, »e wielomiany z powy»szych przykªadów s¡ stopnia drugiego, wi¦c na mocy Twierdzenia Lagrange'a nie mog¡ mie¢ wi¦cej ni» 2 pierwiastki.

10.4.

Wielomian

x2 − 1

ma w

Z12

cztery pierwiastki: 1, 5, 7 oraz 11.

m na moduªy b¦αk α1 α2 d¡ce pot¦gami liczb pierwszych z rozkªadu m. Je±li m = p1 p2 . . . pk , to αi kongruencja f (x) ≡ 0 (mod m) implikuje k kongruencji f (x) ≡ 0 (mod pi ), gdzie 1 ≤ i ≤ k . Odwrotna implikacja tak»e zachodzi, poniewa» pot¦gi Rozwa»ymy teraz metod¦ redukcji moduªu zªo»onego

ró»nych liczb pierwszych s¡ kopierwsze.

10.5 Przykªad. Rozwa»my kongruencj¦ x2 ≡ 1 (mod 105).

Poniewa»

105 =

3 · 5 · 7, wi¦c nasza kongruencja jest równowa»na ukªadowi trzech kongruencji x2 ≡ 1 x2 ≡ 1 x2 ≡ 1

(mod 3) (mod 5) (mod 7).

Ka»d¡ z powy»szych kongruencji rozwi¡zujemy podstawiaj¡c kolejne liczby i otrzymujemy w trzech przypadkach po dwa rozwi¡zania: 1 i 2 modulo 3, 1 i 4 modulo 5 oraz 1 i 6 modulo 7. Dowolna kombinacja tych rozwi¡za« daje 2 rozwi¡zanie modulo 105. Oznaczmy przez r pierwiastek wielomianu x − 1 modulo 105. Wówczas

r

jest jednym z rozwi¡za« o±miu poni»szych ukªadów

kongruencji.

r≡1 r≡1 r≡1

(mod 3) (mod 5) (mod 7),

r≡2 r≡1 r≡1

(mod 3) (mod 5) (mod 7), 41

r ≡ 1 (mod 3) r ≡ 4 (mod 5) r ≡ 1 (mod 7),

r ≡ 2 (mod 3) r ≡ 4 (mod 5) r ≡ 1 (mod 7), r≡2 r≡1 r≡6

(mod 3) (mod 5) (mod 7),

r≡1 r≡4 r≡6

r≡1 r≡1 r≡6 (mod 3) (mod 5) (mod 7),

(mod 3) (mod 5) (mod 7), r≡2 r≡4 r≡6

(mod 3) (mod 5) (mod 7).

Rozwi¡zaniami (modulo 105) tych ukªadów kongruencji s¡, kolejno, 1, 71, 64, 29, 76, 41, 34 i 104. Wracaj¡c do przykªadu 10.1, kongruencja (10.1) jest równowa»na ukªadowi kongruencji

n ≡ n2 n ≡ n2

(mod 23 ) (mod 53 ).

(10.2)

Pierwsz¡ kongruencj¦ z (10.2) mo»emy jeszcze rozwi¡za¢ podstawiaj¡c kolejne liczby od 0 do 7. Przy drugiej kongruencji metoda ta zawodzi ze wzgl¦du na zbyt wiele (a» 125) liczb. Zastosujemy wi¦c inn¡ metod¦. Poniewa» kon2 gruencj¦ n ≡ n (mod 5) speªniaj¡ dwie liczby (modulo 5) 0 oraz 1, wi¦c kongruencj¦

n ≡ n2

(mod 52 )

(10.3)

0 + 5k1 oraz 1 + 5l1 . Podstawiamy te liczby do (10.3) 2 2 otrzymuj¡c 5k1 ≡ 0 (mod 5 ) oraz 5l1 ≡ 10l1 (mod 5 ). St¡d kongruencje k1 ≡ 0 (mod 5) i l1 ≡ 2l1 (mod 5), które daj¡ k1 = 0 oraz l1 = 0. Mamy

speªniaj¡ liczby postaci

zatem 2 rozwi¡zania modulo 25: 0 oraz 1. Rozwi¡zaniami modulo 125 drugiej 2 2 kongruencji z (10.3) s¡ liczby postaci 5 k2 oraz 1 + 5 l2 . Wykonuj¡c podobne obliczenia jak powy»ej dostajemy dwa rozwi¡zania: 0 i 1.

Aby rozwi¡za¢

zadanie postawione w przykªadzie 10.1, wystarczy rozwi¡za¢ cztery ukªady kongruencji

r ≡ e1 r ≡ e2 gdzie za

e1

oraz

e2

(mod 2) (mod 5),

podstawiamy 0 lub 1. Cztery szukane rozwi¡zania to 0,

1, 376 i 625.

42

Nasze rozumowanie uogólnimy, podaj¡c je w formie twierdzenia. Zdeniujemy przedtem poj¦cie pochodna wielomianu. Przypu±¢my, »e dany jest wielomian

f (x) = an xn + an−1 xn−1 + · · · + a1 x + a0 . Pochodn¡ wielomianu f (x)

nazywamy wielomian

f 0 (x) = nan xn + (n − 1)an−1 xn−1 + · · · + a1 . Zauwa»my teraz, »e

f (x + y) = f (x) + yf 0 (x) + y 2 g(x, y), gdzie

g(x, y)

(10.4)

jest pewn¡ wielko±ci¡, któr¡ nie jeste±my zainteresowani.

10.6 Twierdzenie. Niech f (x) b¦dzie wielomianem o wspóªczynnikach caªkowitych, a f 0 (x) jego pochodn¡. Przypu±¢my, »e element x0 speªnia kongruencj¦ f (x0 ) ≡ 0 (mod pk ) (dla k ≥ 1). Wówczas kongruencja wielomianowa f (x) ≡ 0 (mod pk+1 ) ma (a) dokªadnie jedno rozwi¡zanie x = x0 + pk t, je»eli p - f 0 (x0 ). Tutaj t jest rozwi¡zaniem kongruencji

pk tf 0 (x0 ) ≡ −f (x0 )

(mod pk+1 ).

(10.5)

(b) p nieprzystaj¡cych do siebie modulo pk+1 rozwi¡za« x = x0 + pk t, je±li p | f 0 (x0 ) oraz pk+1 | f (x0 ). Tutaj t przyjmuje warto±ci 0, 1, . . . , p − 1. (c) zero rozwi¡za« przystaj¡cych do x0 modulo pk , je»eli p | f 0 (x0 ) oraz pk+1 - f (x0 ). Dowód.

x jest rozwi¡zaniem kongruencji f (x) ≡ 0 (mod pk ), k k takim »e x ≡ x0 (mod p ). Mo»emy wi¦c zapisa¢ x = x0 + p t dla pewnej liczby caªkowitej t. Korzystaj¡c z równania (10.4) otrzymujemy Przypu±¢my, »e

f (x) ≡ f (x0 + pk t)

Ale

pk+1


2 ≡ f (x0 ) + pk tf 0 (x0 ) + pk t g(x, pk t)
2 | pk t , wi¦c f (x) ≡ f (x0 ) + pk tf 0 (x0 )

(mod pk+1 ). 43

(mod pk+1 ).

f (x) ≡ 0 (mod pk+1 ), 0 Przypu±¢my teraz, »e p - f (x0 ).

Pami¦taj¡c, »e

dostajemy (10.5). k Poniewa» p | f (x0 ), wi¦c kongruen-

cj¦ (10.5) mo»na zredukowa¢ do kongruencji liniowej (z niewiadom¡

f 0 (x0 )t ≡ −

f (x0 ) pk

która ma dokªadnie jedno rozwi¡zanie. x = x0 + tpk .

(b),

t)

(mod p), St¡d jednoznaczno±¢ rozwi¡zania

p | f 0 (x0 )

pk+1 | f (x0 ). Wówczas kongruencja (10.5) jest speªniona dla dowolnego t ∈ {0, 1, 2, . . . , p − 1}. St¡d p rozwi¡za« x = x0 + tpk . 0 k+1 Je±li p | f (x0 ) oraz p - f (x0 ), to kongruencja (10.5) przybiera sprzeczn¡ k+1 z zaªo»eniem posta¢ 0 ≡ −f (x0 ) (mod p ). Nie ma wi¦c rozwi¡za« postaci x = x0 + tpk , co pokazuje (c). Aby pokaza¢

10.7 Przykªad.

zaªó»my, »e

oraz

Rozwi¡»emy kongruencj¦

x2 + 4x + 2 ≡ 0

(mod 49).

(10.6)

f (x) = x2 +4x+2 oraz 49 = 72 . Zaczynamy wi¦c od kongruencji x + 4x + 2 ≡ 0 (mod 7), dla której znajdujemy rozwi¡zanie podstawiaj¡c po kolei wszystkie liczby od 0 do 6. Znajdujemy dwa pierwiastki x1 = 1 oraz x2 = 2. Poniewa» f 0 (x) = 2x + 4, wi¦c mamy 7 - f 0 (xi ) dla i = 1 oraz i = 2. Zastosujemy wi¦c cz¦±¢ (a) twierdzenia 10.6. Dla x1 otrzymujemy: Mamy tutaj 2

7tf 0 (1) ≡ −f (1) 7t · 6 ≡ −7 6t ≡ −1 t≡1 Zatem

x=1+7=8

72 ) 72 ) 7) 7).

jest pierwiastkiem (10.6). Podobnie,

7tf 0 (2) ≡ −f (2) 7t · 8 ≡ −14 8t ≡ −2 t≡5 wi¦c

(mod (mod (mod (mod

x = 2 + 7 · 5 = 37

(mod (mod (mod (mod

72 ) 72 ) 7) 7),

jest pierwiastkiem kongruencji (10.6).

44

10.8 Przykªad.

Rozwi¡»emy kongruencj¦

x2 + x + 7 ≡ 0 f 0 (x) = 2x + 1,

(mod 9).

(10.7)

x2 + x + 7 ≡ 0 (mod 3), otrzymu0 jemy x0 = 1. Tak si¦ jednak skªada, »e 3 | f (1) oraz 9 | f (1), wi¦c stosujemy twierdzenie 10.6(b), z którego wynika, »e x1 = 1 + 3 · 0 = 1, x2 = 1 + 3 · 1 = 4 i x3 = 1 + 3 · 2 = 7 s¡ pierwiastkami (10.7). Mamy tutaj

10.9 Przykªad.

a rozwi¡zuj¡c

Poszukamy pierwiastków z 1 modulo 16. Rozwa»ymy wi¦c

f (x) = x2 − 1. Modulo 8, ma on 4 pierwiastki: x1 = 1, x2 = 3, x3 = 5 i x4 = 7. Poniewa» f 0 (x) = 2x, wi¦c 2 | f 0 (xi ) dla i ∈ {1, 2, 3, 4}, ale 16 dzieli tylko f (x1 ) i f (x4 ). Na podstawie punktu (c) twierdzenia 10.6 wnioskujemy wi¦c, »e tylko x1 i x4 daj¡ pierwiastki modulo 16. A s¡ to, k zgodnie z punktem (b), 1, 9, 7 i 15. Ogólnie, je±li m = 2 , gdzie k ≥ 3, to k−1 wielomian f (x) ma dokªadnie 4 pierwiastki modulo m: 1, 2 − 1, 2k−1 + 1 k oraz 2 − 1, czyli −1.

wielomian

10.10 Przykªad.

Wró¢my do przykªadu 10.1.

Stosuj¡c twierdzenie 10.6, 2 otrzymujemy rozwi¡zania 0 i 1 dla obu kongruencji n ≡ n (mod 8) oraz 2 n ≡ n (mod 125). Zatem cztery rozwi¡zania kongruencji (10.1) otrzymamy po rozwi¡zaniu nast¦puj¡cych czterech ukªadów:

n1 ≡ 0 (mod 8) n1 ≡ 0 (mod 125) n3 ≡ 1 (mod 8) n3 ≡ 0 (mod 125) S¡ to:

n1 = 0, n2 = 376, n3 = 625

n2 ≡ 0 (mod 8) n2 ≡ 1 (mod 125) n4 ≡ 1 (mod 8) n4 ≡ 1 (mod 125). oraz

n4 = 1.

Zako«czymy ten rozdziaª jeszcze jednym przykªadem, który ma du»e znaczenie przy znajdywaniu rozkªadu liczb na czynniki oraz uzasadnia prawidªowo±¢ gry w orªa i reszk¦ przez telefon.

10.11 Przykªad.

p i q s¡ ró»nymi liczbami pierwszymi oraz x ≡ 1 (mod n) ma dokªadnie 4 rozwi¡zania, 2 2 poniewa» ka»da z kongruencji x ≡ 1 (mod p) oraz x ≡ 1 (mod q) ma dokªadnie dwa rozwi¡zania. Rozwi¡zania ±1 nazywamy trywialnymi. Je±li x jest nietrywialnym rozwi¡zaniem, to NWD(x − 1, n) oraz NWD(x + 1, n) s¡ liczbami p oraz q . Zatem je±li znamy nietrywialne rozwi¡zanie kongruencji x2 ≡ 1 (mod n), to znamy te» rozkªad liczby n. n = pq .

Przypu±¢my, »e 2

Wówczas kongruencja

45

Wykªad 11 Liczby pseudopierwsze Teoria liczb znalazªa najwi¦ksze zastosowanie w kryptograi, a tam potrzeba du»ych liczb pierwszych i to takich, których nikt nie zna. Pojawia si¦ zatem potrzeba szybkich algorytmów szukaj¡cych liczb pierwszych lub testuj¡cych liczby na pierwszo±¢. Warunek równowa»ny pierwszo±ci liczby, daje nam np. Twierdzenie Wilsona, które mówi, »e liczba

n

jest pierwsza wtedy i tylko

(n − 1)! ≡ −1 (mod n). Nie jest to jednak dobre kryterium  ªatwiej sprawdzi¢ czy n jest liczb¡ pierwsz¡ dziel¡c j¡ przez kolejne liczby nieparzyste ni» oblicza¢ (n − 1)! (nawet modulo n). wtedy, gdy

Dobrym testem pierwszo±ci jest Maªe Twierdzenie Fermata (5.1).

Pro-

blem w tym, i» nie jest to warunek równowa»ny pierwszo±ci. Na przykªad,

2340 ≡ 1 chocia»

341

(mod 341),

(11.1)

nie jest liczb¡ pierwsz¡. Nasze rozwa»ania oprzemy jednak na

tym twierdzeniu, badaj¡c które liczby zªo»one speªniaj¡ tez¦ MTF. Liczb¦ zªo»on¡

pseudopierwsz¡ ),

n

nazywamy

pseudopierwsz¡ przy podstawie a

(lub

a-

je±li

an−1 ≡ 1 Piszemy wówczas w skrócie: dopierwsza przy podstawie

a

n

(mod n).

(11.2)

jest psp(a). Zauwa»my, »e ka»da liczba pseu-

jest wzgl¦dnie pierwsza z

a,

Jak wynika z (11.1), liczba 341 jest 2-pseudopierwsza. Jak pokazaª Sarrus w 1819 roku, jest to najmniejsza liczba pseudopierwsza przy podstawie 2. Kolejne odkrywane liczby psp(2) byªy nieparzyste. Dopiero w 1950, D.H. Lehmer odkryª pierwsz¡ parzyst¡ liczb¦ 2-pseudopierwsz¡. Najmniejsz¡ liczb¡ pseudopierwsz¡ przy podstawie 3 jest, natomiast, 91.

46

Skoro najmniejsze liczby pseudopierwsze s¡ tak du»e, to powstaje pytanie, czy jest ich niesko«czenie wiele. Odpowied¹ jest pozytywna.

11.1 Twierdzenie.

Mamy niesko«czenie wiele liczb pseudopierwszych przy

Dowód.

b¦dzie dowoln¡ liczb¡ pierwsz¡. Rozwa»my liczby

podstawie a.

Niech

p>2

n=

ap − 1 , a−1

m=

ap + 1 , a+1

N = nm.

nie jest dzielnikiem a, a − 1 ani a + 1. Wówczas z Maªego p−1 Twierdzenia Fermata mamy p | a − 1. Poniewa» a − 1 | ap−1 − 1 oraz ap−1 −1 NWD(p, a − 1) = 1, wi¦c p | . Zatem a−1 Przypu±¢my, »e

p

n−1=

ap − ap−1 + ap−1 − 1 ap−1 − 1 − 1 = ap−1 − 1 + a−1 a−1

jest podzielna przez

n−1

p.

Dodatkowo jeszcze,

n = 1 + a + a2 + · · · + ap−1 ,

wi¦c

jest sum¡ parzystej ilo±ci liczb o tej samej parzysto±ci, czyli jest liczb¡

parzyst¡. Zatem

2p | n − 1.

Dalej, mamy

m−1=

ap − a ap−1 − 1 =a . a+1 a+1

p - a + 1, wi¦c, podobnie jak poprzednio, zauwa»amy »e 2p | m − 1. N − 1 = nm − 1 = (n − 1)(m − 1) + (n − 1) + (m − 1), wi¦c 2p | N − 1.

Poniewa» Ale,

Zauwa»my teraz, »e

N = nm = czyli

N (a2 − 1) = a2p − 1

a2p − 1 ap − 1 ap + 1 · = 2 , a−1 a+1 a −1

i

a2p ≡ 1

(mod N ).

(11.3)

aN −1 − 1. Poniewa» 2p | N − 1, wi¦c istnieje liczba k , taka »e N − 1 = 2pk . Po podniesieniu obu stron kongruencji (11.3) do pot¦gi k

Rozwa»my

otrzymujemy

aN −1 ≡ 1 Zatem

N,

(mod N ).

która jest oczywi±cie liczb¡ zªo»on¡, jest psp(a).

Oczywi±cie, takich liczb

N

jest niesko«czenie wiele, poniewa» mamy nie-

sko«czenie wiele liczb pierwszych, za pomoc¡ których mo»emy zdeniowa¢ liczby

n

oraz

m. 47

Posªu»ymy si¦ algorytmem z powy»szego twierdzenia.

p = 5

Dla

a = 2

oraz

N = 341, a dla p = 7, liczb¦ 5461. Podobnie, p = 5, dostajemy liczb¦ N = 7381, pseudopierwsz¡

otrzymujemy liczb¦

podstawiaj¡c

a=3

oraz

przy podstawie 3. Ogólnie, mamy 5597 liczb psp(2) mniejszych od miliarda oraz 5804 liczby psp(3) mniejsze od miliarda. Posiadaj¡c baz¦ tych liczb mo»emy zastosowa¢ nast¦puj¡cy test pierwszo±ci dla liczb 1. sprawd¹, czy liczba

a = 2,

n

n

mniejszych od miliarda:

speªnia tez¦ Maªego Twierdzenia Fermata dla

je±li tak

n jest na li±cie n jest pierwsza.

2. sprawd¹, czy liczba stawie 2. Je±li nie,

3. Je±li tak, powtórz kroki 1 i 2 dla

liczb pseudopierwszych przy pod-

a = 3.

Jak wida¢, liczby pseudopierwsze nie s¡ tak g¦sto rozmieszczone jak liczby pierwsze. Wydaje si¦ wi¦c, »e bior¡c odpowiednio du»o pocz¡tkowych liczb pierwszych jako podstawy dojdziemy w ko«cu do sytuacji, w której nie znajdziemy liczb pseudopierwszych mniejszych od okre±lonej liczby. Jak odkryª w 1912 roku R.D. Carmichael, jest to sytuacja niemo»liwa. Liczb¦ zªo»on¡

liczb¡ Carmichaela, pierwszej z n. Jak pokazaª

n

jest psp(a) dla ka»dej liczby

a

n

nazywamy

je±li

wzgl¦d-

nie

w roku 1992 A. Granville, liczb Carmichaela

jest niesko«czenie wiele. Podamy przykªad jednej z nich.

11.2 Przykªad.

Mamy

561 = 3 · 11 · 17.

Niech

a

b¦dzie liczb¡ wzgl¦dnie

pierwsz¡ z 561. Korzystaj¡c z Maªego Twierdzenia Fermata, otrzymujemy:

a2 ≡ 1 (mod 3) a10 ≡ 1 (mod 11) a16 ≡ 1 (mod 17)

a560 ≡ (a2 )280 ≡ 1 (mod 3) a560 ≡ (a10 )56 ≡ 1 (mod 11) a560 ≡ (a16 )35 ≡ 1 (mod 17).

⇒ ⇒ ⇒

Dalej, z chi«skiego twierdzenia o resztach, dostajemy

a560 ≡ 1 (mod 561),

co oznacza, »e 561 jest liczb¡ Carmichaela. Do±¢ du»y post¦p w skuteczno±ci testów opartych na liczbach pseudopierwszych daje nast¦puj¡ca obserwacja. Je±li liczba p jest pierwsza, to kon2 gruencja x ≡ 1 (mod p) ma dokªadnie 2 rozwi¡zania: 1 i −1 (twierdzenie Lagrange'a). Z tego samego twierdzenia wynika, »e je»eli kongruencja

x2 ≡ 1

(mod n) 48

ma wi¦cej ni» dwa rozwi¡zania, to testowania liczby

n

n musi by¢ liczb¡ zªo»on¡.

na pierwszo±¢ sprowadza si¦ do szukania nietrywialnych

pierwiastków stopnia 2 z jedynki modulo by

Zatem problem

n.

Z oczywistych wzgl¦dów, b¦dziemy dalej rozwa»a¢ tylko nieparzyste liczr Skoro n jest nieparzysta, to n − 1 mo»na zapisa¢ w postaci 2 s, gdzie s

n.

r > 0. pseudopierwsza przy podstawie a. jest liczb¡ nieparzyst¡ oraz

Przypu±¢my, »e liczba n jest pierwsza lub n−1 Wówczas a ≡ 1 (mod n). Rozwa»amy

po kolei liczby

x1 = a2s mod n,

x0 = as mod n,

...

rs

x r = a2

mod n.

Zauwa»my, »e aby obliczy¢ warto±ci wszystkich wyrazów ci¡gu

X = (x0 , x1 , . . . , xr ), wystarczy obliczy¢ redukowa¢ modulo

x0 , a nast¦pnie podnosi¢ j¡ sukcesywnie do kwadratu i n otrzymuj¡c kolejne wyrazy. Ostatecznie, mamy 3 mo»-

liwo±ci: 1. istnieje 2. istnieje 3.

0 < t ≤ r, 0 < t ≤ r,

takie »e takie »e

xt = 1 oraz xt−1 = −1, xt = 1, xt−1 6= ±1,

x0 = 1.

i > t mamy xi = 1. Zatem je±li w pewnym momencie konstrukcji w ci¡gu X pojawi si¦ 1, to wszystkie nast¦pne wyrazy n−1 te» s¡ równe 1. Poniewa» xr = a , wi¦c xr = 1. Je±li speªniony jest 2 warunek 2, to oznacza to, »e kongruencja x ≡ 1 (mod n) ma wi¦cej ni» dwa pierwiastki (bo 1, −1 oraz xt−1 ), czyli n na pewno nie jest liczb¡ pierwsz¡. Oczywi±cie, je±li

xt = 1,

to dla

Pozostaªe przypadki daj¡ nast¦puj¡c¡ denicj¦.

n jest nieparzyst¡ psp(a). Mówimy, »e n jest liczb¡ silnie pseudopierwsz¡, przy podstawie a lub spsp(a), je»eli as ≡ 1 (mod n) lub 2t s istnieje 0 < t < r , takie »e a ≡ −1 (mod n), gdzie n − 1 = 2r s, s jest liczb¡ nieparzyst¡ oraz r > 0. W terminologii ci¡gu X mamy, »e n jest spsp(a), je±li jest speªniony Przypu±¢my, »e

warunek 1 lub 3.

11.3 Przykªad. 2

2 · 85

Rozwa»my najmniejsz¡ psp(2), czyli 341.

Mamy

340 =

x0 = 32, x1 =1. Oznacza to, »e 341 nie jest spsp(2). Co wi¦x0 jest nietrywialnym pierwiastkiem kwadratowym z 1 modulo 341, wi¦c mo»emy znale¹¢ rozkªad 341 obliczaj¡c NWD(32 − 1, 341) = 31 oraz NWD(32 + 1, 341) = 11. oraz

cej, poniewa»

49

11.4 Przykªad.

n = 561.

Jest to liczba Carmichaela, czyli jest ona 4 pseudopierwsza przy ka»dej podstawie. Mamy 560 = 2 · 35 i niech a = 2. Wówczas

x0 = 263, x1 = 166, x2 = 67, x3 = 1.

11.5 Przykªad. jest

We¹my

Zatem 561 nie jest spsp(2).

Najmniejsz¡ liczb¡ silnie pseudopierwsz¡ przy podstawie 2

2047 = 23 · 89. Poka»emy, »e jest to istotnie liczba silnie pseudopierwsza. 2046 = 2 · 1023 oraz x0 = 1.

Mamy

Wszystkich liczb psp(2) mniejszych od dziesi¦ciu miliardów jest 14884, ale liczb spsp(2) jest ju» tylko 3291. Najmniejsz¡ liczb¡ b¦d¡c¡ jednocze±nie spsp(2) oraz spsp(3) jest

1373653 = 829 · 1657.

Nie ma liczby mniejszej od

dziesi¦ciu miliardów, która by byªa jednocze±nie spsp(a) dla liczb dziaªu

[2, 13].

a

z prze-

Mimo to liczb silnie pseudopierwszych przy dowolnej podsta-

wie jest niesko«czenie wiele, co udowodnili C. Pomerance, J.L. Selfridge i S.S. Wagsta w 1980 roku. Trudny dowód ogólnego twierdzenia pomijamy i zadowolimy si¦ tylko dowodem w przypadku

11.6 Twierdzenie.

a = 2.

Je±li n jest nieparzyst¡ psp(2), to 2n − 1 jest spsp(2).

Dowód. Poniewa» n jest liczb¡ zªo»on¡, wi¦c tak»e 2n − 1 jest liczb¡ zªo»on¡. n−1 Dalej, n jest psp(2), wi¦c 2 ≡ 1 (mod n). n−1 Zapiszmy 2 − 1 = nk , przy czym liczba k (tak jak n) jest nieparzysta. n n Niech m = 2 −1. Wówczas m−1 = 2 −2 = 2nk . Zatem cz¦±ci¡ nieparzyst¡ m − 1 jest s = nk . n Poniewa» mamy oczywist¡ kongruencj¦ 2 − 1 ≡ 0 (mod m), wi¦c zan chodzi te» 2 ≡ 1 (mod m). Podnosz¡c strony tej kongruencji do pot¦gi k nk otrzymamy 2 ≡ 1 (mod m), czyli 2s ≡ 1 (mod m) i m jest spsp(2).

50

Wykªad 12 Pierwiastki pierwotne Rz¦dem elementu a modulo n nazywamy najmniejsz¡ liczb¦ dodatni¡ k , tak¡ »e ak ≡ 1 (mod n). Zauwa»my, »e, z uwagi na twierdzenie Eulera, k ≤ ϕ(n). B¦dziemy pisa¢ k = ordn a. Przypu±¢my, »e liczby

12.1 Przykªad.

a

oraz

n > 1

s¡ wzgl¦dnie pierwsze.

1 modulo n jest jeden, a rz¦dem −1 modulo n > 2 jest dwa, ale dla dowolnej liczby nieparzystej l (wi¦c i dla −1), zachodzi ord2 l = 1. Obliczaj¡c kolejne pot¦gi liczby 2 modulo 31, zauwa»amy, »e ord31 2 = 5. Podobnie obliczamy ord31 3 = 30. W tym ostatnim przypadku ordn a = ϕ(n). 5 Przypu±¢my, »e x ≡ 1 (mod n). Zatem ordn x ≤ 5. Je±li x 6≡ 1 (mod n), to rz¡d elementu x nie mo»e by¢ równy 1. Nie mo»e to by¢ te» 2, bo wówczas x5 ≡ (x2 )2 x ≡ x 6≡ 1 (mod n). Z podobnych przyczyn, rz¦dem elementu x modulo n nie mo»e by¢ 3 ani 4. Podobnie mo»emy pokaza¢, »e je±li dla p dowolnej liczby pierwszej p, x ≡ 1 (mod n), oraz x 6≡ 1 (mod n) to wtedy ordn x = p. Rz¦dem

Poka»emy teraz kilka podstawowych wªasno±ci rz¦du elementu. W ka»dym z nast¦puj¡cych twierdze« zakªadamy, »e

12.2 Twierdzenie. Dowód.

Oznaczmy

rz¦du.

jest wzgl¦dnie pierwsza z

Przypu±¢my, »e am ≡ 1 (mod n). Wówczas

ordn a

k = ordn a i zapiszmy m = qk +r, gdzie 0 ≤ r < k . 1 ≡ am ≡ (ak )q ar ≡ ar

r < k , wi¦c r = 0, Zatem k | m.

Poniewa»

a

n.

| m.

Mamy

(mod n).

bo inaczej mieliby±my sprzeczno±¢ z denicj¡

51

12.3 Wniosek.

1. Je±li ai ≡ aj (mod n), to i ≡ j (mod ordn a), 2. ordn a jest dzielnikiem ϕ(n). W szczególno±ci, je»eli n jest liczb¡ pierwsz¡, to ordn a | p − 1. 3. Je»eli ordn a = k , to 1, a, a2 , . . . , ak−1 s¡ ró»ne modulo n.

Dowód.

j Skoro a jest elementem odwracalnym i−j i−j modulo n, wi¦c istnieje element a oraz a ≡ 1 (mod n). Zatem i−j

i ≥ j.

1. Przypu±¢my, »e

musi by¢ wielokrotno±ci¡ rz¦du elementu

a,

czyli

i ≡ j (mod

ordn a).

2. Wynika bezpo±rednio z twierdzenia 12.2 oraz Maªego Twierdzenia Fermata lub Twierdzenia Eulera. 3. Wynika bezpo±rednio z punktu 1. Twierdzenie 12.2 oraz wniosek po nim pozwalaj¡ w istotny sposób uªatwi¢ obliczenie rz¦du liczby. Dla przykªadu, rozwa»my liczb¦

ϕ(31) = 30,

wi¦c dla liczby

a

ord31 a

wzgl¦dnie pierwszej z

31,

n = 31.

Poniewa»

mamy

∈ {1, 2, 3, 5, 6, 10, 15, 30} .

Wystarczy wi¦c sprawdzi¢ tylko 8 liczb zamiast 30. 2 n−1 Je±li ordn a = n−1, to zbiór {0, a, a , . . . , a } jest peªnym ukªadem reszt

{0, 1, 2, . . . , n − 1}, zwªaszcza je±li chcemy bada¢ wªasno±ci multyplikatywne modulo n. Je»eli jest nam znany rz¡d liczby a modulo n, to dobrze byªoby zna¢ szybk¡ metod¦ wyznaczenia rz¦du dowolnej pot¦gi liczby a. Tak¡ metod¦ modulo

n

i mo»e on by¢ u»ywany w miejscu

daje nam nast¦puj¡ce twierdzenie.

12.4 Twierdzenie. Dowód.

Oznaczmy

Je±li

l=

(a, n) = 1, to

NWD

ordn a

(

NWD ordn

a, k)

ordn a

k

k

ordn a

(

NWD ordn

a, k)

.

. Poniewa»

(ak )l ≡ akl ≡ (aordn a )(k/NWD(ordn a, k)) ≡ 1 wi¦c ordn a

=

(mod n),

| l.

m = ordn ak . Wówczas (ak )m ≡ akm ≡ 1 (mod n), wi¦c ordn a | km. Zapiszmy km = c · ordn a dla pewnej liczby c. Obie strony ostatniej równo±ci podzielmy przez NWD(ordn a, k). Otrzymamy Oznaczmy teraz

k (

NWD ordn

a, k) 52

m = cl.

Ale NWD

yk =



 , l =1 NWD(ordn a, k) k

(

NWD ordn

a, k),

czyli

gdy» istniej¡ takie liczby

y NWD(ordk n a, k) + xl = 1.

wcze±niej udowodnionego daje nam

x

y,

oraz

Zatem

»e

x · ordn a +

l | m,

co wobec

l = m.

U»ywaj¡c wzoru z powy»szego twierdzenia i wiedz¡c, »e ordn a

= 12,

otrzymujemy

k ordn a

k

0

1

2

3

4

5

6

7

8

9

10

11

1

12

6

4

3

12

2

12

3

4

6

12

Niech a b¦dzie liczb¡ wzgl¦dnie pierwsz¡ z n. Liczba a jest pierwiastkiem pierwotnym modulo n, je±li ordn a = ϕ(n). Pierwiastkiem pierwotnym mo2 dulo 31 jest liczba 3, ale nie jest nim liczba 2. Poniewa» a ≡ 1 (mod 8) dla dowolnej liczby a wzgl¦dnie pierwszej z 8, wi¦c nie ma pierwiastków pierwotnych modulo 8. Ostatni fakt uogólnimy w nast¦puj¡cym twierdzeniu.

12.5 Twierdzenie. dulo 2 .

Je±li k ≥ 3, to nie ma pierwiastka pierwotnego mo-

k

Dowód. Przypu±¢my, 2 2k−1 wi¦c a, a , . . . , a

k k−1 istnieje. Poniewa» ϕ(2 ) = 2 , k s¡ ró»nymi elementami modulo 2 i wszystkie one s¡ k odwracalne. Co wi¦cej, nie ma innego elemnetu odwracalnego modulo 2 ni» k te, które znajduj¡ si¦ na li±cie. Istnieje zatem tylko jeden element modulo 2 , »e taki pierwiastek

a

który ma rz¡d 2, gdy» je±li

ord2k a

to NWD


i, 2k−1 = 2k−2 ,

czyli

i

=

2k−1 = 2, NWD(i, 2k−1 )

i = 2k−2 . x2 ≡ 1

Poka»emy teraz, »e kongruencja

(mod 2k )

ma przynajmniej 4 rozwi¡zania, wi¦c elementów odwracalnych modulo

2k

rz¦du 2 jest wi¦cej ni» 1. St¡d otrzymamy sprzeczno±¢. 2 k Rozwa»my wi¦c kongruencj¦ x ≡ 1 (mod 2 ). Jej pierwiastkami s¡ 1 k−1 oraz −1, ale tak»e liczby y1 = 2 − 1 i y2 = 2k−1 + 1 (porównaj z przykªadem 10.9), poniewa»

yi2 = (2k−1 ± 1)2 = 22(k−1) ± 2k + 1 ≡ 1 53

(mod 2k ).

Udowodnione wªa±nie twierdzenie jest rezultatem negatywnym, poniewa» mówi nam, dla jakich liczb nie nale»y szuka¢ pierwiastków pierwotnych. Za-

n=2

uwa»my, »e dla

oraz

n = 4,

pierwiastki pierwotne modulo

n

istniej¡.

Istnieje te» pierwiastek pierwotny modulo 31.

12.6 Przykªad. ϕ(16) = 8).

Nie ma elementu rz¦du 8 modulo 16 (bo

16 = 24

Mamy te» 8 elementów odwracalnych modulo 16.

nich jest element neutralny 1, który ma rz¡d 1.

oraz

Jednym z

Mamy te» trzy elementy

rz¦du 2: 7, 9 i 15. Pozostaªe 4 elementy (3, 5, 11, 13) s¡ rz¦du 4. Je±li istnieje pierwiastek pierwotny modulo

n,

to z jego pomoc¡ mo»emy

rozwi¡zywa¢ kongruencje wykªadnicze. Dla przykªadu rozwa»my

n = 17 oraz

liczb¦ 3. Mamy

k k

3

mod 17

k k

3

mod 17

1

2

3

4

5

6

7

8

3

9

10

13

5

15

11

16

9

10

11

12

13

14

15

16

14

8

7

4

12

2

6

1

x 11 Rozwi¡»emy kongruencj¦ 7 ≡ 4 (mod 17). Poniewa» 7 ≡ 3 (mod 17) 12 oraz 4 ≡ 3 (mod 17), wi¦c nasza kongruencja sprowadza si¦ do 311x ≡ 312

(mod 17).

Zatem

11x ≡ 12 czyli

x = 4 + 16k ,

gdzie

(mod 16),

k ∈ Z.

U»ywaj¡c pierwiastków pierwotnych mo»emy te» ªatwo znale¹¢ liczb¦ odwrotn¡ do danej. Na przykªad, dla

13 ≡ 34 St¡d

n = 17

oraz

a=3

mamy

(mod 17).

13−1 ≡ 316−4 ≡ 4 (mod 17).

Niestety, okazuje si¦, »e dla wi¦kszo±ci liczb zªo»onych nie ma pierwiastka pierwotnego.

54

Wykªad 13 Istnienie pierwiastków pierwotnych Pokazali±my ju», »e o ile k > 2, to nie istniej¡ pierwiastki pierwotne mo2k . Nast¦pne twierdzenie znacznie rozszerzy klas¦ liczb, dla których nie

dulo

ma pierwiastków pierwotnych.

13.1 Twierdzenie. Przypu±¢my, »e p jest nieparzyst¡ liczb¡ pierwsz¡.

Je»eli n 6= pk oraz n 6= 2pk dla pewnego k > 0, to nie istnieje pierwiastek pierwotny modulo n. Dowód.

n speªnia zaªo»enia twierdzenia, to n = rs, gdzie r > 2, s > 2 oraz NWD(r, s) = 1. Wówczas ϕ(n) = ϕ(r)ϕ(s), przy czym zarówno ϕ(r) jak i ϕ(s) jest liczb¡ parzyst¡. Z twierdzenia Eulera mamy: Je±li

a a

ϕ(r)ϕ(s) 2 ϕ(r)ϕ(s) 2

Zatem, poniewa» NWD(r,

≡ a

s) = 1, a


ϕ(s) 2

≡1

(mod r),


ϕ(r) ϕ(s) 2

≡1

(mod s).

≡ aϕ(r)

otrzymujemy

ϕ(r)ϕ(s) 2

≡1

ϕ(n) 2

(mod rs),

≡ 1 (mod n) dla dowolnej liczby a wzgl¦dnie pierwszej z n. Czyli »adna liczba a wzgl¦dnie pierwsza z n nie mo»e by¢ pierwiastkiem pierwotnym modulo n.

czyli

a

55

Poka»emy, »e dla pozostaªych liczb, tj.

dla pot¦g i podwojonych po-

t¦g nieparzystych liczb pierwszych pierwiastki pierwotne istniej¡.

Ale aby

udowodni¢ odpowiednie twierdzenie potrzebujemy pewnych wiadomo±ci na temat wykªadników uniwersalnych.

ϕ(n) mo»e by¢ poprawiona do takiej liczby w(n) < ϕ(n), »e dla dowolnej liczby a wzgl¦dnie pierwszej z n zachodzi Twierdzenie 6.6 mówi, »e liczba

kongruencja

aw(n) ≡ 1

(mod n).

(13.1)

λ(n)

i nazywamy

n, to λ(n) = ϕ(n).

W przykªa-

Najmniejsz¡ liczb¦ dodatni¡ o wªasno±ci (13.1) oznaczamy

wykªadnikiem uniwersalnym modulo n. Je±li istnieje pierwiastek pierwotny modulo

dzie 12.6 pokazali±my, »e λ(16) = 4. Rezultat ten mo»na uogólni¢ i pokaza¢, k k−2 »e λ(2 ) = 2 dla k ≥ 3. Poka»emy, »e dla ka»dego n istnieje element rz¦du

λ(n)

modulo

n.

13.2 Lemat.

element rz¦du Dowód.

Potrzebny nam b¦dzie nast¦puj¡cy lemat.

Przypu±¢my, »e ordn a = k , oraz (k, l) modulo n.

ordn b

= l. Wówczas istnieje

NWW

Zapiszmy

k = xu i l = yv ,

przy czym NWD(x, y) = 1, xy = NWW(k, l). u = x oraz ordn bv = y . Rozwa»my liczb¦

Z twierdzenia 12.4 wynika, »e ordn a c = au bv . Poniewa»

cxy ≡ (au )x (bv )y ≡ 1

(mod n),

| xy . Z drugiej strony, je±li ordn c 6= xy , to ordn c = x1 y1 , gdzie x1 | x, y1 | y i zachodzi przynajmniej jedna z nierówno±ci x1 < x, y1 < y . Mo»emy zaªo»y¢, »e y1 < y . Zapiszemy w tym wypadku x2 ordn c = xy1 , przy czym x1 x2 = x. Zatem

wi¦c ordn c

1 ≡ cxy1 ≡ (bv )xy1 Ale to oznacza, »e rz¡d wi¦c

y | y1 ,

bv

jest dzielnikiem

co jest sprzeczne z nierówno±ci¡ ordn c

Dla przykªadu rozwa»my ordn 7

(mod n).

= 30.

xy1 , a poniewa» y1 < y . Zatem

(x, y) = 1,

= xy = NWW(k, l).

n = 465.

Mo»na pokaza¢, »e ordn 2

Istnieje zatem element rz¦du 60 modulo 465.

= 20

oraz

Dowód lematu

in explicite. Mianowicie, rozpisujemy 20 = 4·5, NWW(20, 30) = 4 · 15 oraz NWD(4, 15) = 1. St¡d

pozwala wskaza¢ ten element

30 = 15 · 2 i otrzymujemy 5 2 liczba 2 · 7 ma rz¡d 60.

NWD

56

13.3 Twierdzenie. Dowód.

Dla ka»dego n istnieje liczba caªkowita a rz¦du λ(n).

M = max {ordn x : NWD(x, n) = 1}. Wówczas M ≤ λ(n). y , »e ordn y - M , to mo»emy skonstruowa¢ taki element t, »e ordn t = NWW(ordn a, M ) > M . Ale takich elementów nie ma, wi¦c rz¡d ka»dej liczby wzgl¦dnie pierwszej z n jest dzielnikiem M . M Oznacza to jednak, »e x ≡ 1 (mod n) dla ka»dej liczby x wzgl¦dnie pierwszej z n, czyli λ(n) ≤ M . Tak wi¦c λ(n) = M , a z denicji M wynika, »e istnieje liczba a rz¦du M . Zapiszmy

Je±li istnieje taka liczba caªkowita

Z powy»szego twierdzenie i twierdzenia Lagrange'a wynika twierdzenie o istnieniu pierwiastka pierwotnego modulo liczba pierwsza.

13.4 Twierdzenie. wotny modulo p.

Dla ka»dej liczby pierwszej p istnieje pierwiastek pier-

Dowód. Przypu±¢my, nie wprost, »e λ(p) < p − 1. Oznacza to, »e kongruenλ(p) cja x ≡ 1 (mod p) ma p − 1 > λ(p) pierwiastków modulo p, a to przeczy twierdzeniu Lagrange'a. Zatem λ(p) = p − 1 i element rz¦du λ(p) jest pierwiastkiem pierwotnym modulo p.

13.5 Wniosek.

Przypu±¢my, »e d | p − 1 oraz d > 0. Wówczas elementów rz¦du d modulo p jest ϕ(d).

Dowód.

Rozwa»my pierwiastek pierwotny

wynika, »e ordp g

p − 1) = p − 1 = d0 d.

St¡d NWD(i, Zapiszmy

0

i

=

g

modulo

d = NWD(i, p − 1) = NWD

Z twierdzenia 12.4

p−1 = d. NWD(i, p − 1)

p−1 , czyli istnieje liczba d Wtedy



p.

j(p − 1) , dd0 d

czyli NWD(j,



j,

taka »e

i = j(p − 1)/d.

= NWD(jd0 , dd0 ) = d0 NWD(j, d),

d) = 1, a takich liczb j modulo d i wykªadników i daj¡cych g rz¡d d jest ϕ(d).

jest dokªadnie

ϕ(d).

Zatem

Jak ju» zauwa»yli±my istniej¡ pierwiastki pierwotne modulo 4 oraz modulo dowolna liczba pierwsza.

Bior¡c pod uwag¦ przypadki liczb zªo»ok nych wykluczone przez twierdzenie 13.1, pozostaje nam rozwa»y¢ liczby p k oraz 2p , gdzie p jest nieparzyst¡ liczb¡ pierwsz¡ oraz k > 1. W trzech

57

nast¦puj¡cych twierdzeniach poka»emy istnienie pierwiastków pierwotnych modulo te liczby. Twierdzenia te poª¡czone s¡ ze sob¡ ªa«cuchem wynikania, tj. zaªo»enie nast¦pnego twierdzenia jest praktycznie tez¡ poprzedniego. Zaªo»enie pierwszego z tych twierdze« jest speªnione na mocy twierdzenia 13.4.

13.6 Twierdzenie.

Je±li g jest pierwiastkiem pierwotnym modulo p, to g lub g + p jest pierwiastkiem pierwotnym modulo p2 . Dowód.

k = ordp2 g . Skoro ϕ(p2 ) = p(p − 1), wi¦c k | p(p − 1). k 2 k Mamy zatem g ≡ 1 (mod p ), czyli tak»e g ≡ 1 (mod p). Poniewa» g jest pierwiastkiem pierwotnym modulo p, wi¦c p − 1 | k . St¡d k = p(p − 1) lub k = p − 1. W pierwszym przypadku g jest pierwiastkiem pierwotnym 2 modulo p . W drugim przypadku rozwa»my g + p. Oznaczmy l = ordp2 (g + p). Podobnie jak na pocz¡tku dowodu, mamy l | p(p − 1). Poniewa» g + p ≡ g (mod p), wi¦c g + p jest pierwiastkiem pierwotnym modulo p i p − 1 | l , czyli l = p − 1 lub l = p(p − 1). Przypu±¢my, »e zachodzi ten gorszy przypadek, czyli »e l = p − 1. Wówczas   p p p (g + p) ≡ g + pg p−1 + p2 co± ≡ g p + p2 g p−1 ≡ g p (mod p2 ). 1 Niech

p−1 Ale z pierwszej cz¦±ci dowodu wynika g ≡ 1 (mod 2 (mod p ). Z drugiej strony, skoro l = p − 1, wi¦c (g + 2 2 Zatem g + p ≡ g (mod p ), co oznacza, »e p | p.

p2 ), wi¦c (g + p)p ≡ g p)p ≡ g + p (mod p2 ).

Tak wi¦c otrzymali±my sprzeczno±¢, która mówi, »e p2 .

l = p(p − 1) i g + p

jest pierwiastkiem pierwotnym modulo

13.7 Twierdzenie.

Je»eli g jest pierwiastkiem pierwotnym modulo p2 , to g jest te» pierwiastkiem pierwotnym modulo pk+1 dla k ≥ 2. Dowód.

p−1 Z Maªego Twierdzenia Fermata mamy g ≡ 1 (mod p), wi¦c istp−1 p−1 = 1 + kp. Ale g 6≡ 1 (mod p2 ), czyli nieje liczba caªkowita k , taka »e g

k

nie mo»e by¢ wielokrotno±ci¡

Zachodzi

k (p−1)

= (1 + kp)p

k

≡ 1 + pk · pk

k−1 (p−1)

= (1 + kp)p

k−1

≡ 1 + pk−1 · pk ≡ 1 + kpk (mod pk+1 ).

gp gp

p.

≡1

(mod pk+1 ), (13.2)

1 + kpk 6≡ 1 (mod p)k+1 . Przypu±¢my, »e s | p−1, r ≤ k oraz g ≡ 1 (mod pk+1 ). Wówczas tak»e spr 2 r g ≡ 1 (mod p ), wi¦c p(p − 1) | sp , czyli p − 1 | s, a zatem p − 1 = s. k+1 Tak wi¦c ordp g = pr (p − 1). Ale r nie mo»e by¢ mniejsza od k , bo to k+1 by dawaªo sprzeczno±¢ z 13.2. Zatem ordp g = pk (p − 1) = ϕ(pk+1 ).

Poniewa»

k

nie jest wielokrotno±ci¡

p,

wi¦c spr

58

13.8 Twierdzenie. Je±li g jest nieparzystym pierwiastkiem pierwotnym mo-

dulo pk (k ≥ 1), to g jest te» pierwiastkiem pierwotnym modulo 2pk . Je»eli g jest liczb¡ parzystym pierwiastkiem pierwotnym, to g + pk jest pierwiastkiem pierwotnym modulo 2pk .

Dowód. Na pocz¡tku dowodu zauwa»my, »e ϕ(2pk ) = ϕ(pk ). Przypu±¢my, s k »e g jest liczb¡ nieparzyst¡ oraz s = ord2pk g . Wówczas g ≡ 1 (mod 2p ), a s k co za tym idzie g ≡ 1 (mod p ). Poniewa» g jest pierwiastkiem pierwotnym k k k modulo p , wi¦c ϕ(p ) | s. Z drugiej strony s | ϕ(2p ) i, ostatecznie, s = k ϕ(2p ), czyli g jest pierwiastkiem pierwotnym modulo 2pk . k Przypu±¢my teraz, »e g jest liczb¡ parzyst¡ oraz t = ord2pk (g + p ). Podobnie jak do tej pory

1 ≡ (g + pk )t ≡ g t wi¦c

ϕ(pk ) | s i g + pk

(mod pk ),

jest pierwiastkiem pierwotnym modulo

2pk .

Rozwa»my dla przykªadu liczb¦ 29 oraz pierwiastek pierwotny 14 mo= 28 6= ϕ(292 ) = 29 · 28. Oznacza to, »e = 14 + 29 jest pierwiastkiem pierwotnym modulo 292 oraz modulo 29k

dulo 29. Okazuje si¦, »e ord292 14

43

k ≥ 3. Poniewa» 14 jest liczb¡ parzyst¡, wi¦c nie jest ona wzgl¦dnie pierwsza z 58 = 2 · 29 i 43 jest te» pierwiastkiem pierwotnym modulo 58 oraz k modulo 2 · 29 dla k ≥ 2. dla

59

Wykªad 14 Logarytm dyskretny jest pierwiastkiem pierwotnym modulo n. W naszym przyk k padku oznacza to, »e n = p lub n = 2p , gdzie p jest nieparzyst¡ liczb¡ y pierwsz¡. Je»eli g ≡ x (mod n), to mówimy »e y jest logarytmem dyskret-

Zaªó»my, »e

nym

lub

g

indeksem

z

x

przy podstawie

logg x ≡ y

g.

Mo»emy zapisa¢

g y ≡ x (mod n).

⇔

(mod ϕ(n))

(14.1)

Mamy tu funkcj¦

logg : Zn → Zϕ(n) ,

logg : x 7→ y,

której warto±ci s¡ trudne do obliczenia. Dla odmiany, warto±ci funkcji wykªadniczej obliczamy w miar¦ prosto. typowym przykªadem

logg jest wi¦c Tego rodzaju funkcje wyko-

Funkcja odwrotna do

funkcji jednokierunkowej.

rzystywane s¡ w kryptograi.

14.1 Przykªad. wi¦c

Niech

log3 (−1) = 8.

n = 17

oraz

g = 3.

Podobnie sprawdzamy, »e

38 ≡ −1 (mod 17), log3 4 = 12 oraz log7 4 = 4. Poniewa»

Podstawowe wªasno±ci logarytmu dyskretnego s¡ zawarte w nast¦puj¡cym twierdzeniu.

14.2 Twierdzenie.

Przypu±¢my, »e g jest pierwiastkiem pierwotnym modulo n. Zachodz¡ nast¦puj¡ce wªasno±ci. (a) logg 1 = 0, (b) logg g = 1, (c) logg (x1 x2 ) ≡ logg x1 +logg x2 (mod ϕ(n)) dla dowolnych liczb x1 , x2 ∈ Z, 60

(d) logg (xa ) ≡ a logg x (mod ϕ(n)) dla x, a ∈ Z, (e) dla dowolnych liczb x1 , x2 ∈ Z, logg x1 ≡ logg x2 (mod ϕ(n)) wtedy i tylko wtedy, gdy x1 ≡ x2 (mod n). Dowód.

g 0 = 1 oraz g 1 = g , wi¦c wªasno±ci (a) oraz (b) s¡ oczywiste. Aby udowodni¢ punkt (c), zapiszmy logg (x1 x2 ) ≡ y (mod ϕ(n)). Woy bec (14.1), oznacza to, »e g ≡ x1 x2 (mod n). Poniewa» g jest pierwiastkiem pierwotnym modulo n, istniej¡ liczby y1 oraz y2 , takie »e Poniewa»

g y1 ≡ x1

(mod n)

oraz

g y2 ≡ x2

(mod n).

y y Mno»¡c te kongruencje stronami otrzymujemy g 1 g 2 ≡ x1 x2 (mod n), czyli g y1 +y2 ≡ g y1 g y2 ≡ g y (mod n). Z Twierdzenia Eulera mamy y1 + y2 ≡ y

(mod ϕ(n)), Wªasno±¢

co nale»aªo pokaza¢.

(d)

udowadniamy najpierw dla nieujemnych

Indukcji Matematycznej. Dalej, z punktów

(a)

oraz

(c),

0 = logg 1 ≡ logg (xx−1 ) ≡ logg x + logg x−1

a

stosuj¡c Zasad¦

mamy

(mod ϕ(n)).

Z powy»szej kongruencji wynika bezpo±rednio przystawanie

logg x−1 ≡ − logg x (mod n). Dla dowolnej warto±ci ujemnej dla

a>0

i zast¡pienie

x

Aby udowodni¢ cz¦±¢ cz¦±ci

(c) i (d)

przez

(e)

a dowód wynika przez x−1 oraz a przez −a.

zastosowanie wyniku

twierdzenia, zauwa»my »e z udowodnionych ju»

wynika

0 = logg 1 ≡ logg x1 − logg x2 ≡ logg (x1 x−1 2 )

(mod ϕ(n)).

Wobec (14.1) powy»sza kongruencja jest równowa»na

g 0 = 1 ≡ x1 x−1 2 która jest równowa»na kongruencji

(mod n),

x1 ≡ x2 (mod n).

W nast¦pnych przykªadach podamy pewne zastosowania logarytmu dyskretnego.

61

14.3 Przykªad. kªadnicz¡

n = 17 oraz g = 3. 7 ≡ 4 (mod 17). Mamy kolejno Niech

7x ≡ log3 7x ≡ x log3 7 ≡ 11x ≡ x≡ Zatem

x = 4 + 16k ,

14.4 Przykªad.

gdzie

4 log3 4 log3 4 12 4

k∈Z

(mod (mod (mod (mod (mod

17) 16) 16) 16) 16).

jest rozwi¡zaniem naszej kongruencji.

n = 17 oraz g = 3, przy czym tym 8k ≡ 3 (mod 17). Przykªadaj¡c obustronnie

Ponownie rozwa»ymy 5

razem rozwa»ymy kongruencj¦

log3

Rozwi¡»emy kongruencj¦ wy-

x

mamy

log3 8k 5 log3 8 + 5 log3 k 5 log3 k log3 k k Ostatecznie

k = 10 + 17n,

gdzie

≡ ≡ ≡ ≡ ≡

log3 3 1 −9 11 311 ≡ 10

(mod (mod (mod (mod (mod

16) 16) 16) 16) 17).

n ∈ Z jest rozwi¡zaniem naszej kongruencji.

algorytm Shanksa na obliczenie logarytmu dyskretnego modulo liczba pierwsza p. Dokªadnie, liczby g oraz x s¡ znane (g jest pierwiastkiem pierwotnym), a chcemy obliczy¢ y = logg x. Zapiszmy y = mq + r dla pewnej ustalonej liczby m. Mamy Na zako«czenie tego wykªadu, podamy

g mq+r ≡ x (mod p),

czyli

g mq ≡ xg −r

(mod p).

m i odpowiadaj¡cych im g mq −r dla 0 ≤ q ≤ m − 1 oraz warto±ci r i odpowiadaj¡cych im yg dla 0 ≤ r ≤ mq −r m − 1. Teraz szukamy q oraz r, dla których g ≡ xg (mod p).

W nast¦pnym kroku tworzymy tablic¦ warto±ci

14.5√Przykªad. 6≈

37 − 1

Obliczymy

log2 22

p = 37.

Ustalamy liczb¦

m=

0

1

2

3

4

5

22

11

24

12

6

3

i tworzymy tabele.

q

0

1

2

3

4

5

6q

1

27

26

36

10

11

2

modulo

r 22 · 19r

Zauwa»amy liczb¦ 11, która jako jedyna powtarza si¦ w dolnym wierszu tabeli. Bierzemy liczby znad 11 i otrzymujemy

62

x = 6 · 5 + 1 = 31.

Wykªad 15 Pewne zastosowania pierwiastków pierwotnych Poka»emy tutaj, jaka jest posta¢ liczb Carmichaela oraz »e nie ma liczb ,,silnie Carmichaela.

Potrzebne nam b¦d¡ do tego trzy twierdzenia pomocnicze,

z których dwa b¦d¡ mówi¢ o postaci liczb Carmichaela.

15.1 Lemat. witej.

Liczba Carmichaela nie dzieli si¦ przez kwadrat liczby caªko-

Dowód. Niech n b¦dzie liczb¡ Carmichaela i niech p2 | n. Zatem dla dowolnej n−1 liczby a wzgl¦dnie pierwszej z n mamy a ≡ 1 (mod p2 ). Z Twierdzenia p(p−1) Eulera, mamy te» a ≡ 1 (mod p2 ). Zatem dla d = NWD(n − 1, p(p − 1)) d 2 zachodzi kongruencja a ≡ 1 (mod p ). Ale poniewa» p - n−1, wi¦c d | p−1, a st¡d

ap−1 ≡ 1 dla dowolnej liczby

(a, n) = 1

NWD

(mod p2 )

a wzgl¦dnie pierwszej z n.

(15.1)

Rozwa»my

oraz

(p + 1)

p−1

=

 p−1  X p−1 j=0

j

pj

≡1−p 6≡ 1 (mod p2 ), co przeczy (15.1).

63

a = p+1.

Wówczas

Z powy»szego lematu wynika, »e ka»da liczba Carmichaela jest postaci

p1 p2 . . . pk ,

gdzie

p1 , p2 , . . . p k

s¡ ró»nymi liczbami pierwszymi.

15.2 Twierdzenie. Liczba n jest liczb¡ Carmichaela wtedy i tylko wtedy, gdy p − 1 | n − 1 dla ka»dego dzielnika pierwszego p liczby n. Dowód. liczby a

Zaªó»my, »e

n

jest liczb¡ Carmichaela. Oznacza to, »e dla dowolnej n zachodzi an−1 ≡ 1 (mod n). Niech p b¦dzie n−1 dzielnikiem pierwszym liczby n. Przypu±¢my, »e p | n. Wówczas a ≡1 wzgl¦dnie pierwszej z

(mod p).

g b¦dzie pierwiastkiem pierwotnym modulo p. Dobierzmy b n tak, aby b ≡ g (mod p) oraz b ≡ 1 (mod ). Taka liczba b istnieje z CTR p i jest jednoznaczna modulo n. Poniewa» p - b oraz »aden inny dzielnik n n−1 nie dzieli b, wi¦c NWD(b, n) = 1. Skoro n jest liczb¡ Carmichaela, b ≡1 (mod n). Z MTF i z faktu, »e b przystaje do g modulo p mamy ordp b = p−1, zatem p − 1 | n − 1. Odwrotnie, niech a b¦dzie liczb¡ wzgl¦dnie pierwsz¡ z n i niech p b¦dzie dzielnikiem pierwszym liczby n. Poniewa» p − 1 | n − 1, wi¦c istnieje k , taka n−1 »e (p − 1)k = n − 1. Zatem a = (ap−1 )k ≡ 1 (mod p). Bior¡c pod uwag¦ ka»d¡ liczb¦ pierwsz¡, która dzieli n oraz poprzedni lemat, otrzymujemy an−1 ≡ 1 (mod n). Niech

Niech

n

b¦dzie liczb¡ Carmichaela. Z denicji liczb Carmichaela wynika,

»e nie jest to liczba pierwsza. (ró»nych) liczb pierwszych, to

Zauwa»my, »e je±li

n

n = pq ,

dla dowolnych

nie mo»e by¢ liczb¡ Carmichaela. Istotnie,

p − 1 byªoby dzielnikiem liczby n − 1 = q(p − 1) + q − 1. p − 1 | q − 1. Podobnie zauwa»amy, »e q − 1 | p − 1. mamy p − 1 = q − 1, czyli p = q , a to ju» jest sprzeczno±¢ z

gdyby tak byªo, to

Ale to oznacza, »e Ostatecznie

lematem 15.1. Zatem ka»da liczba Carmichaela jest iloczynem przynajmniej trzech ró»nych liczb pierwszych.

15.3 Lemat.

Przypu±¢my, »e n jest nieparzyst¡ liczb¡ Carmichaela oraz n − 1 = 2 s, gdzie s jest liczb¡ nieparzyst¡ oraz r > 0. Wówczas istnieje co najwy»ej n2 liczb w modulo n, które speªniaj¡ któr¡kolwiek z kongruencji r

ws ≡ 1 w Dowód.

2i s

≡ −1

(mod n)

(15.2)

dla 0 ≤ i ≤ r.

(mod n)

n = p1 p2 . . . pk oraz pj − 1 = 2rj sj , gdzie sj -ty s¡ liczbami rj > 0 oraz 1 ≤ j ≤ k . Z twierdzenia 15.2 oraz z faktu, »e

Zapiszmy

nieparzystymi,

(15.3)

64

(p1 − 1)(p2 − 1) . . . (pk − 1) < n − 1, 2r1 +r2 +···+rk | 2r

mamy oraz

s1 s2 . . . sk < s.

ws ≡ 1 (mod pj ). Z twierdzenia 7.3, ma ona dokªadnie sj = NWD(s, pj − 1) rozwi¡za«. Z Chi«skiego Twierdzenia o Resztach s dostajemy wi¦c, »e kongruencja w ≡ 1 (mod n), która si¦ sprowadza do s ukªadu k kongruencji w ≡ 1 (mod pj ) ma dokªadnie s1 s2 . . . sk rozwi¡za«. Ustalmy teraz i i policzmy rozwi¡zania kongruencji (15.3). W tym celu Rozwa»my kongruencj¦

rozwa»ymy kongruencj¦ i

w2 s ≡ −1 Zauwa»my, »e z MTF wynika, »e

i < rj

(mod pj ).

(15.4)

dla dowolnego

j.

Oznaczmy

m = min {r1 , r2 , . . . , rk } . Mamy i < m. Z twierdzenia 7.3 dostajemy, »e kongruencja (15.4) ma dokªadi i nie 2 sj = NWD(2 s, pj − 1) rozwi¡za«. Z Chi«skiego Twierdzenia o Resztach, ki mamy, »e (15.3) ma 2 s1 s2 . . . sk rozwi¡za«.

w, które mog¡ Dla k ≥ 3 mamy:

Oszacujmy teraz liczb¦ tych z kongruencji (15.2), (15.3).

s1 s2 . . . sk +

m−1 X

speªnia¢ przynajmniej jedn¡



ki

2 s1 s2 . . . sk = s1 s2 . . . sk

i=0

2km − 1 1+ k 2 −1

2k − 2 + 2km 2k − 1 2 · 2r1 +r2 +···+rk ≤ s1 s2 . . . sk 2k − 1 n ≤ , 2



= s1 s2 . . . sk

a dla

k =2

szacujemy w (15.5)

22 − 2 ≤ 2r1 +r2 −1

(15.5)

podobnie otrzymuj¡c na

n ko«cu . 2

15.4 Twierdzenie. przy co najwy»ej

n 2

Nieparzysta liczba zªo»ona n jest silnie pseudopierwsza podstawach jednocze±nie.

Dowód.

n−1 Przypu±¢my, »e istnieje taka liczba a, »e a 6≡ 1 (mod n). Wówn−1 czas ka»dej liczbie b takiej, »e b ≡ 1 (mod n) odpowiada liczba ab, taka 65

(ab)n−1 6≡ 1 (mod n). wie a, to znajdziemy co »e

Zatem je±li n nie jest pseudopierwsza przy podstan podstaw, przy których n nie jest silnie najmniej 2

pseudopierwsza. Zaªó»my wi¦c, »e dla dowolnego pseudopierwsza przy podstawie Z lematu 15.1 wynika, »e

n

a.

a

wzgl¦dnie pierwszego z

Oznacza to, »e

n

n,

liczba

n

jest

jest liczb¡ Carmichaela.

jest iloczynem ró»nych liczb pierwszych, a z

twierdzenia 15.2 dostajemy, »e dla ka»dej z tych liczb pierwszych

p−1 | n−1.

Teza twierdzenia wynika bezpo±rednio z lematu 15.3.

n n mo»na poprawi¢ do . 2 4 Potraktujmy ten fakt jednak tylko jako ciekawostk¦ przyrodnicz¡. Jak pokazaª M.O. Rabin w 1980 roku, liczb¦

66