Spis treści

1

Algebra liniowa

3

1.1

Podzielność . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2

Równania w zbiorze Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3

Liczby pierwsze i względnie pierwsze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.4

Funkcja Eulera i funkcja Π

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.5

Kongruencje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2

Algebra abstrakcyjna

10

2.1

Iloczyn kartezjański zbiorów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.2

Grupy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.3

Podgrupy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2.4

Grupy permutacji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.5

Homomorfizm grup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.6

Pierścienie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.7

Ciała . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.8

Homomorfizm ciał i pierścieni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

1

yyg

2

1

Algebra liniowa

1.1

Podzielność

Twierdzenie 1 (Zasada minimum)

Każdy niepusty podzbiór zbioru liczb naturalnych N zawiera liczbę najmniejszą.

Definicja 1 (Podzielności)

Liczba całkowita b ∈ Z jest podzielna przez liczbę całkowitą a 6= 0 ∈ Z wtedy i tylko wtedy, gdy istnieje
liczba całkowita k taka, że b = a · k. Piszemy wtedy a|b (czytamy: a dzieli b, a jest podzielnikiem b, b jest
podzielna przez a). a 6 | b - liczba a nie dzieli b.

Twierdzenie 2 (O podzielności liczb całkowitych)

Dla a,b,c ∈ Z i a 6= 0 mamy następujące własności:

(1) Jeśli a|b i c ∈ Z to a|b · c

(2) Jeśli a|b i b|c, to a|c (Przechodniość)

(3) Jeśli a|b i a|c to a|bx + cy, gdzie x, y ∈ Z

(4) Jeśli a|b i b|a, to a = ±b

(5) Jeśli a|b i a, b > 0, to a ¬ b

(6) Jeśli m ∈ Z i m 6= 0 i a|b to ma|mb

Dowód twierdzenia 2:

(1) Skoro a|b to istnieje k ∈ Z takie, że b = a · k. Pomnóżmy ostatnią równość stronami przez c,

wówczas:

b · c = a · k · c ⇔ b · c = a · (k · c)

Oznaczmy k · c = l ∈ Z. Zatem b · c = a · l. Z definicji wynika, że a|b · c.

(2) Skoro a|b to istnieje k

1

∈ Z takie, że b = a · k

1

. Skoro b|c to istnieje k

2

∈ Z takie, że c = b · k

2

. A

więc

c = b · k

2

= a · k

1

· k

2

Oznaczmy symbolem k liczbę k

1

· k

2

∈ Z. Wówczas c = a · k oznacza, że a|c.

(3) a|b ⇔ ∃

k

1

∈Z

b = a·k

1

i a|c ⇔ ∃

k

2

∈Z

c = a·k

2

. Zatem bx+cy = a·k

1

·x+a·k

2

·y = a(k

1

x+k

2

y) = a·l,

gdzie l = k

1

x + k

2

y ∈ Z, co oznacza, że a|bx + cy.

(4) a|b ⇔ ∃

k

1

∈Z

b = a · k

1

i b|a ⇔ ∃

k

2

∈Z

a = b · k

2

. Stąd b = k

1

· k

2

· a. Zatem k

1

= 1 ∧ k

2

= 1 lub

k

1

= −1 ∧ k

2

= −1. Stąd wniosek, że liczby a i b mogą różnić się tylko znakiem, a więc a = ±b.

(5) a|b ⇔ ∃

k∈Z

b = a · k, ale jeśli a > 0 i b > 0 to też k > 0, a więc a ¬ b.

(6) ∃

k∈Z

b = a · k. Pomnóżmy obie strony równości przez m. Wówczas mb = ma · k. Zatem ma|mb na

mocy definicji relacji podzielności.

Twierdzenie 3 (O reszcie z dzielenia dla liczb dodatnich)

Niech a, b ∈ Z, przy czym a > 0. Istnieją wówczas liczby całkowite q i r, takie, że:

b = a · q + r

gdzie 0 ¬ r < a. Jeśli a 6 | b to 0 < r < a.

3

Dowód twierdzenia 3:

Rozważmy zbiór liczb A = {. . . , b− 2a, b− a, b, b + a, b + 2a, . . .} czyli b − q · a, gdzie q ∈ Z. Na mocy zasady
minimum w zbiorze A istnieje najmniejsza liczba nie ujemna. Oznaczmy tą liczbę symbolem r. Istnieje
wówczas taka liczba q ∈ Z, że b − q · a = r. A więc A = b − q · a = r; q ∈ Z. Przypuśćmy, że istnieją liczby
q

1

i r

1

takie że

b = q

1

· a + r

1

,

gdzie 0 ¬ r

1

< a, r

1

> r

Odejmniemy stronami podkreślone równości:

0 = (q

1

− q) · a + r

1

− r,

0 ¬ r

1

− r < a

i otrzymujemy:

(1)

r

1

− r = (q − q

1

) · a

Skoro 0 ¬ r

1

− r < a to

r

1

−r

a

= q − q

1

6∈ Z. Wobec tego mamy sprzeczność, r

