Wst

,

ep.

Prowadzone przez wieki prace nad wÃlasno´sciami liczb i nieco p´o´zniej rozpocz

,

ete poszuki-

wania rozwi

,

aza´

n r´owna´

n wielomianowych pozwoliÃly zauwa˙zy´c wiele analogii pomi

,

edzy

wÃlasno´sciami r´o˙znych na poz´or obiekt´ow matematycznych. W gr

,

e wchodziÃly wszak poj

,

ecia

o wydawaÃloby si

,

e caÃlkiem odmiennej naturze, a jednak w kluczowych sytuacjach zachowy-

waÃly si

,

e one bardzo podobnie. SprawiÃlo to, ˙ze matematycy, zwÃlaszcza w XIX wieku podj

,

eli

pr´oby ustalenia pewnej aksjomatyki, kt´ora pozwoliÃlaby na peÃlne zrozumienie podstaw tych
analogii. OkazaÃlo si

,

e w´owczas, ˙ze obiekty te posiadaj

,

a t

,

e sam

,

a ”struktur

,

e” algebraiczn

,

a-

dzi´s kojarzon

,

a ze struktur

,

a grupy, przestrzeni wektorowej, pier´scienia, moduÃlu itp.

Wychodz

,

ac od konkretnych przykÃlad´ow warto wi

,

ec w tej sytuacji bada´c wÃlasno´sci

tych˙ze og´olniejszych struktur i na ich podstawie wyci

,

aga´c wsp´olne tym obiektom wnioski.

W´owczas uciekaj

,

ac od ogranicze´

n jakie narzuca szczeg´olna sytuacja, kt´ore cz

,

esto maskuj

,

a

cz

,

e´s´c prawdy, wÃlasno´sci udowodnione og´olnie mo˙zemy wykorzystywa´c charakteryzuj

,

ac zna-

ne wcze´sniej przykÃlady. W ten spos´ob stykamy si

,

e ni mniej ni wi

,

ecej tylko z algebr

,

a

abstrakcyjn

,

a.

Podstawowe poj

,

ecia, jakie pojawi

,

a si

,

e na tym wykÃladzie to poj

,

ecia grupy i pier´scienia.

B

,

ed

,

a to struktury algebraiczne, kt´orych definicja oparta zostanie na wÃlasno´sciach znanych

nam z teorii liczb - wÃlasno´sciach liczb caÃlkowitych, z kt´orymi spotkamy si

,

e w pierwszej

cz

,

e´sci wykÃladu: ”Elementy teorii liczb”. Ta cz

,

e´s´c wprowadzona zostaÃla, aby pokaza´c w

jaki spos´ob ”abstrakcyjne” i trudne cz

,

esto do zrozumienia ”na sucho” poj

,

ecia i wÃlasno´sci

wyrastaj

,

a ze znanych nam przykÃlad´ow. Cho´c historycznie rzecz bior

,

ac korzenie poj

,

ecia

grupy tkwi

,

a raczej w analizie wÃlasno´sci takich obiekt´ow jak permutacje i pierwiastki

wielomian´ow, to jednak start od poj

,

e´c teorioliczbowych jest uzasadniony przez mocne

przenikanie si

,

e teorii liczb z algebr

,

a. Cz

,

e´s´c wÃlasno´sci i definicji b

,

edzie tu dla nas stanowiÃlo

powt´orzenie poj

,

e´c poznanych na wykÃladzie z arytmetyki.

Druga cz

,

e´s´c wykÃladu b

,

edzie po´swi

,

econa poj

,

eciu grupy. PojawiÃlo si

,

e ono w trakcie

bada´

n prowadzonych nad r´ownaniami algebraicznymi, czyli r´ownaniami danymi za pomoc

,

a

wielomian´ow. To wÃla´snie poj

,

ecie grupy przyniosÃlo ostateczn

,

a odpowied´z na pytanie o

mo˙zliwo´s´c uzyskania og´olnych wzor´ow na pierwiastki wielomian´ow stopnia wy˙zszego ni˙z
cztery.

Wprowadzenie poj

,

ecia grupy do geometrii stan

,

eÃlo u podstaw niezwykle pÃlodnego roz-

woju poj

,

e´c geometrycznych, radykalnie zmieniaj

,

ac zasadnicze spojrzenie na t

,

e jak˙ze gÃl

,

ebo-

ko zakorzenion

,

a w pocz

,

atkach naszych dziej´ow dziedzin

,

e. Z pocz

,

atku grupy interweniowaÃly

w postaci grup przeksztaÃlce´

n przestrzeni euklidesowej, dostarczaj

,

ac nowych narz

,

edzi do

badania wÃlasno´sci figur klasycznych. Z czasem odgrywaÃly one coraz wi

,

eksz

,

a rol

,

e w ge-

ometrii, w ko´

ncu z narz

,

edzia staj

,

ac si

,

e sercem bada´

n obiekt´ow geometrycznych. Aktual-

nie, nie tylko w geometrii euklidesowej jedn

,

a z podstawowych metod bada´

n jest badanie

poj

,

e´c i wÃlasno´sci, kt´ore pozostaj

,

a niezmiennicze wzgl

,

edem zadanej grupy przeksztaÃlce´

n.

W pewnym sensie wi

,

ec tak˙ze na wsp´oÃlczesn

,

a geometri

,

e mo˙zna spojrze´c jak na odgaÃl

,

ezienie

teorii grup.

Nie nale˙zy zapomina´c m´owi

,

ac o grupach, ˙ze s

,

a one nie tylko narz

,

edziem dla ogrom-

nej cz

,

e´sci prowadzonych aktualnie bada´

n matematycznych, s

,

a te˙z dobrze znane w innych

dziedzinach nauki. Ta wÃla´snie struktura algebraiczna odgrywa bardzo wa˙zn

,

a rol

,

e w roz-

woju mechaniki, w chemii, biologii, lingwistyce i psychologii.

2

Pocz

,

atki bada´

n wÃlasno´sci liczb caÃlkowitych si

,

egaj

,

a najdalszej staro˙zytno´sci, ale to ba-

danie wÃlasno´sci tak zwanych liczb algebraicznych, kt´ore pojawiÃly si

,

e w XIX wieku do-

prowadziÃlo do powstania takich poj

,

e´c jak pier´scie´

n czy ciaÃlo. Przegl

,

ad ich podstawowych

wÃlasno´sci to gÃl´owna tre´s´c trzeciej cz

,

e´sci wykÃladu.

Przypomnijmy, ˙ze badanie podzielno´sci w zbiorze liczb caÃlkowitych opiera si

,

e na nas-

t

,

epuj

,

acej ich fundamentalnej wÃlasno´sci: ka˙zda liczba caÃlkowita zapisuj

,

e si

,

e ”w jednoz-

naczny spos´ob” jako iloczyn liczb pierwszych. Podobnie jak wszystkie wa˙zne struktury
algebraiczne, struktura pier´scienia pojawia si

,

e w licznych przykÃladach, gdzie elementami

nie s

,

a ju˙z bynajmniej liczby caÃlkowite. Szczeg´olnym przypadkiem takiej sytuacji s

,

a wielo-

miany. Warto wi

,