1

= r. Jeśli r

1

= r, to z

równości (1) mamy

0 = (q − q

1

) · a

Ponieważ a 6= 0, to q − q

1

= 0. Stad q = q

1

. Zatem przedstawienie b = a · q + r jest przedstawieniem

jednoznacznym.

Twierdzenie 4 (O reszcie z dzielenia dla liczb Z różnych od 0)

Niech a, b ∈ Z, a 6= 0 . Istnieją wówczas liczby całkowite k i r, takie że

b = k · a + r,

gdzie 0 ¬ r < |a|

Dowód twierdzenia 4:

Przypadek 1)
a > 0 to tezę mamy z twierdzenia 3. |a| = a > 0.

Przypadek 2)
a < 0 to |a| = −a. Z twierdzenia 3 mamy

b = |a| · q + r,

gdzie 0 ¬ r < |a|

Stąd b = −a · q + r, a więc prawdą jest też, że b = a · (−q) + r. Oznaczmy −q = k. Wtedy

b = a · kr,

gdzie 0 ¬ r < |a|, k ∈ Z

Gdzie r - reszta z dzielenia liczby b przez liczbę a, przy czym a, b ∈ Z, a 6= 0.

Definicja 2 (Największego wspólnego dzielnika - NWD)

Liczbę a ∈ Z − {0} nazywamy wspólnym dzielnikiem liczb całkowitych b i c, jeśli a|b i a|c. Jeśli choć
jedna z liczb b lub c jest różna od zera, to wśród wszystkich dzielników b i c (jest ich skończona liczba)
istnieje dzielnik największy. Dzielnik ten nazywamy największym wspólnym dzielnikiem liczb b i c
oraz oznaczamy (b, c).

UWAGA. Analogicznie definiuje się NWD dla liczb b

1

, b

2

, . . . , b

n

∈ Z nie wszystich jednocześnie równych

zeru.
(b

1

, b

2

, . . . , b

n

) - NWD liczb b

1

, b

2

, . . . , b

n

.

Twierdzenie 5

Jeśli (a, b) jest największym wspólnym dzielnikiem liczb całkowitych b i c to istnieją liczby całkowite x

0

i

y

0

takie, że

(b, c) = bx

0

+ cy

0

Innymi słowy NWD liczb b i c jest kombinacją liniową liczb b i c o współczynnikach całkowitych.

4

Twierdzenie 6

Największy wspólny dzielnik liczb b, c ∈ Z można scharakteryzować następująco:

1. Jest to wspólny dzielnik tych liczb, który jest podzielny przez każdy inny dzielnik liczb b i c.

2. Jest to najmniejsza liczba naturalna należąca do zbioru A = {bx + cy; x, y ∈ Z}.

Twierdzenie 7 (Algorytm Euklidesa)

Niech b, c ∈ Z, przy czym c > 0. NWD liczb b i c można obliczyć przy pomocy serii równań:

b = k

1

· c + r

1

,

gdzie 0 < r

1

< c

c = k

2

· r

1

+ r

2

,

gdzie 0 < r

2

< r

1

r

1

= k

3

· r

2

+ r

3

,

gdzie 0 < r

3

< r

2

r

2

= k

4

· r

3

+ r

4

,

gdzie 0 < r

4

< r

3

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

r

j−2

= k

j

· r

j−1

+ r

j

gdzie 0 < r

j

< r

j−1

r

j−1

= k

j+1

· r

j

+ 0

Podkreślona reszta r

j

(ostatnia niezerowa reszta) jest jednocześnie największym wspólnym dzielnikiem

liczb b i c.

Definicja 3 (Najmniejszej wspólnej wielokrotności)

Liczby całkowite a

1

, a

2

, . . . , a

n

, takie że a

i

6= 0, i ∈ {1, 2, . . . , n} posiadają wielokrotność całkowitą b jeśli

a

i

|b, i ∈ {1, 2, . . . , n}. Najmniejszą z tych wielokrotności (dodatnią) nazywamy najmniejszą wspólną

wielokrotnością liczb a

1

, a

2

, . . . , a

n

i oznaczamy symbolem:

[a

1

, a

2

, . . . , a

n

] lub N W W (a

1

, a

2

, . . . , a

n

).

Twierdzenie 8

Iloczyn największego wspólnego dzielnika liczb naturalnych a i b oraz najmniejszej wspolnej wielokrotności
tych liczb jest równy iloczynowi tych liczb:

(a, b) · [a, b] = ab;

a, b ∈ N

Twierdzenie 9

Każda wspólna wielokrotność liczb a

1

, a

2

, . . . , a

n

, a

i

6= 0, i ∈ {1, 2, . . . , n} jest podzielna przez ich naj-

mniejszą wspólną wielokrotność.

1.2

Równania w zbiorze Z

Definicja 4 (Równania diofantycznego)

Równaniem diofantycznym nazywamy takie równanie, którego rozwiązań szukamy w zbiorze liczb Z. Przy-
kłady:

ax + by = c,

a

2

+ b

2

> 0

a

1

x

1

+ a

2

x

2

+ . . . + a

n

x

n

= b

n

X

i=1

a

2
i

> 0

5

Twierdzenie 10 (Rozwiązanie równania nieoznaczonego)

Na to by równanie postaci

a

1

x

1

+ a

2

x

2

+ . . . + a

n

x

n

= b

gdzie a

i

, b ∈ Z, i ∈ {1, 2, . . . , n} oraz gdzie zachodzi warunek

n

X

i=1

a

2
i

> 0

miało rozwiązanie wystarczy, by (a

1

, a

2

, . . . , a

n

)|b.

Twierdzenie 11

Jeśli (x

0

, y

0

) jest rozwiązaniem szczególnym równania postaci ax+by = c, gdzie a, b, c ∈ Z, to rozwiązanie

ogólne tego równania ma postać:

x = x

0

+

b

(a, b)

· t

y = y

0

−

a

(a, b)

· t

1.3

Liczby pierwsze i względnie pierwsze

Definicja 5 (Liczby pierwszej)

Liczbę naturalną n > 1 nazywamy liczbą pierwszą, jeśli jedynymi jej dzielnikami naturalnymi są liczba 1
i ona sama.

Twierdzenie 12 (Zasada twierdzenia arytmetycznego)

Niech a, b, c będą liczbami naturalnymi i niech (a, b) = 1. Jeśli a|b · c, to a|c.

Dowód twierdzenia 12:

Na mocy twierdzenia (5) istnieją liczby całkowite x

0

, y

0

, takie że: (a, b) = 1 = ax

0

+ by

0

, czyli

1 = ax

0

+ by

0

| · c

c = ax

0

c + by

0

c

Liczba a|a i liczba a|bc (z założenia). Zatem a|c.

Twierdzenie 13

Każda liczba naturalna a > 1 może być przedstawiona w postaci iloczynu liczb pierwszych. Przedstawienie
to jest jednoznaczne z dokładnością do kolejnych czynników, tzn. jeśli

a = p

1

· p

2

· . . . · p

k

∧

a = q

1

· q

2

· . . . · q

l

gdzie p

1

, . . . , p

k

, q

1

, . . . , q

l

są liczbami pierwszymi, to k = l i można przedstawić czynniki w obu rozkładach,

by dla pewnego i ∈ {1, . . . , k} oraz j ∈ {1, . . . , k} było p

i

= q

j

.

Liczbę naturalną, która nie jest liczbą pierwszą, nazywamy liczbą złożoną.

Twierdzenie 14

Każda liczba złożona n ma dzielnik pierwszy mniejszy bądź równy

√

n.

Twierdzenie 15

Jeśli liczba naturalna n ­ 2 nie ma dzielnika mniejszego bądź równego

√

n to jest liczbą pierwszą.

6

1.4

Funkcja Eulera i funkcja Π

Definicja 6 (Funkcji Eulera)

Funkcję ϕ : N → N dla n ∈ N nazywamy funkcją Eulera (lub Gaussa) i definiujemy następująco:

ϕ(n) = {ilość liczb naturalnych ¬ n względnie pierwszych z n}

Z definicji (6) funkcji Eulera wynika, że:

1. ϕ(p) = p − 1, gdy p jest liczbą pierwszą.

2. Jeśli α ∈ N jest liczbą pierwszą, to:

ϕ(p

α

) = p

α−1

· (p − 1)

3. Jeśli n jest liczbą naturalną większą od 1, to:

ϕ(n) = n ·



1 −

1

p

1



·



1 −

1

p

2



· . . . ·



1 −

1

p

n



n = p

α

1

1

· p

α

2

2

· . . . · p

α

n

n

gdzie α

1

, α

2

, . . . , α

n

∈ N p

1

, p

2

, . . . , p

n

- liczby pierwsze

4. Niech a

1

, a

2

, . . . , a

n

∈ N takimi, że (a

i

, a

j

) = 1 dla i 6= j i i, j ∈ {1, 2, 3, . . . , k}. Wówczas:

ϕ(a

1

· a

2

· . . . · a

k

) = ϕ(a

1

) · ϕ(a

2

) · . . . · ϕ(a

k

)

Definicja 7 (Funkcji Π)

Funkcję tą definiuje się w następujący sposób:

Π(x) = {ilość liczb pierwszych ¬ x}

1.5

Kongruencje

Definicja 8 (Przystawania modulo m)

Powiemy, że liczby całkowite a i b przystają do siebie modulo m (gdzie m ∈ N), jeśli istnieje k ∈ Z takie,
że:

a − b = k · m

gdzie k ∈ Z

a ≡ b(mod m) ⇔ ∃

k∈Z

a − b = k · m

Przykłady:

3 ≡ −4(mod 7), gdyż 3 − (−4) = 7, a 7|7

25 ≡ 4(mod 7), gdyż 25 − 4) = 21, a 7|21

100 ≡ 1(mod 9), gdyż 100 − 1 = 99, a 9|99