ec pochyli´c si

,

e przez chwil

,

e nad og´olniejszym poj

,

eciem podzielno´sci, wpro-

wadzonym w strukturze pier´scienia, aby nast

,

epnie zauwa˙zy´c, i˙z posiada ona wszelkie cechy

poznane wcze´sniej w tej pierwszej napotkanej sytuacji. W ten spos´ob dojdziemy te˙z krok
po kroku do og´olnego odpowiednika rozkÃladu na liczby pierwsze znanego pod hasÃlem:
”rozkÃladu elementu pier´scienia na iloczyn element´ow nierozkÃladalnych”.

Zasadnicz

,

a ide

,

a, zwi

,

azan

,

a z poj

,

eciem rozkÃladu jest wprowadzenie poj

,

ecia ideaÃlu: poj

,

ecie

to pozwala uog´olni´c wÃlasno´sci podzielno´sci z liczb caÃlkowitych na struktur

,

e pier´scienia.

W szczeg´olno´sci uog´olnienie na ideaÃly poj

,

ecia ”rozkÃladu na czynniki nierozkÃladalne” w

poÃl

,

aczeniu z poj

,

eciem rozszerzenia ciaÃl doprowadziÃlo do ogromnego post

,

epu w rozwoju

arytmetyki.

Podobnie jak w przypadku grup tak i w przypadku pier´scieni, nowa struktura do-

prowadziÃla do narodzin algebraicznego podej´scia do pewnych problem´ow geometrycznych,
w szczeg´olno´sci przy badaniu krzywych i powierzchni: pojawiÃla si

,

e wi

,

ec geometria alge-

braiczna. ”Algebraiczny krok” pozwoliÃl tak˙ze na wiele nowych odkry´c wyrastaj

,

acych z

analizy: grupy topologiczne, unormowane przestrzenie wektorowe, algebry Banacha.

Stopie´

n og´olno´sci poj

,

e´c grupy, pier´scienia czy ciaÃla, ogromna siÃla stosowanych tu metod i

narz

,

edzi, kt´ore one dostarczaj

,

a, ich staÃla obecno´s´c w praktycznie wszystkich zagadnieniach

matematycznych sprawiaj

,

a, ˙ze wiedza na ich temat powinna by´c wiedz

,

a fundametaln

,

a dla

wyksztaÃlcenia ka˙zdego matematyka.

3

Oznaczenia i umowy:

N := {0, 1, 2, . . . } - zbi´or liczb naturalnych, N

?

:= N \ {0}

Z - zbi´or liczb caÃlkowitych,

Z

?

:= Z \ {0},

Q - zbi´or liczb wymiernych,

Q

?

:= Q \ {0},

R - zbi´or liczb rzeczywistych,

R

?

:= R \ {0},

C - zbi´or liczb zespolonych,

C

?

:= C \ {0}.

Funkcja ”signum” jest okre´slona na R nast

,

epuj

,

aco:

sgn(a) :=











−1,

dla a < 0

0,

dla a = 0

1,

dla a > 0

Uwaga: Dla dowolnej liczby rzeczywistej mamy |a| = sgn(a) · a.

Oznaczenia:

(1) Dla liczb caÃlkowitych a, b ∈ Z takich, ˙ze b ∈ Z

?

: b|a oznacza, ˙ze b dzieli a (def.

I.1.1.),

(2) Dla liczb caÃlkowitych a

1

, . . . , a

n

∈ Z takich, ˙ze przynajmniej jedna z nich jest nieze-

rowa NWD(a

1

, . . . , a

n

) oznacza najwi

,

ekszy wsp´olny dzielnik tych liczb, (def. I.1.5.)

(3) Dla niezerowych liczb caÃlkowitych a

1

, . . . , a

n

∈ Z

?

NWW(a

1

, . . . , a

n

) oznacza naj-

mniejsz

,

a wsp´oln

,

a wielokrotno´s´c tych liczb, (def. I.1.5.)

4

I - ELEMENTY TEORII LICZB.

Bardzo wa˙znym przykÃladem i wzorem do wprowadzania kolejnych, coraz bogatszych

struktur algebraicznych b

,

edzie znany nam dobrze zbi´or liczb caÃlkowitych.

To z jego

wÃlasno´sci b

,

edziemy czerpa´c okre´slaj

,

ac nowe poj

,

ecia algebraiczne. Dlatego zaczniemy od

kilku uwag dotycz

,

acych wÃlasno´sci tego zbioru i jego struktury.

1 - Liczby caÃlkowite i ich wÃlasno´sci.

1A - Dzielenie z reszt

,

a w zbiorze liczb caÃlkowitych.

Najwa˙zniejszym poj

,

eciem zwi

,

azanym z liczbami caÃlkowitymi jest poj

,

ecie ”dzielenia” i

”podzielno´sci”. Ka˙zdy z nas wie na przykÃlad, ˙ze liczba 6 jest podzielna przez liczb

,

e 2 ale

nie jest podzielna przez liczb

,

e 5. Mo˙zna j

,

a jednak zapisa´c jako 6 = 5 · 1 + 1 czyli ”podzieli´c

z reszt

,

a”. Od tych pierwszych prostych wÃlasno´sci rozpoczniemy podr´o˙z przez kraj liczb

caÃlkowitych.

Doprecyzujmy najpierw co to znaczy, ˙ze liczba 6 jest podzielna przez liczb

,

e 2. M´owi

,

ac

inaczej mo˙zemy zapisa´c 6 = 2 · 3 czyli otrzymujemy liczb

,

e 6 jako iloczyn liczby 2 przez

inn

,

a liczb

,

e caÃlkowit

,

a. To spostrze˙zenie prowadzi nas do definicji:

Definicja 1.1. (relacja podzielno´sci) Niech a, b ∈ Z takie, ˙ze b 6= 0. M´owimy, ˙ze b
dzieli a (lub b jest dzielnikiem a), je´sli istnieje c ∈ Z: a = bc.

Oznaczenie: b|a. Kolejne wÃlasno´sci nale˙z

,

a do prostych ´cwicze´

n.

Uwagi 1.2. (1) Relacja podzielno´sci jest zwrotna i przechodnia.

(2) Je´sli b|a i a|b, to |b| = |a|

(3) Dla a, b ∈ Z

?

mamy b|a wtedy i tylko wtedy, gdy b||a|.

´

Cwiczenie 1.A. Przeprowadzi´c dow´od Uwagi 1.2.

Wracaj

,

ac do naszego przykÃladu zauwa˙zmy, ˙ze liczb

,

e 6 mo˙zemy zapisa´c w postaci 6 =

2 · 3 + 0 czyli w podobnej formie jak przy dzieleniu przez 5. Wobec tego w pewnym sensie
podzielno´s´c liczb jest szczeg´olnym przypadkiem dzielenia z reszt

,

a. Okazuje si

,

e, ˙ze w zbiorze

liczb caÃlkowitych dowolne dwie liczby mo˙zemy podzieli´c przez siebie z reszt

,

a, (oczywi´scie

je´sli przez ”dowolne” rozumiemy sytuacj

,

e, gdy nie dzielimy przez zero !!).