100 ≡ 1(mod 11), gdyż 100 − 1 = 99, a 11|99

Twierdzenie 16 (Własności relacji przystawania)

Dla a, b, c, d ∈ Z i m ∈ N mamy następujące własności (te z * nie obowiązują na egzaminie):

(1) a ≡ a(mod m) - zwrotność relacji przystawania

7

(2) Jeśli a ≡ b(mod m) to b ≡ a(mod m) - symetria relacji przystawania.

(3) Jeśli a ≡ b(mod m) i b ≡ c(mod m), to a ≡ c(mod m) - przechodniość relacji przystawania.

(4) a − b ≡ 0(mod m).

(5) Jeśli a ≡ b(mod m) i c ≡ d(mod m), to a + c ≡ b + d(mod m).

(6) Jeśli a ≡ b(mod m) i c ≡ d(mod m), to a · c ≡ b · d(mod m).

(7*) Jeśli a

i

≡ b

i

(mod m), i ∈ {1, 2, . . . , k}, a

i

, b

i

∈ Z to

k

X

i=1

a

i

≡

k

X

i=1

b

i

(mod m)

jeśli a

1

≡ b

1

(mod m), a

2

≡ b

2

(mod m), . . . , a

k

≡ b

k

(mod m) to

a

1

+ a

2

+ . . . + a

k

≡ b

1

+ b

2

+ . . . + b

k

(mod m)

(8*) a

i

≡ b

i

(mod m), i ∈ {1, 2, . . . , k} i a, b ∈ Z.

(9) Jeśli a ≡ b(mod m), d|m i d > 0 to a ≡ b(mod d).

(10) Jeśli a ≡ b(mod m) i c > 0, c ∈ Z to a · c ≡ b · c(mod m · c)

Dowód twierdzenia 16:

Dowód (1) Mamy pokazać, że a ≡ a(mod m). Rzeczywiście a ≡ a(mod m) ⇔ a − a = k · m, a więc a − a = 0,

czyli 0 = k · m, gdzie k = 0 (bo z definicji kongruencji wynika, że m nie może być równe 0). A więc
m|a − a bo m|0. Z tego możemy także wywnioskować, że a ≡ b(mod m), jeśli m|a − b.

Dowód (2) Mamy wykazać, że jeśli a ≡ b(mod m) to b ≡ a(mod m). Rzeczywiście jeśli, m|a − b to m dzieli też

liczbę przeciwną b − a, a więc jeśli a − b = k · m to b − a = −k · m, co dowodzi przykład. Zatem
b ≡ a(mod m)

Dowód (3) Załóżmy, że a ≡ b(mod m) i b ≡ c(mod m). Istnieją takie liczby k

1

, k

2

∈ Z takie, że a − b = k

1

· m

i b − c = k

2

· m. A więc zacznijmy od końca twierdzenia, a mianowicie:

a − c = (a − b) + (b − c) = k

1

· m + k

2

· m = (k

1

+ k

2

) · m = k · m

jeśli k = k

1

+ k

2

∈ Z. Jeżeli a − c = k · m to a ≡ c(mod m), co kończy dowód.

Dowód (4) Załóżmy, że a ≡ b(mod m). Z definicji wynika, że a − b = k · m dla pewnego k ∈ Z. Dalej

(a − b) − 0 = k · m, więc z definicji przystawania modulo m a − b ≡ 0(mod m).

Dowód (5) Załóżmy, że a ≡ b(mod m) i c ≡ d(mod m). Wówczas istnieją liczby całkowite k

1

, k

2

∈ Z takie, że

a − b = k

1

· m i c − d = k

2

· m, stąd a = b + k

1

· m i c = d + k

2

· m. Dodajemy otrzymane równości

stronami:

a + c = b + d + k

1

+ k

2

· m

Załóżmy, że oznaczymy k

1

+ k

2

= k ∈ Z, zatem a + c = b + d + k · m, z czego wynika, że

(a + c) − (b + d) = k · m, a więc udowodniliśmy, że a + c ≡ b + d(mod m).

Dowód (6) Załóżmy, że a ≡ b(mod m) i c ≡ d(mod m). Wówczas istnieją liczby k

1

, k

2

∈ Z takie, że a−b = k

1

·m

i c − d = k

2

· m. Stąd a = b + k

1

· m i c = d + k

2

· m. Pomnóżmy więc oba wyrażenia stronami

a · c = (b + k

1

· m) · (d + k

2

· m) = bd + bk

2

· m + dk

1

· m + k

1

k

2

m

2

=

= bd + (bk

2

+ dk

1

+ mk

1

k

2

) · m

Oznaczmy k = (bk

2

+ dk

1

+ mk

1

k

2

) ∈ Z, co daje nam bd + k · m, co oznacza z definicji a · c ≡

b · d(mod m).

8

Dowód (7) i (8) Dowód nie obowiązuje na egzaminie.

Dowód (9) Załóżmy, że a ≡ b(mod m) i d|m, gdzie d ∈ N. Zatem istnieje k

1

∈ Z takie, że a − b = k