Ujmiemy to bardzo wa˙znym twierdzeniu, kt´ore doprowadzi nas w przyszÃlo´sci do poj

,

ecia

pier´scienia euklidesowego.

Twierdzenie 1.3. (Algorytm dzielenia z reszt

,

a w zbiorze liczb caÃlkowitych)

Z: a, b ∈ Z, b 6= 0.

T: ∃ ! (q, r) ∈ Z × Z taka, ˙ze:

(1) a = qb + r

(2) 0 6 r < |b|.

Dow´

od: Jednoznaczno´s´

c: Niech a = bq + r = bq

0

+ r

0

, gdzie (q, r), (q

0

, r

0

) speÃlniaj

,

a

tez

,

e oraz zaÃl´o˙zmy, ˙ze |q − q

0

| 6= 0 i r

0

> r.

5

Wtedy |b| 6 |b||q − q

0

| = r

0

− r < |b|, co prowadzi do sprzeczno´sci.

Istnienie: Niech T := {k|b| : k ∈ Z, k|b| 6 a}.

T 6= ∅: poniewa˙z −|a||b| 6 −|a| 6 a czyli −|a||b| ∈ T .

T jest ograniczony z g´ory przez a.

Wobec tego T posiada element najwi

,

ekszy: k

0

|b|.

Z definicji T mamy k

0

|b| 6 a, czyli r := a − k

0

|b| > 0.

Musimy sprawdzi´c, czy r < |b|. Przypu´s´cmy wobec tego, ˙ze |b| 6 r = a − k

0

|b|. Dosta-

jemy, ˙ze |b|(k

0

+ 1) 6 a co oznaczaÃloby, ˙ze |b|(k

0

+ 1) ∈ T i dostaliby´smy sprzeczno´s´c z

maksymalno´sci

,

a |b|k

0

w tym zbiorze.

Przyjmujemy teraz

q :=

½

k

0

,

gdy b > 0

−k

0

,

gdy b < 0.

¤

Wniosek 1.4. Z: a, b ∈ Z

?

takie,˙ze b nie dzieli a.

T: Istniej

,

a dokÃladnie dwie pary q

i

, r

i

) ∈ Z × Z, i = 1, 2 takie, ˙ze:

(1) a = bq

i

+ r

i

(2) |r

i

| < |b|.

´

Cwiczenie 1.B. Przeprowadzi´c dow´od Wniosku 1.4.

Jak dowiemy si

,

e o tym p´o´zniej taka wÃlasno´s´c istnienia dokÃladnie dw´och mo˙zliwych

wynik´ow i reszt z dzielenia element´ow przez siebie jest wÃlasno´sci

,

a, kt´ora wyr´o˙znia liczby

caÃlkowite spo´sr´od wszystkich takich struktur algebraicznych, w kt´orych mo˙zna m´owi´c o
takim poj

,

eciu jak dzielenie element´ow z reszt

,

a.

Mo˙zliwo´s´c wykonywania dzielenia z reszt

,

a pozwoli nam teraz na om´owienie pierwszego

algorytmu, kt´ory jest nam zapewne znany z arytmetyki: Algorytmu Euklidesa.

Zaczniemy od przypomnienia definicji znanych poj

,

e´c: NWD i NWW.

1B - Najwi

,

ekszy wsp´

olny dzielnik i najmniejsza wsp´

olna wielokrotno´s´

c.

Definicja 1.5. (NWD) Niech a

1

, . . . , a

r

∈ Z, z kt´orych przynajmniej jedna jest nieze-

rowa.

Wsp´

olnym dzielnikiem liczb a

1

, . . . , a

r

nazywamy liczb

,

e caÃlkowit

,

a, kt´ora dzieli wszys-

tkie liczby a

1

, . . . , a

r

.

Wsp´

oln

,

a wielokrotno´sci

,

a (w przypadku gdy wszystkie a

i

s

,

a niezerowe) nazywamy

liczb

,

e caÃlkowit

,

a podzieln

,

a przez ka˙zd

,

a z liczb a

1

, . . . , a

r

.

Najwi

,

ekszym wsp´

olnym dzielnikiem liczb a

1

, . . . , a

r

nazywamy nazywamy najwi

,

ek-

sz

,

a liczb

,

e caÃlkowit

,

a kt´ora dzieli wszystkie a

1

, . . . , a

r

.

Oznaczenie: NWD(a

1

, . . . , a

r

).

6

Najmniejsz

,

a wsp´

oln

,

a wielokrotno´sci

,

a niezerowych liczb a

1

, . . . , a

r

nazywamy naj-

mniejsz

,

a liczb

,

e dodatni

,

a, kt´ora jest podzielna przez ka˙zd

,

a z liczb a

1

, . . . , a

r

.

Oznaczenie: NWW(a

1

, . . . , a

r

).

Wa˙znym przypadkiem, z kt´orym cz

,

esto przyjdzie nam si

,

e spotka´c w dalszych rozwa˙za-

niach jest sytuacja, gdy najwi

,

ekszy wsp´olny dzielnik ukÃladu liczb jest r´owny jeden. Liczby

takie jak wiadomo nosz

,

a nawet specjaln

,

a nazw

,

e.

Definicja 1.6. (liczby wzgl

,

ednie pierwsze) Niech a

1

, . . . , a

r

∈ Z oraz ∃ i ∈ {1, . . . , r} :

a

i

6= 0. Je´sli NWD(a

1

, . . . , a

r

) = 1, to liczby a

1

, . . . , a

n

nazywamy wzgl

,

ednie pier-

wszymi.

Najcz

,

e´sciej obliczenia najwi

,

ekszego wsp´olnego dzielnika i najmniejszej wsp´olnej wielo-

krotno´sci wykonujemy dla dw´och liczb. Dlaczego ? Sytuacja taka nie tylko wydaje si

,

e

najprostsza ale pomaga nam w jej rozwi

,

azaniu algorytm dzielenia z reszt

,

a, o kt´orym ju˙z

m´owili´smy.

Prowadzi on bowiem do znanego sposobu wyznaczania najwi

,

ekszego wsp´olnego dziel-

nika, kt´ory najcz

,

e´sciej okre´slany jest mianem Algorytmu Euklidesa, gdy˙z zostaÃl on zapro-

ponowany przez tego wÃla´snie matematyka okoÃlo 300 roku przed nasz

,

a er

,

a.

Jak to dziaÃla ?

Algorytm Euklidesa dla liczb caÃlkowitych 1.7.

Ustalmy dwie liczby caÃlkowite a, b ∈ Z. Je´sli b = 0, to NWD(a, b) = a. Przypu´s´cmy

wi

,

ec, ˙ze b 6= 0. Przyjmijmy: r

−1

:= a, r

0

:= |b|.

Krok 1: Istniej

,

a liczby caÃlkowite q

1

, r

1

∈ Z :

(1) a = r

−1

= q

1

|b| + r

1

,

(2) 0 6 r

1

< |r

0

| = |b|.

Je´sli r

1

= 0 ko´

nczymy Algorytm. Je´sli r

1

6= 0, to

Krok 2: Istniej

,

a liczby caÃlkowite q

2

, r

2

∈ Z :

(1) r

0

= q

2

r

1

+ r

2

,

(2) 0 6 r

2

< r

1

< |r

0

| = |b|.

Je´sli r

2

= 0, to ko´

nczymy Algorytm. Je´sli r

2

6= 0, to kontynuujemy analogicznie.

Og´olnie maj

,

ac r

i−2

, r

i−1

Krok (i>1): Istniej

,

a liczby caÃlkowite q

i

, r

i

∈ Z:

(1) r

i−2

= q

i

r

i−1

+ r

i

,

(2) 0 6 r

i

< r

i−1

.

Ze wzgl

,

edu na nier´owno´sci: 0 6 r

i

< r

i−1

istnieje N ∈ N takie, ˙ze r

N +1

= 0 ale r

N

6= 0.

Liczb

,

e N ∈ N b

,

edziemy nazywa´c dalej dÃlugo´sci

,

a Algorytmu dla liczb a i b.

Jak udowodnimy za chwil

,

e w tak opisanym algorytmie r

N

jest najwi

,

ekszym wsp´olnym

dzielnikiem liczb a, b.

7

Twierdzenie 1.8. Z: a, b ∈ Z

?

, r

N

- ostatnia niezerowa reszta w Algorytmie 1.7. dla

liczb a i b gdzie N - dÃlugo´s´c Algorytmu.

T: (1) r

N

= NWD(a, b).

(2) Istniej

,

a liczby k, l ∈ Z takie, ˙ze r

N

= ka + lb.

Dow´

od: Dow´od przeprowadzimy indukcyjnie wzgl

,

edem ilo´sci krok´ow w Algorytmie,

czyli wzgl

,

edem N .

Sprawd´zmy najpierw dwie pierwsze sytuacje: N = 0 oraz N = 1.

Je´sli N = 0, oznacza to, ˙ze liczba |b| dzieli a czyli r

0

= |b| jest najwi

,

ekszym wsp´olnym

dzielnikiem obu liczb i oczywi´scie przyjmuj

,

ac NWD(a, b) = |b| = 0·a+sgn(b)b i otrzymamy

drug

,

a cz

,

e´s´c tezy.

Je´sli N = 1, to a = |b|q

1

+ r

1

oraz |b| = r

1

q

2

+ 0 co oznacza, ˙ze r

1

|b oraz z pierwszego

r´ownania wtedy te˙z r

1

|a - jest to wi

,

ec ich wsp´olny dzielnik. Je´sli za´s teraz jaka´s liczba

d > 0 dzieli a oraz b to na podstawie pierwszej z r´owno´sci dzieli te˙z r

1

czyli d 6 r

1

, sk

,

ad

otrzymujemy, ˙ze r

1

= NWD(a, b).

Mamy te˙z r

1

= a − |b|q

1

= a − sgn(b)bq

1

czyli (2).

Niech teraz N > 1 oraz teza zachodzi dla liczb, dla kt´orych Algorytm 1.7. ko´

nczy si

,

e

po N − 1 krokach.

Pierwszy krok Algorytmu prowadzi do r´owno´sci a = |b|q

1

+ r

1

. Zauwa˙zmy, ˙ze dalsza

cz

,

e´s´c tego Algorytmu dla liczb a i b jest dokÃladnie zÃlo˙zona z krok´ow Algorytmu dla liczb

|b| i r

1

. Wobec tego wiemy, ˙ze dla liczb |b| i r

1

Algorytm ko´

nczy si

,

e po N − 1 krokach i jego

efektem jest liczba r

N

, sk

,

ad z zaÃlo˙zenia indukcyjnego otrzymujemy, ˙ze r

N

= NWD(|b|, r

1

)

oraz istniej

,

a liczby k

1

, l

1

caÃlkowite takie, ˙ze r

N

= k

1

|b| + l

1

r

1

.

Skoro r

N

= NWD(|b|, r

1

), to r

N

|b oraz r

N

|r

1

co w poÃl

,

aczeniu z pierwszym krokiem daje,

˙ze r

N

|a - jest to wi

,

ec wsp´olny podzielnik a i b. Ponownie je´sli jaka´s liczba d > 0 dzieli a i

dzieli b, to z pierwszego kroku dzieli ona tak˙ze r

1

, wobec tego musi by´c d 6 r

N

, co ko´

nczy

dow´od (1).

Dla (2) wystarczy wyliczy´c: r

N

= k

1

|b| + l

1

(a − |b|q

1

) = l

1

a + sgn(b)(k

1

− l

1

q

1

)b. ¤

Widzimy, ˙ze algorytm dostarcza bardzo prostej ”maszynki” do wyliczenia najwi

,

ekszego

wsp´olnego dzielnika dla dw´och liczb.

Kolejne twierdzenie nosi zwyczajowo nazw

,

e ”identyczno´sci Bezouta” od nazwiska fran-

cuskiego matematyka, (1730-1783). Etienne Bezout zasÃlyn

,

aÃl najpierw jako autor podr

,

eczni-

k´ow matematyki dla wojskowych. Jednak do dzi´s jego nazwisko wi

,

a˙ze si

,

e przede wszystkim

z problemami rozwi

,

azywania r´owna´

n algebraicznych. Bezout znany byÃl jako matematyk

stosuj

,

acy ”metod

,

a upraszczania zaÃlo˙ze´

n”, kt´ora sprowadzaÃla si

,

e do rozwi

,

azywania szeregu

szczeg´olnych przypadk´ow twierdzenia by w ko´

ncu osi

,

agn

,

a´c og´olny rezultat.

8

Wi

,

ekszo´s´c wynik´ow jakie uzyskaÃl w teorii r´owna´

n zostaÃla zebrana w dziele ”Th´eorie

g´en´erale des ´equations alg´ebriques”, kt´ore zostaÃlo opublikowane w 1779 roku. Tam zawarte
jest znane twierdzenie Bezouta z geometrii algebraicznej do tej pory fundamentalny rezultat
tej dziedziny. Twierdzenie to wi

,

a˙ze wÃlasno´sci rozwi

,

aza´

n ukÃladu r´owna´

n algebraicznych z

iloczynem stopni wielomian´ow wyst

,

epuj

,

acych w takim ukÃladzie.

Poni˙zsza ”identyczno´s´c Bezouta” tak naprawd

,

e udowodniona zostaÃla przez innego ma-

tematyka francuskiego Bachet de M´eziriac w XVII wieku.

Twierdzenie 1.9. (identyczno´s´

c Bezouta) Z: a

1

, . . . , a

n

∈ Z, oraz istnieje i ∈

{1, . . . , n}: a

i

6= 0.

T: Istniej

,

a liczby k

1

, . . . , k

n

∈ Z:

NWD(a

1

, . . . , a

n

) = k

1

a

1

+ . . . + k

n

a

n

.

Dow´

od: Indukcja wzgl

,

edem n. Dla n = 1 mamy do czynienia z trywialn

,

a sytuacj

,

a, za´s

w przypadku n = 2 to˙zsamo´s´c ta to nic innego jak druga cz

,

e´s´c tezy 1.8.

Przypu´s´cmy wi

,

ec, ˙ze n > 2 i twierdzenie mamy udowodnione dla mniejszej ni˙z n ilo´sci

liczb.