1

· m i

k

2

∈ Z takie, że m = d · k

2

. Stąd a − b = k

1

· d · k

2

= (k

1

k

2

) · d. Oznaczmy k = k

1

k

2

∈ Z. Wówczas

a − b = k · d, a to oznacza, że a ≡ b(mod d).

Dowód (10) Załóżmy, że a ≡ b(mod m) i c > 0 oraz c ∈ Z. Z definicjui mamy, że a − b = k · m. Pomnóżmy to

przez c, z czego otrzymamy ac − bc = k · mc, z czego wynika (na mocy definicji) ac ≡ bc(mod mc).

Twierdzenie 17 (Wielomian)

Niech f oznacza wielomian o współczynnikach całkowitych o wzorze:

f (x) = a

n

x

n

+ a

n−1

x

n−1

+ . . . + a

1

x

1

+ a

0

gdzie a

0

, a

1

, . . . , a

n

∈ Z

Jeśli a ≡ b(mod m), gdzie a, b ∈ Z i m ∈ N to

f (a) ≡ f (b)(mod m)

Dowód twierdzenia 17:

Z twierdzenia 16 mamy między innymi a ≡ a(mod m) (tzw. zwrotność relacji przystawania), oraz jeśli
a ≡ b(mod m) to a

k

≡ b

k

(mod m) dla k ∈ N. Wynika z tego że:

a

0

≡ a

0

(mod m)

f (a) = a

n

a

n

+ a

n−1

a

n−1

+ . . . + a

1

a

1

+ a

0

f (b) = a

n

b

n

+ a

n−1

b

n−1

+ . . . + a

1

b

1

+ a

0

a więc z a

1

≡ a

1

(mod m) i a ≡ b(mod m) wynika, że a

1

· a ≡ a

1

· b(mod m). Zauważmy, że

a

2

≡ a

2

(mod m) ∧ a

2

≡ b

2

(mod m) ⇒ a

2

· a

2

≡ a

2

· b

2

(mod m)

a

3

≡ a

3

(mod m) ∧ a

3

≡ b

3

(mod m) ⇒ a

3

· a

3

≡ a

3

· b

3

(mod m)

..

.

a

n

≡ a

n

(mod m) ∧ a

n

≡ b

n

(mod m) ⇒ a

n

· a

n

≡ a

n

· b

n

(mod m)

Z odpowiedniego prawa relacji przystawania wiemy, że kongruencje możemy sumować stronami:

a

n

a

n

+ a

n−1

a

n−1

+ . . . + a

1

a + a

0

≡ a

n

b

n

+ a

n−1

b

n−1

+ . . . + a

1

b + a

0

(mod m)

czyli f (a) ≡ f (b)(mod m).

Twierdzenie 18 (Chińskie twierdzenie o resztach)

Niech m ­ 2. Niech a

1

, a

2

, . . . , a

m

∈ N takie, że (a

i

, a

j

) = 1 (są względnie pierwsze), dla i 6= j, i, j ∈

{1 . . . m}. Niech r

1

, r

2

. . . , r

m

∈ Z (dowolne liczby całkowite). Wówczas istnieje liczba x ∈ Z taka, że

x ≡ r

1

(mod a

1

)

x ≡ r

2

(mod a

2

)

..

.

x ≡ r

m

(mod a

m

)

Liczba x jest wyznaczona jednoznacznie modulo a

1

· a

2

· . . . · a

m

.

Twierdzenie 19 (Lagrange’a)

Niech f (x) = a

n

x

n

+ a

n−1

x

n−1

+ . . . + a

1

x

1

+ a

0

, gdzie a

n

, a

n−1

, . . . , a

1

, a

0

∈ Z. Niech p będzie liczbą

pierwszą taką, że a

n

6≡ 0(mod p). Wówczas kongruencja f (x) ≡ 0(mod p) ma co najwyżej n pierwiastów.

9

Twierdzenie 20 (Wilsona)

Jeśli p jest liczbą pierwszą, to (p − 1)! ≡ −1(mod p).

Twierdzenie 21 (Eulera)

Jeśli a jest liczbą całkowitą wszględnie pierwszą z m ∈ N, to

a

ϕ(m)

≡ 1(mod m)

gdzie (a, m) = 1, a ∈ Z

Twierdzenie 22 (Małe twierdzenie Fermata)

Jeśli a jest liczbą całkowitą, zaś p jest liczbą pierwszą, to a

p−1

≡ 1(mod p) i a

p

≡ a(mod p).

2

Algebra abstrakcyjna

2.1

Iloczyn kartezjański zbiorów

Definicja 9 (Iloczynu kartezjańskiego)

Niech dane będą dwa niepuste zbiory A i B, wtedy iloczynem kartezjańskim nazywamy zbiór par uporząd-
kowanych (a, b), takich że:

A × B = {(a, b) : a ∈ A ∧ b ∈ B}

Definicja 10 (Działania wewnętrznego)

Działaniem wewnętrznym w zbiorze A nazywamy każde odwzorowanie zbioru A×A w zbiorze A. Działanie
to oznaczamy np. symbolem ◦:

◦ : A × A → A

◦(a, b) = a ◦ b; a, b ∈ A

Twierdzenie 23 (Własności działania wewnętrznego)

1. Działanie ◦ : A × A → A nazywamy działaniem łącznym w zbiorze A, jeśli:

∀

a,b,c∈A

(a ◦ b) ◦ c = a ◦ (b ◦ c)

2. Działanie ◦ : A × A → A nazywamy działaniem przemiennym w zbiorze A, jeśli:

∀

a,b∈A

a ◦ b = b ◦ a

3. Jeśli:

∃

e∈A

∀

a∈A

e ◦ a = a ◦ e = a

wtedy e nazywamy elementem neutralnym (jeśli wogóle istnieje, bo nie musi istnieć)

4. Załóżmy, że w zbiorze A istnieje element neutralny działania ◦. Elementem odwrotnym do elementu

a ∈ A nazywamy taki element b ∈ A (o ile istnieje), że:

a ◦ b = b ◦ a = e

Twierdzenie 24

Jeśli w zbiorze A z działaniem wewnętrznym ◦ istnieje element neutralny działania ◦, to istnieje on tylko
jeden.

10

Dowód twierdzenia 24:

Przypuśćmy, że e

1

i e

2

są elementami neutralnymi działania ◦, zatem

e

1

◦ e

2

= e

2

◦ e

1

= e

1

(ponieważ e

2

jest elementem neutralnym)

e

2

◦ e

1

= e

1

◦ e

2

= e

2

(ponieważ e

1

jest elementem neutralnym)

Zatem z powyższego wynika, że e

1

= e

1

◦ e

2

= e

2

◦ e

1

= e

2

, a więc e

1

= e

2

. Przypuszczenie było błędne,

gdyż jest tylko jeden element neutralny danego działania ◦ w danym zbiorze.

Twierdzenie 25

Załóżmy, że w A istnieje element neutralny działania ◦ (◦ : A × A → A) oraz, że działanie ◦ jest łączne
w zbiorze A. Jeśli a ∈ A posiada element odwrotny w zbiorze A, to tylko jeden.

Dowód twierdzenia 25:

Rzeczywiście niech b

1

i b

2

będą elementami odwrotnymi do elementu a wówczas:

a ◦ b

1

= b

1

◦ a = e

(gdyż b

1

jest elementem odwrotnym do a)

a ◦ b

2

= b

2

◦ a = e

(gdyż b

2

jest elementem odwrotnym do a)

Zatem b

1

= b

1

◦ e = b

1

◦ (a ◦ b

2

) = (b

1

◦ a) ◦ b

2

= e ◦ b

2

= b

2

, a więc b

1

= b

2

i nasze przypuszczenie było

błędne.

Jeśli działanie oznaczamy symbolem +, to taki zapis nazywamy zapisem addytywnym. Wówczas ele-
ment neutralny oznaczamy symbolem 0, a element odwrotny do a nazywamy elementem przeciwnym do
a i oznaczamy symbolem −a.

Jeśli działanie oznaczamy symbolem ·, to taki zapis nazywamy zapisem multiplikatywnym. Wówczas
element neutralny oznaczamy symbolem 1, a element odwrotny do a nazywamy elementem odwrotnym
i oznaczamy symbolem a

−1

albo

1
a

.

Definicja 11 (Działania zewnętrznego)

Działanie ◦ : P × A → A, gdzie P ,A - dowolne niepuste zbiory, nazywamy działaniem zewnętrznym w
zbiorze A.

Definicja 12 (Struktury algebraicznej)

Strukturą algebraiczną nazywamy układ złożony ze zbioru i skończonych ilości działań wewnętrznych i
zewnętrznych określonych na zbiorze A.

2.2

Grupy

Definicja 13 (Grupy)

Zbiór G wraz z działaniem ◦ nazywamy grupą, jeśli spełnione są następujące warunki:

1. ◦ : G × G → G

11

2. ∀

a,b,c∈G

(a ◦ b) ◦ c = a ◦ (b ◦ c) (◦ jest działaniem łącznym w zbiorze G)

3. ∃

e∈G

∀

a∈G

e ◦ a = a ◦ e = a (istnieje element neutralny działania ◦ w zbiorze G)

4. ∀

a∈G

∃

b∈G

a ◦ b = b ◦ a = e (istnieje element odwrotny b do elementu a w zbiorze G)

Jeśli dodatkowo spełniony jest warunek:

5. ∀

a,b∈G

a ◦ b = b ◦ a (przeienność działania ◦ w zbiorze G)

to grupa ta jest grupą abelową.

Twierdzenie 26 (Praw działania wewnętrznego)

Dla a, b ∈ A i ◦ = · zachodzą następujące prawa:

1. (b

−1

)

−1

= b

2. (a · b)

−1

= b

−1

· a

−1

ale uwaga: (a · b)

−1

6= a

−1

· b

−1

.

Dowód twierdzenia 26:

1. Rzeczywiście:

(b

−1

)

−1

· (b

−1

)

=

e

| · b

(b

−1

)

−1

· (b

−1

) · b

=

e · b

(b

−1

)

−1

· (b

−1

· b)

=

e · b

(b

−1

)

−1

· e

=

b · e

(b

−1

)

−1

=

b

2. Rzeczywiście:

(ab)

−1

· (ab)

=

e

| · b

−1

(ab)

−1

· (ab) · b

−1

=

e · b

−1

(ab)

−1

· a(b · b

−1

)

=

b

−1

(ab)

−1

· a · e

=

b

−1

(ab)

−1

· a

=

b

−1

| · a

−1

(ab)

−1

· a · a

−1

=

b

−1

· a

−1

(ab)

−1

· e

=

b

−1

· a

−1

(ab)

−1

=

b

−1

· a

−1

2.3

Podgrupy

Definicja 14 (Podgrupy)

Niech będzie dana grupa (G, ◦). Niech H ⊂ G, H 6= ∅. Podzbiór H nazywamy podgrupą grupy G wtedy i
tylko wtedy, gdy H jest grupą ze względu na działanie ◦ rozważane w zbiorze H.
Grupa i każda jej podgrupa mają ten sam element neutralny i element odwrotny do a w zbiorze H jest
taki sam, jak w zbiorze G.

Twierdzenie 27

Niepusty podzbiór H grupy (G, ◦) jest jej podgrupą wtedy i tylko wtedy, gdy:

∀

a,b∈H

a ◦ b

−1

∈ H

12

Twierdzenie 28 (Rząd grupy)

Jeśli liczba elementów grupy jest skończona i równa k to rząd tej grupy też jest równy k. Jeżeli liczba
elementów grupy jest nieskończona, to mówimy że rząd tej grupy jest nieskończony.

Twierdzenie 29 (Lagrange o rzędzie podgrupy grupy skończonej)

Rząd podgrupy grupy skończonej (tzn. mającej skończoną liczbę elementów) jest dzielnikiem rzędu tej
grupy.

2.4

Grupy permutacji

Definicja 15 (Funkcji różnowartościowej)

Funkcja g : X → Y jest różnowartościowa:

∀

x

1

,x

2

∈X

(x

1

6= x

2

⇒ g(x

1

) 6= g(x

2

))

∀

x

1

,x

2

∈X

(g(x

1

) = g(x

2

) ⇒ x

1

= x

2

)

Definicja 16 (Permutacji)

Permutacją zbioru X 6= ∅ nazywamy każde różnowartościowe odwzorowanie zbioru X na siebie. Weźmy
pod uwagę zbiór X = {1, 2, 3 . . . , n}:

σ =



1

2

3

. . .

n

σ(1)

σ(2)

σ(3)

. . .

σ(n)



Permutację oznaczamy małymi literami greckiego alfabetu (α, β, γ, τ, π, δ). Permutacje można mnożyć
(tzw. składanie permutacji). Mnożymy (składamy) permutacje tego samego typu :

σ =



1

2

3

. . .

n

σ(1)

σ(2)

σ(3)

. . .

σ(n)



τ =



1

2

3

. . .

n

τ (1)

τ (2)

τ (3)

. . .

τ (n)



τ ◦ σ =



1

2

3

. . .

n

τ (σ(1))

τ (σ(2))

τ (σ(3))

. . .

τ (σ(n))



Składanie permutacji nie jest działaniem przemiennym: τ ◦ σ 6= σ ◦ τ . Składanie permutacji jest dzia-
łaniem wewnętrznym. Składanie wszelkich przekształceń, a więc i permutacji, jest działaniem łącznym.
Elementem neutralnym jest premutacja identycznościowa (tożsamościowa):

e =



1

2

3

. . .

n

1

2

3

. . .

n



Elementem odwrotnym do danej permutacji

σ =



1

2

3

. . .

n

σ(1)

σ(2)

σ(3)

. . .

σ(n)



jest permutacja odwrotna

σ

0

=



σ(1)

σ(2)

σ(3)

. . .

σ(n)

1

2

3

. . .

n



Twierdzenie 30

Zbiór permutacji zbioru X = {1, 2, . . . , n} stanowi grupę nieprzemienną ze względu na składanie (mno-
żenie) permutacji.

13

Twierdzenie 31 (Permutacja cykliczna (cykl))

Niech X = {1, 2, . . . , n}. Niech Y = {a

1

, a

2

, . . . , a

k

}, k ¬ n będzie pewnym podzbiorem zbioru X. Per-

mutacją π ∈ S

n

(zbiór n-elementowy) nazywamy permutacją cykliczną albo cyklem, jeśli:

π(a

1

) = a

2

, π(a

2

) = a

3

, . . . , π(a

k−1

) = a

k

, π(a

k

) = a

1

Jeśli a

i

6∈ Y , to π(a

i

) = a

i

.

Liczbę k nazywamy rzędem permutacji cyklicznej. Permutacja identycznościowa (tożsamościowa) jest
cyklem rzędu 0, tzn. Y = ∅.