Wprowad´zmy nast

,

epuj

,

ace oznaczenia:

d

0

:= NWD(a

1

, . . . , a

n−1

) > 0,

d := NWD(NWD(a

1

, . . . , a

n−1

), a

n

) > 0.

Zgodnie z zaÃlo˙zeniem indukcyjnym wiemy, ˙ze istniej

,

a l

1

, . . . , l

n−1

, k, l ∈ Z takie, ˙ze

(?) d

0

= l

1

a

1

+ . . . , +l

n−1

a

n−1

,

d = kd

0

+ la

n

.

Udowodnimy, ˙ze d jest najwi

,

ekszym wsp´olnym dzielnikiem liczb a

1

, . . . , a

n

.

Z definicji wynika, ˙ze d dzieli d

0

oraz a

n

. Poniewa˙z d

0

dzieli ka˙zde a

i

dla i = 1, . . . , n−1,

z przechodnio´sci relacji d jest wsp´olnym dzielnikiem wszystkich liczb a

1

, . . . , a

n

.

Z drugiej strony je´sli ˜

d > 0 jest wsp´olnym dzielnikiem a

1

, . . . , a

n

, to z (?) mamy, ˙ze ˜

d|d

0

a tym samym dzieli d. Oznacza to, ˙ze ˜

d 6 d i wobec tego d =NWD(a

1

, . . . , a

n

).

Jednocze´snie dzi

,

eki (?) wiemy, ˙ze d = kd

0

+ la

n

= k(l

1

a

1

+ . . . + l

n−1

a

n−1

) + la

n

i

przyjmuj

,

ac k

i

:= kl

i

dla i = 1, . . . , n − 1 i k

n

:= l mamy tez

,

e. ¤

Twierdzenie 1.9. mo˙zna dowodzi´c r´ownie˙z nie odwoÃluj

,

ac si

,

e do Algorytmu dzielenia z

reszt

,

a. Dow´od taki poznamy w ramach ´cwicze´

n.

Wniosek 1.10. Z: a

1

, . . . , a

r

∈ Z takie, ˙ze ∃ i ∈ {1, . . . , r} : a

i

6= 0.

T: Liczby a

1

, . . . , a

r

s

,

a wzgl

,

ednie pierwsze wtedy i tylko wtedy, gdy istniej

,

a liczby

caÃlkowite k

1

, . . . , k

r

takie, ˙ze:

(?)

1 = k

1

a

1

+ . . . + k

r

a

r

.

Dow´

od: Je´sli a

1

, . . . , a

r

s

,

a wzgl

,

ednie pierwsze to istnienie k

1

, . . . , k

r

wynika z Tw. 1.9.

Z drugiej strony je´sli istniej

,

a k

1

, . . . , k

r

speÃlniaj

,

ace (?), to ka˙zdy wsp´olny dzielnik liczb

a

1

, . . . , a

r

musi dzieli´c jedynk

,

e wobec tego liczby te s

,

a wzgl

,

ednie pierwsze. ¤

9

2 - O liczbach pierwszych i ich wÃlasno´sciach.

Zacznijmy od przypomnienia definicji liczby pierwszej.

2A - Poj

,

ecie liczby pierwszej.

Definicja 2.1. (liczba pierwsza) Liczb

,

e caÃlkowit

,

a p ∈ Z nazywamy liczb

,

a pierwsz

,

a

je´sli

(1) p > 1 oraz (2) d|p, d > 0 =⇒ d = 1 lub d = p.

Zbi´or wszystkich liczb pierwszych oznaczamy dalej przez P.

Ka˙zd

,

a liczb

,

e naturaln

,

a wi

,

eksz

,

a od jedynki, nie b

,

ed

,

ac

,

a liczb

,

a pierwsz

,

a nazywamy liczb

,

a

zÃlo˙zon

,

a.

Pami

,

etajmy dalej o umowie, i˙z liczba jeden nie jest ani liczb

,

a pierwsz

,

a ani te˙z liczb

,

a

zÃlo˙zon

,

a.

Uwaga 2.2. Je´sli p ∈ P, k ∈ Z, to NWD(p, k) = 1 lub NWD(p, k) = p.

Kolejna wÃlasno´s´c to bardzo przydatny fakt w praktycznym wykorzystaniu liczb pier-

wszych. Po raz pierwszy zastosujemy tutaj identyczno´s´c Bezouta. WÃlasno´s´c bardzo niepo-
zorna a jak zobaczymy niezmiernie wa˙zna przy badaniu r´o˙znego typu przykÃlad´ow.

WÃlasno´s´

c 2.3. Z: p ∈ P, k, l ∈ Z, p|kl.

T: p|k lub p|l.

´

Cwiczenie 3.A. Przeprowadzi´c dow´od WÃlasno´sci 2.3.

Zauwa˙zmy, ˙ze je´sli dana liczba nie jest liczb

,

a pierwsz

,

a, to taka wÃlasno´s´c wcale nie musi

zachodzi´c. Na przykÃlad warto spojrze´c na liczb

,

e 12, kt´ora dzieli 24 = 4 · 6 ale nie dzieli

ani 4 ani 6. Jak si

,

e przekonamy wÃlasno´s´c 2.3 tak naprawd

,

e ma charakter r´ownowa˙zno´sci.

Zanim jednak rozwa˙zymy inne przydatne wÃlasno´sci liczb pierwszych udowodnimy jedno z
podstawowych twierdze´

n arytmetyki.

2B - Zasadnicze Twierdzenie Arytmetyki.

Lemat 2.4. Ka˙zda liczba caÃlkowita wi

,

eksza od jedynki jest liczb

,

a pierwsz

,

a lub sko´

nczonym

iloczynem liczb pierwszych.

Dow´

od: Indukcja: Dla n = 2 teza jest speÃlniona.

ZaÃl´o˙zmy tez

,

e dla liczb naturalnych m takich, ˙ze 1 < m < n.

Je´sli n jest liczb

,

a pierwsz

,

a to mamy tez

,

e.

Je´sli n nie jest liczb

,

a pierwsz

,

a, to n = ab, gdzie 1 < a < n i 1 < b < n wobec tego z

zaÃlo˙zenia indukcyjnego a i b s

,

a sko´

nczonymi iloczynami liczb pierwszych. St

,

ad r´ownie˙z n

ma t

,

e wÃlasno´s´c. ¤

Definicja 2.5. (jedno´s´

c ) Jedno´sciami w Z nazywamy liczby −1 i 1. Zbi´or jedno´sci

w Z b

,

edziemy oznacza´c przez U (Z) := {−1, 1}.

10

Definicja 2.6. (rozkÃlad jednoznaczny) Niech k ∈ Z

?

. M´owimy, ˙ze k posiada jednoz-

naczny rozkÃlad na iloczyn liczb pierwszych je´sli

(1) istniej

,

a p

1

, . . . , p

r

∈ P, u ∈ U (Z) takie, ˙ze k = u · p

1

· . . . · p

r

.

(2) dla dowolnych dw´och ukÃlad´ow p

1

, . . . , p

r

∈ P, q

1

, . . . , q

s

∈ P, u, v ∈ U (Z) takich, ˙ze

k = u · p

1

. . . p

r

= v · q

1

. . . q

s

mamy r = s oraz istnieje σ - bijekcja zbioru {1, . . . , r} na siebie dla kt´orej zachodzi:
∀ i ∈ {1, . . . , r} p

i

= q

σ(i)

.

Maj

,

ac ju˙z wszystkie niezb

,

edne narz

,

edzia mo˙zemy sformuÃlowa´c Zasadnicze Twierdzenie

Arytmetyki.

Twierdzenie 2.7. (Zasadnicze Twierdzenie Arytmetyki) Ka˙zda niezerowa liczba
caÃlkowita, nie b

,

ed

,

aca jedno´sci

,

a w Z posiada jednoznaczny rozkÃlad na iloczyn liczb pier-

wszych.

Dow´

od: Wystarczy oczywi´scie wykaza´c twierdzenie dla liczb naturalnych wi

,

ekszych od

jedynki.

Zgodnie z Lematem 2.4. wiemy, ˙ze ˙z

,

adany przez nas rozkÃlad istnieje, musimy jedynie

wykaza´c jego jednoznaczno´s´c. Jednoznaczno´s´c wyka˙zemy indukcyjnie.

Dla n = 2 jednoznaczno´s´c rozkÃladu jest oczywista ze wzgl

,

edu na pierwszo´s´c tej liczby.

ZakÃladaj

,

ac tez

,

e dla (n − 1) gdzie n > 1 przypu´s´cmy, ˙ze dla n, mamy dwa rozkÃlady:

n = p

1

. . . p

r

= q

1

. . . q

r

gdzie p

i

, q

j

∈ P oraz p

1

6 . . . 6 p

r

, q

1

6 . . . 6 q

s

Niech p b

,

edzie najmniejsz

,

a liczb

,

a pierwsz

,

a dziel

,

ac

,

a n. Wobec tego p dzieli p

i

dla

pewnego i, (Wn. 2.4.) sk

,

ad p = p

i

czyli z minimalno´sci p mamy p = p

1

, analogicznie

p = q

1

.

Niech teraz m :=

n

p

< n. Wobec tego mamy rozkÃlad:

m = p

2

. . . p

r

= q

2

. . . q

s

.

Z zaÃlo˙zenia indukcyjnego otrzymujemy r = s i ∀ i ∈ {2, . . . , r} istnieje j ∈ {2, . . . , r}

takie, ˙ze p

i

= q

j

. ¤

Twierdzenie 2.8. (Euklides) Istnieje niesko´

nczenie wiele liczb pierwszych.

Dow´

od: Przypu´s´cmy dla dowodu niewprost, ˙ze P = {p

1

, . . . , p

r

}.

Przyjmijmy m := p

1

. . . p

r

+ 1.

˙Zadne p

i

nie dzieli liczby m, (w przeciwnym razie

dzieliÃloby jedynk

,

e). Niech p b

,

edzie liczb

,

a pierwsz

,

a dziel

,

ac

,

a m, (taka istnieje na mocy

Zasadniczego Twierdzenia Arytmetyki). Wobec tego p /

∈ P i p jest liczb

,

a pierwsz

,

a, co

prowadzi do sprzeczno´sci. ¤

Istniej

,

a r´ownie˙z inne dowody istnienia niesko´

nczonej ilo´sci liczb pierwszych, mi

,

edzy

innymi dow´od podany przez G. Polya.

W okolicach 200 p.n.e. grecki matematyk Eratosthenes wprowadziÃl metod

,

e wyznaczania

liczb pierwszych nie wi

,

ekszych od ustalonej liczby n zwan

,

a odt

,

ad ”sita Eratothenesa”.

11

Wypisujemy wszystkie liczby od 2 do n nast

,

epnie zakre´slamy 2 i wykre´slamy jej wszystkie

wielokrotno´sci. Potem zakre´slamy pierwsz

,

a pozostaÃl

,

a liczb

,

e i wykre´slamy wszystkie jej

wielokrotno´sci i tak a˙z nie ma ”nietkni

,

etych” liczb 6

√

n.

3 - Kongruencje i ich wÃlasno´sci.

3A - Relacje przystawania modulo.

Definicja 3.1. (przystawanie ’modulo’) Niech n ∈ N

?

. M´owimy, ˙ze liczby caÃlkowite

k, l przystaj

,

a modulo n je´sli n|(k − l).

Oznaczenie: k ≡ l(mod n).

Uwaga 3.2. Relacja przystawania modulo n jest relacj

,

a r´ownowa˙zno´sci w zbiorze liczb

caÃlkowitych.

Klas

,

e r´ownowa˙zno´sci liczby k ∈ Z w relacji modulo m oznaczamy [k]

m

za´s zbi´or wszys-

tkich klas r´ownowa˙zno´sci w relacji modulo m oznaczamy Z

m

.

WÃlasno´sci 3.3. Z: n ∈ N

?

, k, l, k

0

, l

0

∈ Z takie, ˙ze k ≡ k

0

(mod n) i l ≡ l

0

(mod n).

T: (1) k + l ≡ k

0

+ l

0

(mod n)

(2) kl ≡ k

0

l

0

(mod n).

´

Cwiczenie 4.A. Przypomnie´c dow´od WÃlasno´sci 3.3.

WÃlasno´sci 3.4.

(1) Je´sli k, l ∈ Z, m ∈ Z

?

takie, ˙ze m|kl oraz m i k s

,

a wzgl

,

ednie pierwsze, to m|l.

(2) Je´sli m ∈ N

?

, a, k, l ∈ Z takie, ˙ze ak ≡ al(mod m) oraz m i a s

,

a wzgl

,

ednie pierwsze,

to k ≡ l(mod m).

(3) Je´sli a

1

, . . . , a

r

∈ Z, k ∈ Z wzgl

,

ednie pierwsza z a

i

dla i = 1, . . . , r, to k jest wzgl

,

ednie

pierwsza z iloczynem a

1

· . . . · a

r

.

´

Cwiczenie 5.A. Udowodni´c WÃlasno´sci 3.4.

3B - Twierdzenie Chi´

nskie o resztach.

WÃlasno´s´

c 3.5. Z: m

1

, . . . , m

r

∈ Z

?

- parami wzgl

,

ednie pierwsze, k ∈ Z taka, ˙ze m

i

|k dla

ka˙zdego i = 1, . . . , r.

T: m

1

· . . . · m

r

|k.

Dow´

od: Zauwa˙zmy najpierw, ˙ze oczywi´scie m

1

|k i ˙zeby wykorzysta´c indukcj

,

e zaÃl´o˙zmy

teraz, ˙ze dla ustalonego 1 < i 6 r mamy m

1

·. . .·m

i−1

|k. Chcemy wykaza´c, ˙ze m

1

·. . .·m

i

|k,

(wtedy na mocy indukcji otrzymamy tez

,

e).

Skoro m

1

· . . . · m

i−1

|k, to k = m

1

· . . . · m

i−1

l dla pewnego l caÃlkowitego. Z zaÃlo˙zenia

wiemy, ˙ze m

i

jest wzgl

,

ednie pierwsze z ka˙zd

,

a z liczb m

1

, . . . , m

i−1