Twierdzenie 32

Każda permutacja należąca do zbioru S

n

jest cyklem lub daje się przedstawić w postaci iloczynu cykli.

Definicja 17

Cykl 2-elementowy nazywamy transpozycją i zapisujemy (dla i < j):

(i, j) =



1

2

. . .

i − 1

i

i + 1

. . .

j − 1

j

j + 1

. . .

n

1

2

. . .

i − 1

j

i + 1

. . .

j − 1

i

j + 1

. . .

n



Twierdzenie 33

Każdy cykl można przedstawić w postaci iloczynu (złożenia) pewnej ilości transpozycji.

Twierdzenie 34

Każdą permutację można przedstawić w postaci iloczynu (złożenia) transpozycji.

Twierdzenie 35 (Permutacja parzysta, nieparzysta)

Jeśli liczba transpozycji w rozkładzie permutacji na transpozycje jest liczbą parzystą, to daną permutację
nazywamy permutacją parzystą. W przeciwnym wypadku permutację nazywamy nieparzystą.

Definicja 18 (Znaku permutacji)

Dla I

t

= {ilość transpozycji w rozkładzie permutacji σna transpozycje} znak permutacji sgn σ jest rów-

ny:

sgn σ = (−1)

I

t

Definicja 19 (Inwersji)

Mamy dany cykl (α

1

α

2

. . . α

k

), gdzie α

i

∈ R oraz i ∈ {1, 2, . . . , k}. Powiemy, że liczby α

i

i α

j

tworzą

inwersję, jeśli α

i

> α

j

podczas gdy i < j (i, j ∈ {1, 2, . . . , k}).

2.5

Homomorfizm grup

Definicja 20 (Homomorfizmu grup)

Niech dane będą dwie grupy: (G, ◦) i (G

0

, ◦

0

). Odwzorowanie h : G → G

0

nazywamy homomorfizmem,

jeśli

∀

a,b∈G

h(a ◦ b) = h(a) ◦

0

h(b)

Powiemy, że homomorfizm h jest izomorfizmem, jeśli jest odwzorowaniem różnowartościowym, od-
wzorowującym zbiór G na zbiór G

0

14

Definicja 21 (Grup cyklicznych)

Niech (G, ◦) będzie grupą i niech a ∈ G. Symbolem a

k

oznaczamy a

k

= a◦a◦. . .◦a (k czynników). Na mocy

definicji a

0

= e i a

−k

= a

−1

◦ a

−1

◦ . . . ◦ a

−1

(k czynników). Niech zbiór H = {. . . , a

−2

, a

−1

, a

0

, a

1

, a

2

, . . .}

stanowi podgrupę grupy G.

Grupę (G, ◦) nazywamy cykliczną, jeśli istnieje w G taki element a, że każdy element tej grupy jest pewną
potęgą całkowitą (wielokrotnym złożeniem) elementu a. Element nazywamy generatorem grupy G.

2.6

Pierścienie

Definicja 22 (Pierścienia)

Zbiór P nazywamy pierścieniem, jeśli:

1. Mamy dwa działania: + : P × P → P oraz ◦ : P × P → P

2. (P, +) jest grupą abelową

3. Prawdziwe są zdania:

• ∀

a,b,c∈P

a(bc) = (ab)c

• ∀

a,b,c∈P

a(b + c) = ab + ac ∧ (b + c)a = bc + ca

Element a ∈ P z pierścienia (P, +, ◦) nazywamy dzielnikiem zera, jeśli a 6= 0 i dla a istnieje b 6= 0, takie,
że a ◦ b = 0.

W pierścieniu nie każdy element musi mieć element odwrotny.

2.7

Ciała

Definicja 23 (Ciała)

Zbiór K wyposażony w dwa działania wewnętrzne + oraz ◦ nazywamy ciałem, jeśli:

1. (K, +) jest grupą abelową

2. (K − {0}, ◦) jest grupą abelową, 0 - element zerowy działania +.

3. ∀

a,b,c∈K

a ◦ (b + c) = a ◦ b + a ◦ c

Przykłady ciał: (R, +, ·), (Q, +, ·), niech Q

√

2 = {a + b

√

2 : a, b ∈ Q} to (Q

√

2, +, ·) też jest ciałem.

2.8

Homomorfizm ciał i pierścieni

Definicja 24 (Homomorfizmu pierścieni)

Niech będą dane dwa pierścienie (P, +, ·) oraz (P

0

, +

0

, ·

0

). Odwzorowanie h : P → P

0

nazywamy homo-

morfizmem pierścienia P w pierścieniu P

0

, jeśli:

∀

a,b∈P

h(a + b) = h(a) +

0

h(b) ∧ h(a · b) = h(a) ·

0

h(b)

Jeśli h odwzorowuje w sposób wzajemnie jednoznaczny P na P

0

, to h nazywamy izomorfizmem pierścienia

P na pierścień P

0

, a pierścienie P i P

0

nazywamy izomorficznymi.

15