, czyli z WÃlasno´sci 3.4.(3)

mamy, ˙ze m

i

jest wzgl

,

ednie pierwsze z iloczynem m

1

· . . . · m

i−1

. Teraz stosuj

,

ac Lemat

3.4.(1) dostajemy, ˙ze wobec tego m

i

|l czyli iloczyn m

1

·. . .·m

i

|k co chcieli´smy otrzyma´c. ¤

12

Twierdzenie 3.6. (Chi´

nskie o resztach) Z: m

1

, . . . , m

r

∈ N

?

- parami wzgl

,

ednie

pierwsze, k

1

, . . . , k

r

∈ Z.

T: (1) Istnieje l ∈ Z takie, ˙ze l ≡ k

i

(mod m

i

) dla ka˙zdego i = 1, . . . , r.

(2) Je´sli l, l

0

speÃlniaj

,

a (1), to l ≡ l

0

(modm) gdzie m = m

1

· . . . · m

r

.

Dow´

od: Niech m := m

1

·. . .·m

r

oraz s

i

:=

m

m

i

. Wtedy s

i

jest iloczynem liczb m

j

dla j 6=

i wobec tego jest iloczynem liczb wzgl

,

ednie pierwszych z m

i

. Z WÃlasno´sci 3.4.(3) wynika,

˙ze r´ownie˙z m

i

i s

i

s

,

a wzgl

,

ednie pierwsze. Wobec tego istniej

,

a a

1

, . . . , a

r

, b

1

, . . . , b

r

∈ Z

takie, ˙ze

a

i

m

i

+ b

i

s

i

= 1 dla i = 1, . . . , r.

Okre´slmy u

i

= b

i

s

i

oraz l := k

1

u

1

+ . . . + k

r

u

r

. Wyka˙zemy, ˙ze takie wÃla´snie l speÃlnia

warunki tezy.

Ustalmy i

0

∈ {1, . . . , r}. Wtedy

l − k

i

0

= k

1

u

1

+ . . . + (u

i

0

− 1)k

i

0

+ . . . + k

r

u

r

.

Ale z okre´slenia u

i

0

= b

i

0

s

i

0

wiemy, ˙ze m

i

0

|(u

i

0

− 1) a jednocze´snie wszystkie s

i

dla i 6= i

0

s

,

a podzielne przez m

i

0

czyli l ≡ k

i

0

(mod m

i

0

), czego oczekiwali´smy.

Niech teraz l

0

speÃlnia r´ownie˙z t

,

e kongruencj

,

e, to oznacza, ˙ze l

0

− l jest podzielne przez

ka˙zde m

i

. Wobec tego z WÃlasno´sci 3.5. wynika, ˙ze l

0

− l jest podzielne przez iloczyn

m

1

. . . m

r

i mamy tez

,

e. ¤

Zauwa˙zmy przy okazji, ˙ze dow´od twierdzenia chi´

nskiego o resztach dostarcza nam konkret-

nego algorytmu znajdowania rozwi

,

azania ukÃladu kongruencji.

PrzykÃlad zastosowania Twierdzenia Chi´

nskiego o Resztach: Rozwi

,

aza´c ukÃlad

kongruencji:

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 1 (mod 7)

Poda´c rozwi

,

azanie og´olne oraz znale´z´c najmniejsz

,

a liczb

,

e naturaln

,

a b

,

ed

,

ac

,

a rozwi

,

azaniem

szczeg´olnym.
4 - Wybrane poj

,

ecia i twierdzenia teorii liczb.

4 A - Funkcja Eulera.

Definicja 4.1. (Funkcja Eulera) Niech ϕ : N

?

−→ N

?

b

,

edzie funkcj

,

a przypisuj

,

ac

,

a

liczbie n liczb

,

e liczb caÃlkowitych k ∈ [0, n) wzgl

,

ednie pierwszych z n. Funkcj

,

e ϕ nazywamy

funkcj

,

a Eulera.

WÃlasno´sci 4.2. (a) ϕ(1) = 1, (zero jest wzgl

,

ednie pierwsze z jedynk

,

a),

(b) Niech p - liczba pierwsza, wtedy ϕ(p) = p − 1 = p(1 −

1
p

), (tylko zero nie jest

wzgl

,

ednie pierwsze z p).

(c) Niech p - liczba pierwsza, k ∈ N

?

. Wtedy ϕ(p

k

) = p

k

− p

k−1

= p

k

(1 −

1
p

), gdy˙z jest

p

k−1

liczb caÃlkowitych takich, ˙ze 0 6 l < p

k

, kt´ore s

,

a podzielne przez p, za´s te kt´ore s

,

a

wzgl

,

ednie pierwsze to te, kt´ore nie s

,

a podzielne przez p.

13

Twierdzenie 4.3. (bez dowodu) Z: m

1

, m

2

∈ N

?

- wzgl

,

ednie pierwsze.

T: ϕ(m

1

m

2

) = ϕ(m

1

)ϕ(m

2

).

Dow´

od: Oznaczmy I := {k ∈ [0, m

1

) : NWD(k, m

1

) = 1},

J := {l ∈ [0, m

2

) : NWD(l, m

2

) = 1}

A := {s ∈ [0, m

1

· m

2

) : NWD(s, m

1

· m

2

) = 1}.

Wtedy oczywi´scie #(I × J) = ϕ(m

1

)ϕ(m

2

), za´s #(A) = ϕ(m

1

m

2

). Skonstruujemy

bijekcj

,

e mi

,

edzy zbiorami I × J i A.

Zgodnie z twierdzeniem chi´

nskim o resztach dla dowolnej pary liczb (k, l) ∈ I ×J istnieje

dokÃladnie jedna liczba z

k,l

taka, ˙ze 0 6 z

k,l

< m

1

m

2

oraz

z ≡ k(mod m

1

),

z ≡ l(mod m

2

).

(Jedyno´s´c wynika z ˙z

,

adania aby 0 6 z < m

1

m

2

). Liczba ta jest wzgl

,

ednie pierwsza z m

1

(bo k byÃla) oraz z m

2

(bo l byÃla) st

,

ad jest wzgl

,

ednie pierwsza z m

1

m

2

.

Mamy wi

,

ec dobrze okre´slone odwzorowanie:

Φ : I × J 3 (k, l) −→ z

k,l

∈ A.

(1) Φ jest injekcj

,

a.

Niech bowiem z

k,l

= z

k

0

,l

0

i na przykÃlad 0 6 k < k

0

< m

1

. Wtedy m

1

|(z

k,l

− k) i

m

1

|(z

k,l

− k

0

) sk

,

ad m

1

|(k

0

− k) co prowadzi do sprzeczno´sci. St

,

ad injektywno´s´c.

(2) Φ jest surjekcj

,

a.

Je´sli bowiem z ∈ A, to z = Φ(k, l) gdzie k := z(mod m

1

) za´s l := z(mod m

2

). ÃLatwo

sprawdzi´c, ˙ze (k, l) ∈ I × J.

Wobec tego ϕ(m

1

)ϕ(m

2

) = #(I) · #(J) = #(I × J) = #(A) = ϕ(m

1

m

2

). ¤

Wniosek 4.4. ϕ(n) = n

Q

p|n

p∈P

³

1 −

1
p

´

, dla dowolnego n ∈ N

?

.

Dow´

od: Niech n = p

k

1

1

. . . p

k

m

m

gdzie p

1

, . . . , p

m

- liczby pierwsze parami r´o˙zne,

k

1

, . . . , k

m

∈ N

?

. Wtedy ϕ(n) = ϕ(p

k

1

1

) . . . ϕ(p

k

m

m

) a ka˙zde ϕ(p

k

i

i

) = p

k

i

i

(1 − (

1

p

i

)), (Uwaga

4.2. (c)) co daje tez

,

e. ¤

Udowodnimy teraz wÃlasno´s´c funkcji Eulera, kt´ora wykorzystana zostanie w drugiej cz

,

e´sci

wykÃladu przy badaniu wÃlasno´sci tak zwanej grupy multiplikatywnej ciaÃla sko´

nczonego.

WÃlasno´s´

c 4.5. Z: n ∈ N

?

, ϕ - funkcja Eulera.

T:

P

d|n

ϕ(d) = n.

Dow´

od: Niech n ∈ N

?

, wtedy n = #{0, 1, . . . , n − 1}. Je´sli l ∈ {0, . . . , n − 1} to

NWD(n, l) =

n

d

dla pewnego d - dzielnika liczby n. Niech n

d

:= {x ∈ [0, n) : NWD(x, n) =

n

d

}. Wtedy wobec tego n =

P

d|n

n

d

.

14

Niech teraz x ∈ [0, n) liczba naturalna taka, ˙ze NWD(x, n) = k =

n

d

. Wtedy x = kα

gdzie α < d (bo x < n = kd). Skoro NWD(x, n) = k to NWD(α, d) = 1 czyli liczby
takie, ˙ze NWD(x, n) = k to liczby postaci kα gdzie α ∈ [0, d) oraz NWD(α, d) = 1 sk

,

ad

n

d

= ϕ(d).

ÃL

,

acz

,

ac oba fakty mamy n =

P

d|n

ϕ(d). ¤

4 B - Twierdzenia Fermata i Eulera.

Zaczniemy od sformuÃlowania i dowodu tzw. ”MaÃlego twierdzenia Fermata”.

Twierdzenie 4.6. (MaÃle Twierdzenie Fermata)

Z: p - liczba pierwsza, k ∈ Z.

T: (1) Je´sli k jest wzgl

,

ednie pierwsza z p, to k

p−1

≡ 1(mod p).

(2) k

p

≡ k(mod p).

Dow´

od: (1) Niech k ∈ Z takie, ˙ze p nie dzieli k. Ustalmy liczb

,

e j ∈ {1, . . . , p − 1}.

Dla niej oczywi´scie tak˙ze zachodzi NWD(j, p) = 1, czyli zgodnie z Lematem 3.5. mamy
NWD(kj, p) = 1.

Dla ka˙zdego ustalonego j z Algorytmu dzielenia z reszt

,

a dla Z istnieje para (q

j

, r

j

) ∈

Z × Z taka, ˙ze

(?) kj = pq

j

+ r

j

oraz 0 6 r

j

6 p − 1.

Jednak poniewa˙z kj nie jest podzielne przez p wi

,

ec na pewno 0 6= r

j

.

Zauwa˙zmy teraz, ˙ze je´sli mamy dwa r´o˙zne wska´zniki j 6= i ze zbioru {1, . . . , , p − 1}, to

odpowiadaj

,

ace im r

j

i r

i

s

,

a te˙z r´o˙zne.

Gdyby bowiem kj = pq

j

+ r i ki = pq

i

+ r, to p|k(j − i) co oznaczaÃloby, ˙ze p|k, (bo

j < p, i < p) sprzeczno´s´c.

Wobec tego mamy dokÃladnie p − 1 reszt r´o˙znych mi

,

edzy sob

,

a czyli r

1

· . . . · r

p−1

=

1 · . . . · (p − 1) = (p − 1)!.

R´ownania (?) oznaczaj

,

a, ˙ze kj ≡ r

j

(mod p), czyli mno˙z

,

ac te kongruencje stronami

dostajemy:

k

p−1

(p − 1)! ≡ (p − 1)!(mod p)

i poniewa˙z (p − 1)! jest wzgl

,

ednie pierwsze z p stosuj

,

ac Lemat 3.5. otrzymujemy k

p−1

≡

1(mod p).

(2) Maj

,

ac (1) wystarczy rozwa˙zy´c przypdek gdy p|k. Ale wtedy p|k

p

sk

,

ad oczywi´scie

k

p

≡ k(mod p). ¤

Uog´olnieniem powy˙zszej wÃlasno´sci udowodniej przez Fermata jest nast

,

epne Twierdzenie

Eulera, kt´ore wykorzystuje wprowadzone wcze´sniej poj

,

ecie funkcji Eulera.

Twierdzenie 4.7. (Euler) Z: m ∈ N

?

, k ∈ Z - wzgl

,

ednie pierwsza z m.

T: k

ϕ(m)

≡ 1(mod m).

Dow´

od: Jest to oczywiste gdy m = 1, wobec tego zaÃl´o˙zmy, ˙ze m > 1.

15

Niech I := {j ∈ [0, m) : NWD(j, m) = 1}. W´owczas #I = ϕ(m).

Je´sli j jest liczb

,

a wzgl

,

ednie pierwsz

,

a z m, to tak˙ze kj ma t

,

e wÃlasno´s´c. Wobec tego dla

ka˙zdego j ∈ I istnieje dokÃladnie jedna liczba caÃlkowita r

j

∈ I taka, ˙ze kj ≡ r

j

(mod m),

(analogicznie jak w dowodzie Twierdzenia Fermata). Co wi

,

ecej je´sli j ∈ I i i ∈ I takie, ˙ze

j 6= l, to r

j

6= r

i

. St

,

ad I = {r

j

: j ∈ I}.

Mno˙z

,

ac stronami kongruencje kj ≡ r

j

(mod m) dla wszystkich j ∈ I dostajemy:

k

ϕ(m)

z ≡ z(mod p) gdzie z jest iloczynem wszystkich liczb caÃlkowitych z I. Ale z jest

wzgl

,

ednie pierwsze z m, sk

,

ad na podstawie Lematu 3.5 mamy k

ϕ(m)

≡ 1(mod m). ¤

Koniec Element´

ow Teorii Liczb.

Do problem´ow teorioliczbowych b

,

edziemy sukcesywnie powraca´c w trakcie wykÃladu.

Chwilowo przechodzimy jednak do cz

,

e´sci po´swi

,

econej teorii grup.

Wiele ciekawych zada´

n i problem´ow z zakresu teorii liczb mo˙zna znale´z´c mi

,

edzy innymi

w ksi

,

a˙zce ”200 zada´

n z elementarnej teorii liczb” WacÃlawa Sierpi´

nskiego. Pi

,

ekn

,

a ksi

,

a˙zk

,

a

zawieraj

,

ac

,

a ogromn

,

a ilo´s´c informacji o problemach teorii liczb jest te˙z ”MaÃla ksi

,

ega wielkich

liczb pierwszych”.