Algebra

2 Podstawy teorii liczb

Celem tego rodziału będzie zaznajomienie czytelnika z podstawowymi wynikami teorii liczb, które są interesujące nie tylko same w sobie, ale znajdą również zastosowanie w dalszych rozdziałach i niejednokrotnie będą motywacją do wprowadzenia nowych pojęć (i badania ich własności).

2.1 Podzielność w $\Z $

Definicja 2.1.1 ( podzielność w $\Z $). Niech $a$, $b\in \Z $. Mówimy, że $b$ dzieli $a$ (lub inaczej $b$ jest dzielnikiem $a$), gdy istnieje takie $c\in \Z $, że $a=bc$.

W dalszej części wykładu dla oznaczenia podzielności $b|a$ będziemy krótko pisać: $b|a$.

Uwaga 2.1.2 ( własności podzielności w $\Z $). Niech $a, b, c, m, n\in \Z $. Wtedy:

(a) $1|a$, $a|0$,

(b) jeśli $0|a$, to $a=0$,

(c) relacja podzielności na $\Z ^\star $ jest zwrotna i przechodnia,

(d) $(b|a \ i \ a|b)$ wtedy i tylko wtedy, gdy $|a|=|b|$,

(e) jeśli $c|a$, $c|b$, to $c|(am+nb)$,

(f) jeśli $a|b$ i $b\ne 0$, to $1\leqslant |a|\leqslant |b|$.

Przedstawimy poniżej dwie wersje twierdzenia o algorytmie dzielenia z resztą w zbiorze liczb całkowitych. Pierwsza z tych wersji (wersja A) stanowi przygotowanie do przyszłego uogólnienia omawianej własności do bardziej abstrakcyjnej sytuacji pierścienia euklidesowego (por. odnośnik). Druga wersja (wersja B) jest znana szerzej i szczególnie wygodna w zastosowaniach.

Twierdzenie 2.1.3 ( algorytm dzielenia z resztą - wersja A). Niech $a$, $b$ - liczby całkowite, $b\ne 0$. Wtedy istnieje para $(q,r)\in \Z \times \Z $ spełniająca następujące warunki:

(1) $a=bq+r$, (2) $|r|<|b|$.

Liczbę $q$ nazywamy wynikiem dzielenia zaś $r$ resztą z dzielenia.

Potraktujemy to twierdzenie jako konsekwencję wspomnianego wyżej, ogólniejszego rezultatu.

Twierdzenie 2.1.4 ( algorytm dzielenia z resztą - wersja B). Niech $a, b\in \Z $ i załóżmy, że $b\ne 0$. Wtedy:

($\bullet $) istnieje dokładnie jedna taka para $(q,r)\in \Z \times \Z $, że:

(1) $a=bq+r$, (2) $0\leqslant r<|b|$.

($\bullet $) jeśli dodatkowo $b\nmid a$, to istnieją dokładnie dwie pary $(q,r)$ takie, że

(1) $a=bq+r$, (2) $|r|<|b|$.

Dowód. Udowodnimy pierwszą część twierdzenia 2.1.4 (wynika z niej natychmiast tw. 2.1.3).

Istnienie reszty. Niech $S:=\{a-kb, \ k\in \Z , \ a-kb\geqslant 0\}$ - jest to niepusty podzbiór $\N _0$, wobec tego ma on element najmniejszy, który oznaczymy jako $r$. Element ten jest postaci $r=a-qb$ dla pewnego $q$ całkowitego i z jego określenia widzimy, że spełniona jest nierówność $0\leqslant r$ oraz $a=qb+r$.

Pozostaje jedynie pytanie, czy $r<|b|$? Udowodnimy tę część niewprost. Gdyby $r\geqslant |b|$, to $r-|b|\geqslant 0$ oraz $r-|b|=a-qb-|b|=a-(q+sgn(b))b$, więc $r-|b|\in S$ oraz $r-|b|<r$, (skoro $b\ne 0$, to $|b|\geq 1$). Dostajemy sprzeczność z wyborem $r$.

Jednoznaczność reszty nieujemnej. Dla dowodu niewprost załóżmy, że $a=bq_1+r_1=bq_2+r_2$, $0\leqslant r_1<|b|$, $0\leqslant r_2<|b|$. Jeśli $r_1<r_2$, to oczywiście $q_1-q_2\ne 0$. Otrzymujemy zatem, że $b(q_1-q_2)=r_2-r_1$ i w konsekwencji $|b|\leqslant |b||q_1-q_2|=|r_2-r_1|=(r_2-r_1)<|b|$, co prowadzi do sprzeczności. W analogiczny sposób rozumujemy w przypadku, gdy $r_{2}<r_{1}$. □

Zachęcamy do udowodnienia we własnym zakresie drugiej części twierdzenia 2.1.4.

Algebra

2.2 NWD i NWW w $Z$

Pojęcia największego wspólnego dzielnika i najmniejszej wspólnej wielokrotności liczb całkowitych są fundamentalne w teorii liczb. Ich podstawowa definicja jest ściśle związana z istnieniem porządku w zbiorze liczb całkowitych. Należy jednak zaznaczyć, że istnieje definicja tych pojęć w ogólniejszych strukturach algebraicznych, w których na ogół nie możemy mówić o pojęciu „najmniejszy” czy „największy”. Wspomnianą defincję przdstawimy dalszej części naszyh rozważań ( odnośnik).

Definicja 2.2.1 ( NWD, NWW, względna pierwszość).
- (1) Największym wspólnym dzielnikiem liczb $a_1,\dots ,a_r\in \Z $, (zakładamy, że przynajmniej jedna z liczb jest niezerowa) nazywamy największą liczbę całkowitą, która dzieli wszystkie $a_1, \ldots , a_r$. ¹
  
  $\underline {Oznaczenie:}$ $\nwd (a_1,\dots ,a_r)$ (w literaturze również: $(a_1,\ldots , a_r)$)
- (2) Najmniejszą wspólną wielokrotnością niezerowych liczb całkowitych $a_1,\dots ,a_r$ nazywamy najmniejszą liczbę całkowitą dodatnią, która jest podzielna przez każdą z liczb $a_1,\ldots , a_r$.
  
  $\underline { Oznaczenie:}$ $\nww (a_1,\dots ,a_r)$ (w literaturze również: $[a_1,\ldots , a_r]$)
- (3) (liczby względnie pierwsze) Liczby $a_1, \ldots , a_r\in \Z $, $a_1\ne 0$ nazywamy względnie pierwszymi, gdy $\nwd (a_1,\ldots , a_r)=1$.

Uwaga 2.2.2. Niech $a, b\in \Z ^{\star }$. Zauważmy, że z określenia $\nwd (a, b)$ wynika, że prawdziwe są równości:

\[ \nwd (a,b)=\nwd (b,a)=\nwd (\pm a,\pm b), \]

dla dowolnej kombinacji znaków $\pm $.

Przedstawimy teraz metodę wyznaczania największego wspólnego dzielnika dwóch liczb całkowitych $a$ i $b$, która nosi nazwę algorytmu Euklidesa ². Oczywiście, jeśli $a\in \Z ^\star $, $b=0$, to $\nwd (a,b)=|a|$. W dalszej części naszych rozważań zakładamy, że obie liczby są niezerowe.

Algorytm Euklidesa ³

Ustalmy dwie liczby całkowite $a,b\in \Z ^\star $. Przyjmijmy: $r_{-1}:=a$, $r_0:=|b|$.

Krok 1: Zgodnie z algorytmem dzielenia z resztą (1.3.(B) ($\bullet $)) istnieją liczby całkowite $q_1,r_1\in \Z $ takie, że:

(1) $a=r_{-1}=q_1|b|+r_1$,

(2) $0\leqslant r_1<|r_0|=|b|$.

Jeśli $r_1=0$, to kończymy algorytm. Jeśli $r_1\ne 0$, to wykonujemy Krok 2.

Krok 2: Istnieją liczby całkowite $q_2,r_2\in \Z :$

(1) $r_0=q_2r_1+r_2$,

(2) $0\leqslant r_2<r_1<|r_0|=|b|$.

Jeśli $r_2=0$, to kończymy algorytm. Jeśli $r_2\ne 0$, to kontynuujemy analogicznie.

Ogólnie, mając $r_{i-2}, r_{i-1}$ takie, że $r_{i-1}\ne 0$, wykonujemy kolejny krok:

Krok (i$>$1): Istnieją liczby całkowite $q_i,r_i\in \Z $:

(1) $r_{i-2}=q_ir_{i-1}+r_i$,

(2) $0\leqslant r_i<r_{i-1}$.

Ze względu na nierówności: $0\leqslant r_i<r_{i-1}$ istnieje $N(a,b)\in \N $ takie, że $r_{N(a,b)+1}=0$ ale $r_{N(a,b)}\ne 0$.

Liczbę $N(a,b)\in \N $ będziemy nazywać dalej długością algorytmu Euklidesa dla liczb $a$ i $b$, (długość może być równa zero, gdy $b|a$), zaś $r(a,b):=r_{N(a,b)}$ wynikiem tego algorytmu.

Zanim przedstawimy związek algorytmu Euklidesa z wyznaczaniem największego wspólnego dzielniak liczb $a, b\in \Z ^{\star }$ potrzebny nam będzie jeszcze jeden wynik.

Lemat 2.2.3. Z: Niech $a, b\in \Z ^\star $ i napiszmy $a=qb+r$, gdzie $0\leq r<|b|$.

T: $\nwd (a,b)=\nwd (b,r)$.

Dowód. Niech $d:=\nwd (a,b)$ i $d’:=\nwd (b,r)$. Wykażemy, że $d=d’$. Ponieważ $d|a$ i $d|b$, więc istnieją takie liczby $k_{1}, k_{2}\in \Z $, że $a=dk_{1}, b=dk_{2}$. Z założenia otrzymujemy równość $r=a-qb=d(k_{1}-qk_{2})$. Oznacza to, że $d|r$ i w konsekwencji $d|d’$ (bo $d’=\nwd (b,r)$). W szczególności $d\leq d’$. Niech teraz $k_{3}, k_{4}\in \Z $ będą takie, że $b=d’k_{3}, r=d’k_{4}$. Stąd $a=qb+r=d’(qk_{3}+k_{4})$ i dostajemy, że $d’|a$. Oznacza to, że $d’$ jest wspólnym dzielnikiem $a, r$ i prawdziwa jest nierówność $d’\leq d$ (bo $d=\nwd (a,b)$). Otrzymujemy zatem $d=d’$, co daje tezę. □

Wykażemy teraz, że prawdziwe jest następujące

Twierdzenie 2.2.4. Z: Niech $a, b\in \Z ^\star $.

T: $\nwd (a,b)=r_{N(a,b)}$.

Dowód. Dla $a, b\in \Z ^\star $ oznaczmy $n:=N(a,b)$. By dowieść naszego twierdzenia wykażemy równość $\nwd (a,b)=r_{n}$. Z opisu algorytmu Euklidesa wynika, że istnieją takie ciągi liczb całkowitych $r_{i}, i=1,\ldots , n, q_{i}, i=1, \ldots , n+1$, że spełnione są równości

\[ a=q_{1}|b|+r_{1},\; |b|=q_{2}r_{1}+r_{2},\ldots ,r_{n-2}=q_{n}r_{n-1}+r_{n},\;r_{n-1}=q_{n+1}r_{n}, \]

gdzie $0<r_{n}<r_{n-1}<\ldots < r_{2}<r_{1}$. W konsekwencji, z lematu 2.2.3, otrzymujemy ciąg równości
$ \seteqsection {2} $
\begin{align*} \nwd (a,b)&=\nwd (|b|,r_{1})=\nwd (r_{1},r_{2})=\ldots =\nwd (r_{n-2},r_{n-1})\\ &=\nwd (r_{n-1},r_{n})=\nwd (q_{n+1}r_{n},r_{n})=r_{n}, \end{align*} co dowodzi tezy. □

Gdy już wiemy, że dla danej pary liczb $a, b\in \Z ^{\star }$ można łatwo wyznaczyć ich największy wspólny dzielnik pojawia się naturalne pytanie: jak duża jest liczba kroków konieczna do wyznaczenia $\nwd (a,b)$? Innymi słowy interesuje nas wielkość liczby $N(a,b)$. Odpowiedź na tak sformułowane pytanie daje rezultat otrzymany przez G. Lamégo. Zanim go sformułujemy przypomnijmy pojęcie liczby Fibonacciego. Dokładniej, jeśli $F_{0}=0, F_{1}=1$, oraz dla $n\geq 2$ położymy $F_{n}=F_{n-1}+F_{n}$, to liczbę $F_{n}$ nazywamy $n$-tą liczbą Fibonacciego. Jeśli oznaczymy teraz $\phi $ dodatni pierwiastek równania $x^2-x-1=0$, tzn. $\phi =\frac {1}{2}(1+\sqrt {5})$, to można wykazać, że $n$-ta iczba Fibonacciego wyraża się tzw. wzorem Bineta postaci:

\[ F_{n}=\frac {1}{\sqrt {5}}\left (\phi ^{n}-\frac {1}{(-\phi )^{n}}\right ). \]

Stosując indukcję ze względu na $n$ oraz rekurencję $F_{n}=F_{n-1}+F_{n-2}$ bez trudu można wykazać, że $F_{n}>\phi ^{n-2}$.

Twierdzenie 2.2.5 (o liczbie kroków w algorytmie Euklidesa). Z: Niech $a, b\in \N $ i niech $N(a,b)$ oznacza liczbę kroków w algorytmie Euklidesa wyznaczania $\nwd (a,b)$.

T: $N(a,b)=5(\lfloor \log _{10}b\rfloor +1)$.

Dowód. Dla $a, b\in \N , b<a,$ oznaczmy $n:=N(a,b)$. Z twierdzenia 2.2.4 wiemy, że $\nwd (a,b)=r_{n}$. Z opisu algorytmu Euklidesa wynika, że istnieją takie ciągi liczb całkowitych $r_{i}, i=1,\ldots , n, q_{i}, i=1, \ldots , n+1$, że spełnione są równości

\[ a=q_{1}|b|+r_{1},\; |b|=q_{2}r_{1}+r_{2},\ldots ,r_{n-2}=q_{n}r_{n-1}+r_{n},\;r_{n-1}=q_{n+1}r_{n}, \]

$0<r_{n}<r_{n-1}<\ldots < r_{2}<r_{1}$. Ponadto, dla $i=1,\ldots , n,$ mamy, że $q_{i}\geq 1$ oraz $q_{n+1}\geq 2$. Otrzymujemy zatem, że
$ \seteqsection {2} $
\begin{align*} r_{n}&\geq 1=F_{1},\\ r_{n-1}&\geq 2r_{n}\geq 2F_{1}=F_{2},\\ r_{n-2}&\geq r_{n-1}+r_{n}\geq F_{2}+F_{1}=F_{3},\\ r_{n-3}&\geq r_{n-2}+r_{n-1}\geq F_{3}+F_{2}=F_{4},\\ \vdots & \\ r_{2} & \geq r_{3}+ r_{2}\geq F_{n-2}+F_{n-3}=F_{n-1},\\ r_{1} & \geq r_{2}+ r_{1} \geq F_{n-1}+F_{n-2}=F_{n},\\ r_{0}=b & \geq r_{1}+r_{0} \geq F_{n}+F_{n-1}=F_{n+1}. \end{align*} W szczególności prawdziwa jest nierówność $b\geq F_{n+1}$ i jeśli $n\geq 2$, to otrzymujemy $b \geq \phi ^{n-1}$. Ponieważ $\log _{10}\phi =0.208988\ldots >\frac {1}{5}$, więc $\log _{10}b>\frac {1}{5}(n-1)$ lub równoważnie

\[ n\leq 5\log _{10}b+1. \]

Zauważmy teraz, że jeśli $b$ ma $m$ cyfr w zapisie dziesiętnym, to $b\leq 10^{m}$ i stąd $\log _{10}b<m$. W konsekwencji $n<5m+1$ i ostatecznie $n\leq 5m$. Ponieważ prawdziwa jest równość $m=\lfloor \log _{10}b\rfloor +1$, więc dostajemy tezę. □

Uwaga 2.2.6. Należy zauważyć, że teza w powyższym twierdzeniu nie może być wzmocniona. Istotnie, z dowodu wynika, jeśli $a=F_{n+1}, b=F_{n}$, to w nierównościach wiążących reszty $r_{n-i}$ z liczbami Fibonacciego $F_{i+1}$ dla $i=0,\ldots , n$, mamy tak naprawdę równości, co jest konsekwencją rekurencji spełnianej przez liczby Fibonacciego.

Przejdziemy teraz do dowodu tzw. identyczności Bacheta-Bezouta, która dla ustalonych liczb całkowitych $a_{1},\ldots ,a_{n}$, umożliwia przedstawienie $\nwd (a_{1},\ldots ,a_{n})$ jako kombinacji liniowej o współczynnikach całkowitych liczb $a_{1},\ldots ,a_{n}$.

Twierdzenie 2.2.7 ( identyczność Bacheta-Bezouta). Z: Niech $a_1,\dots , a_n\in \Z $ i załóżmy, że con jamniej jedna z tych liczb jest niezerowa.

T: Istnieją takie liczby $k_1,\ldots , k_n\in \Z $, że spełniona jest równość

\[\nwd (a_1,\ldots , a_n)=k_1a_1+\ldots +k_na_n.\]

Dowód. Najpierw udowodnimy tezę dla dwóch liczb $a$, $b$ z których co najmniej jedna jest niezerowa. W tym celu rozważmy zbiór $T=\{ax+by: \ ax+by>0, x, y\in \Z \}$. Oczywiście, jedna z liczb $\pm a$, $\pm b$ należy do naszego zbioru bo któraś z liczb $a$, $b$ jest niezerowa. Wobec tego zbiór ten jest niepusty. Ponieważ zawiera wyłącznie liczby naturalne, to posiada element najmniejszy, powiedzmy $d$. Istnieją więc takie liczby $x_0$, $y_0\in \Z $, że $d=ax_0+by_0$. Udowodnimy, że $d$ jest poszukiwanym największym wspólnym dzielnikiem $a$ i $b$.

Udowodnimy najpierw, że $d|a$. Z algorytmu dzielenia z resztą wiemy, że istnieją $q$, $r$ takie, że $a=dq+r$ i $0\leqslant r<d$. Wobec tego

\[r=a-dq=a(1-qx_0)-bqy_0.\]

Jeśli $r>0$, to $r\in T$ i jest to element mniejszy od $d$, sprzeczność. W takim razie $r=0$ i w konsekwencji dostajemy $d|a$. W analogiczny sposób dowodzimy, że $d|b$.

Załóżmy teraz, że $0<t$ jest taką liczbą całkowitą, która dzieli i $a$ i $b$. To oznacza, że $a=tm$, $b=tn$, skąd $d=ax_0+by_0=t(mx_0+ny_0)$ czyli $t|d$, wobec czego $t\leqslant d$. Oznacza to, że każdy wspólny dzielnik liczb $a$ i $b$ jest dzielnikiem $d$, co oznacza, że $d=\nwd (a,b)$.

Przypuśćmy teraz, że $n>2$ i nasze twierdzenie jest prawdziwe dla mniej niż $n$ liczb.

Wprowadźmy następujące oznaczenia:

\[d_0:=\nwd (a_1,\ldots , a_{n-1})>0, \ \ \ \ d:=\nwd (\nwd (a_1,\ldots , a_{n-1}),a_n)>0.\]

Zgodnie z założeniem indukcyjnym wiemy, że istnieją takie liczby $l_1,\ldots , l_{n-1}, k, l\in \Z $, że

\[ (\star )\ \ \ d_0=l_1a_1+\ldots +l_{n-1}a_{n-1}, \ \ \ \ \ d=kd_0+la_n. \]

Udowodnimy, że $d$ jest największym wspólnym dzielnikiem liczb $a_1,\ldots , a_n$, (a przy okazji udowodnimy własność rekurencyjnego obliczania $\nwd $).

Z definicji wynika, że $d$ dzieli $d_0$ oraz $a_n$. Ponieważ $d_0$ dzieli każde $a_i$ dla $i=1,\ldots , n-1$, z przechodniości relacji podzielności $d$ jest wspólnym dzielnikiem wszystkich liczb $a_1,\ldots , a_n$.

Z drugiej strony jeśli $\tilde d\in \N $ jest wspólnym dzielnikiem $a_1,\ldots , a_n$, to z $(\star )$ mamy, że $\tilde d|d_0$, a tym samym liczba $\tilde d$ dzieli $d$. Oznacza to, że $\tilde d\leqslant d$ i wobec tego $d=$NWD$(a_1,\ldots , a_n)$.

Jednocześnie, ponownie dzięki $(\star )$, wiemy, że $d=kd_0+la_n=k(l_1a_1+\ldots +l_{n-1}a_{n-1})+la_n$ i przyjmując $k_i:=kl_i$ dla $i=1,\ldots , n-1$ i $k_n:=l$ mamy tezę.

□

Z twierdzenia 2.2.7 i jego dowodu otrzymujemy następujące wnioski.

Wniosek 2.2.8 ( wnioski z BB). Z: $a_1,\dots ,a_r\in \Z $, $\exists \ i=1,\ldots ,r: a_i\ne 0$.

T: (1) Liczby $a_1,\ldots ,a_r$ są względnie pierwsze wtedy i tylko wtedy, gdy istnieją takie liczby całkowite $k_1,\ldots ,k_r$, że:

\[(\star )\ \ \ \ \ \ 1=k_1a_1+\ldots +k_ra_r.\]

(2) Jeśli $r>2$, to $\nwd (\nwd (a_1,\ldots , a_{r-1}),a_r)=\nwd (a_1,\ldots , a_r)$.

(3) Jeśli $(a,b)=1$ i $a|bc$, to $a|c$.

Odnotujmy jeszcze w tym miejscu, że znajomość rozkładu liczb całkowitych $a, b$ na czynniki pierwsze umożliwia szybkie wyznaczenie $\nwd (a,b)$. Istotnie, jeśli

\[ a=\text {sgn}(a)p_1^{k_1}\cdot \ldots \cdot p_s^{k_s},\;b=\text {sgn}(b)p_1^{l_1}\cdot \ldots \cdot p_s^{l_s},\]

(zakładamy, że $p_i\ne p_j$ dla $i\ne j$, $k_i\geqslant 0$ oraz $t_i=$min$(k_i,l_i)>0$ dla każdego $i$), to $\nwd (a,b)=p_1^{t_1}\cdot \ldots \cdot p_s^{t_s}$. Nie wspominamy dokładniej o tej metodzie, gdyż odwołuje się ona do zasadniczego twierdzenia arytmetyki, o którym opowiemy w dalszej części naszych rozważań. Należy jednak zwrócić uwagę, że ta metoda wyznaczania $\nwd (a,b)$ ma istotną słabość, gdyż wymaga znajomości rozkładu liczb $a, b$. Dla małych wartości $a, b$ nie jest to problem, ale gdy liczby $a, b$ są duże, powiedzmy $>10^{100}$, i wybrane w sposób losowy, to problem ich rozkładu jest trudny.

Z podstawowych informacji odnotujmy na zakończenie zależność łaczącą $\nwd (a,b)$ i $\nww (a,b)$.

Wniosek 2.2.9 ( zależność między $\nwd $ i $\nww $). Dla liczb $a$, $b\in \N $ zachodzi równość: $\nwd (a,b)\cdot \nww (a,b)=ab$.

Przedstawimy teraz metodę, która umożliwia rozwiązywanie liniowych równań diofantycznych. Dokładniej, przez liniowe równanie diofantyczne będziemy rozumieć równanie postaci:

\[ax+by=c,\]

gdzie $a, b, c$ są ustalonymi liczbami całkowitymi, zaś rozwiązań $x, y$ poszukujemy w liczbach całkowitych.

Twierdzenie 2.2.10 ( istnienie i postać rozwiązań liniowego równania diofantycznego). Z: Niech $a, b, c\in \Z $ i załóżmy, że $ab\neq 0$.

T:
- (1) Liniowe równanie diofantyczne $ax+by=c$ posiada rozwiązanie w liczbach całkowitych $x, y$, wtedy i tylko wtedy, gdy $d=$NWD$(a,b)|c$.
- (2) Jeśli $(x_{0}, y_{0})$ jest dowolnym rozwiązaniem równania $ax+by=c$, to każde inne rozwiązanie jest postaci
  
  \[ x=x_{0}+\frac {b}{d}t,\quad y=y_{0}-\frac {a}{d}t, \]
  
  dla pewnego $t\in \Z $.

Dowód. Pierwsza część naszego twierdzenia jest natychmistowym wnioskiem z twierdzenia 2.2.7.

By dowieść drugiej części na początek zauważmy, że dla dowolnej liczby całkowitej $t$ mamy

\[ a\left (x_{0}+\frac {b}{d}t\right )+b\left (y_{0}-\frac {a}{d}t\right )=ax_{0}+by_{0}=c. \]

Oznacza to, że para $\left (x_{0}+\frac {b}{d}t,y_{0}-\frac {a}{d}t\right )$ również jest rozwiązaniem naszego równania.

Niech teraz $(X,Y)$ będzie całkowitym rozwiązaniem równania $ax+by=c$, tzn. $aX+bY=c$. Mamy zatem, że $aX+bY=c=ax_{0}+by_{0}$ i w konsekwencji

\[ a(X-x_{0})=b(y_{0}-Y)\;\mbox {lub rÃşwnowaÅĳnie}\;\frac {a}{d}(X-x_{0})=\frac {b}{d}(y_{0}-Y). \]

Ponieważ $\nwd (a/d,b/d)=1$, więc $\frac {a}{d}|y_{0}-Y$ oraz $\frac {b}{d}|X-x_{0}$. Onzacza to, że istnieje taka liczba całkowita $t$, że spełnione są równości

\[ t=\frac {y_{0}-Y}{\frac {a}{d}}=\frac {X-x_{0}}{\frac {b}{d}}. \]

Innymi słowy $X=x_{0}+\frac {b}{d}t, Y=y_{0}-\frac {a}{d}t$, co kończy dowód naszego twierdzenia.

□

Przykład 2.2.11. By pokazać teraz działanie (rozszerzonej wersji) algorytmu Euklidesa w akcji rozwiążemy liniowe równanie diofantyczne

\[ 720x+546y=12. \]

By rowiązać powyższe równanie wyznaczymy najpierw $\nwd (720,546)$, a dokładniej takie liczby całkowite $x_{0}, y_{0}$, że $\nwd (720,546)= 720x_{0}+546y_{0}$. Zanim jednak to zrobimy zauważmy, że przedstawienie $\nwd $ dwóch liczb za pomocą kombinacji liczb wyjściowych można oczywiście uzyskać „wracając” krok po kroku drogą wykonywanego algorytmu Euklidesa. Jest to jednak czasochłonne, gdyż wymaga wielu operacji arytmetycznych. Procedurę tę można uprościć wyrażając w każdym kroku powstałą resztę jako kombinację liniową (o współczynnikach całkowitych) liczb $720$ i $546$.

Chcemy wyliczyć $\nwd (720, 546)$ oraz przedstawić tę liczbę w postaci Bezouta (tak nazywać będziemy poszukiwaną kombinację).

Wypiszmy, dla przejrzystości kolejne kroki w tabeli

720 546

720 1 0

546 0 1

.

Wiemy teraz, że $720=1\cdot 546+174$. Mnożąc drugi wiersz przez $1$ i odejmujemy od pierwszego dostajemy

720 546

546 0 1

174 1 -1

.

Otrzymaliśmy zatem przedstawienie reszty: $174=1\cdot 720+(-1)\cdot 546$ w postaci kombinacji wyjściowych liczb. Dalej powtarzamy procedurę zgodnie z algorytmem Euklidesa i otrzymujemy równość $546=3\cdot 174+24$. Ponownie więc mnożymy drugi wiersz ostatniej tabeli przez $3$ i odejmujemy od pierwszego otrzymując

720 546

174 1 -1

24 -3 4

,

i w konsekwencji dostajemy równość $24=(-13)\cdot 720+4\cdot 546$. Kontynuujemy nasze rozumowanie wykorzystując równość $174=7\cdot 24+6$ i otrzymujemy

720 546

24 -3 4

6 22 -29

.

Po wydzieleniu $24$ przez $6$ jako resztę otrzymamy zero, wobec tego $\nwd (720,546)=6$ i otrzymaliśmy też przedstawienie $6=22\cdot 720+(-29)\cdot 546$. Mamy zatem, że para $(X_{0},Y_{0})=(22, 29)$ jest rozwiązaniem równania $720X+546Y=6$. W konsekwencji, para $(x_{0},y_{0})=(44,-58)$ jest szczególnym rozwiązaniem naszego wyjściowego równania, zaś ogólne rozwiązanie ma postać

\[ x=44+91t,\quad y=-58-120t. \]

¹ Zauważmy, że stwierdzenie największa liczba ma tutaj sens: rozważamy naturalny porządek w zbiorze liczb całkowitych, zaś potencjalne dzielniki są ograniczone z góry przez $|a_i|$

² Euklides: matematyk grecki, głównie działający w Aleksandrii, (ok.364-300 p.n.e. dokładne daty nie są znane), autor jednego z najbardziej znanych dzieł matematycznych: Elementy

³ Nazwa algorytm pochodzi od brzmienia fragmentu nazwiska arabskiego matematyka Muhammada ibn Musa al.-Chorezmiego, którego uznaje się za prekursora metod obliczeniowych w matematyce. Żył on na przełomie VIII i IX wieku, przyczynił się do upowszechnienia systemu dziesiętnego oraz wprowadził stosowanie zera jako symbolu oznaczającego ”nic”

Algebra

2.3 O liczbach pierwszych i ich własnościach

W niniejszej podrozdziale podamy podstawowe informacje i własności dotyczące liczb pierwszych. Liczby pierwsze można widzieć jako podstawowe składniki, z których zbudowane są liczby cakowite.

Definicja 2.3.1 ( liczba pierwsza). Liczbę całkowitą $p\in \Z $ nazywamy liczbą pierwszą, jeśli spełnione są następujące warunki:
- (1) $p>1$;
- (2) $\forall d\in \N :\;d|p\;\Longrightarrow \; d=1\;\mbox {lub}\; d=p$.
Zbiór wszystkich liczb pierwszych oznaczamy dalej przez $\mathcal {P}$.

Każdą liczbę naturalną większą od jedynki, nie będącą liczbą pierwszą nazywamy liczbą złożoną.

Pamiętajmy dalej o umowie, iż liczba jeden nie jest ani liczbą pierwszą ani też liczbą złożoną.

Definicja liczby pierwszej i proste zastosowanie identyczności Bezouta prowadzi nas do następującego wniosku.

Własność 2.3.2 ( podstawowe własności liczb pierwszych).
- (1) Jeśli $p\in \mathcal {P}$, $k\in \Z $, to $\nwd (p,k)=1$ lub $\nwd (p,k)=p$.
- (2) Jeśli $p\in \mathcal {P}$, $k_1,\ldots , k_n\in \Z $, $p|k_1\cdot \ldots \cdot k_n$, to $p|k_i$ dla pewnego $i=1,\ldots , n$.

Warto zaznaczyć, że własność 2.3.2 charakteryzuje liczby pierwsze. Dokładniej, stosując tę własność można wprowadzić definicję liczby pierwszej. Jest to o tyle ciekawe z naszego punktu widzenia, że w przyszłości własność „braku istotnego rozkładu” elementu (jak to jest w przypadku liczby pierwszej, gdzie rozkłada się ona wyłącznie na iloczyn $p\cdot 1$, względnie $(-p)\cdot (-1)$) oraz 2.4.2(2) okażą się być nierównoważne w ogólniejszych strukturach. Te problemy doprowadzą nas do definicji odpowiednio elementów nierozkładalnych i elementów pierwszych, (por. III).

Własność 2.3.2(2) w wersji dla $n=2$ to nic innego jak wspomniany wcześniej Lemat Euklidesa, który pojawia się w VII Księdze Elementów, sformułowany dla przypadku dwóch liczb. Gauss ⁴ w swoim dziele Disquisitiones arithmeticae wypowiada lemat Euklidesa i dowodzi przy jego pomocy twierdzenie o rozkładzie liczb całkowitych na liczby pierwsze, z którego to twierdzenia bezpośrednio wynika też gaussowskie uogólnienie lematu Euklidesa. Jak się często podkreśla „lemat Gaussa” pojawia się już jednak wcześniej w pracy Nouveaux éléments de mathématiques Jeana Presteta ⁵ z XVII wieku.

Definicja, którą teraz wprowadzimy może razić przerostem formy nad treścią. Znów wytłumaczeniem niech będą nasze przyszłe zamierzenia, gdzie słowo „ jedność” oznaczać będzie znacznie szerszą klasę elementów niż jest to w przypadku zbioru $\Z $.

Definicja 2.3.3 ( jedność w $\Z $). Jednościami w $\Z $ nazywamy liczby $-1$ i $1$. Zbiór jedności w $\Z $ będziemy oznaczać przez $U(\Z ):=\{-1,1\}$.

Definicja 2.3.4 ( rozkład jednoznaczny). Niech $k\in \Z ^\star $. Mówimy, że $k$ posiada jednoznaczny rozkład na iloczyn liczb pierwszych, jeśli
- (1) istnieją $p_1,\dots ,p_r\in \mathcal {P}$, $u\in U(\Z )$ takie, że $k=u\cdot p_1\cdot \ldots \cdot p_r$;
- (2) dla dowolnych dwóch układów $p_1,\dots ,p_r\in \mathcal {P}$, $q_1,\dots ,q_s\in \mathcal {P}$, $u,v\in U(\Z )$ takich, że
  
  \[k=u\cdot p_1\cdot \ldots \cdot p_r=v\cdot q_1\cdot \ldots \cdot q_s\]
  
  mamy $r=s$ oraz istnieje taka funkcja $\sigma $ - bijekcja zbioru $\{1,\ldots , r\}$ na siebie, że: $\forall \ i\in \{1,\dots ,r\}: \ p_i=q_{\sigma (i)}$.

Twierdzenie 2.3.5 ( Zasadnicze twierdzenie arytmetyki). Każda niezerowa liczba całkowita, nie będąca jednością w $\Z $ posiada jednoznaczny rozkład na iloczyn liczb pierwszych.

Dowód. Wystarczy oczywiście wykazać twierdzenie dla liczb naturalnych większych od jedynki. W naturalny sposób dowód rozbija się na dwie części: wykazanie istnienia rozkładu i wykazanie jego jednoznaczności.

Istnienie. Indukcja względem $n$: dla $n=2$ teza jest spełniona.

Załóżmy, że teza jest spełniona dla takich liczb naturalnych $m$, że $1<m<n$. Jeśli $n$ jest liczbą pierwszą, to dowód jest zakończony. Jeśli $n$ nie jest liczbą pierwszą, to $n=ab$, gdzie $1<a<n$ i $1<b<n$. Wobec tego, z założenia indukcyjnego liczby $a$ i $b$ są liczbami pierwszymi bądź iloczynami liczb pierwszych. W konsekwencji $n$ również jest iloczynem liczb pierwszych.

Jednoznaczność. Ponownie indukcja względem $n$.

Dla $n=2$ jednoznaczność rozkładu jest oczywista ze względu na pierwszość tej liczby. Gdyby bowiem było $n=p_1\cdot \ldots \cdot p_r$ gdzie $p_i\in \mathcal {P}$ i $r>1$, to $2$ musiałaby dzielić jedną z liczb $p_i$ a tym samym być jej równa (wobec pierwszości). Wtedy dzieląc obie strony przez $2$ mielibyśmy, że pozostałe liczby pierwsze $p_j$ dzielą jedynkę co jest niemożliwe. Wobec tego $r=1$ i $p_1=2$.

Zakładając tezę dla liczb mniejszych lub równych $(n-1)$, gdzie $n>2$ przypuśćmy, że dla $n$, mamy dwa rozkłady:

\[ n=p_1\cdot \ldots \cdot p_r=q_1\cdot \ldots \cdot q_s, \]

gdzie $p_i, q_j\in \mathcal {P}$ oraz $p_1\leqslant \ldots \leqslant p_r$, $q_1\leqslant \ldots \leqslant q_s.$ Oczywiście możemy przyjąć, że $r>1$. Istotnie, w przeciwnym razie mamy do czynienia z liczbą pierwszą i teza zachodzi. Niech zatem $p$ będzie najmniejszą liczbą pierwszą dzielącą $n$. Oznacza to, że $p$ dzieli $p_i$ dla pewnego $i$,
(2.3.2(2)). W konsekwencji $p=p_i$ i z minimalności $p$ otrzymujemy równość $p=p_1$. Rozumując analogicznie dostajemy $p=q_1$.

Niech teraz $m:=\f {n}{p}<n$. Wobec tego mamy rozkład:

\[ m=p_2\cdot \ldots \cdot p_r=q_2\cdot \ldots \cdot q_s. \]

Z założenia indukcyjnego otrzymujemy $r=s$ i istnieje taka bijekcja $\widetilde \sigma $ zbioru $\{2,\ldots , n\}$ na siebie, (permutacja tego zbioru), że $\forall \ i\in \{2,\dots ,r\}$ $p_i=q_{\widetilde \sigma (i)}$. Przyjmując $\sigma (1)=1$, $\sigma (i)=\widetilde \sigma (i)$, dla $i>1$ otrzymujemy poszukiwaną permutację zbioru $\{1,\ldots , n\}$.

□

Twierdzenie 2.3.6 ( Euklides). Istnieje nieskończenie wiele liczb pierwszych.

Dowód. Dla dowodu niewprost przypuśmy, że $\mathcal {P}=\{p_1,\dots , p_r\}$ i zdefinujmy liczbę $M:=p_1\cdot \ldots \cdot p_r+1$. Jest jasne, że żadna z liczby $p_{1},\ldots , p_{r}$ nie dzieli $M$. W przeciwnym razie liczba 1 byłaby podzielna przez liczbę pierwszą. Niech zatem $p$ będzie liczbą pierwszą dzielącą $M$, (taka istnieje na mocy 2.3.5). Wobec tego $p\notin \mathcal {P}$ i $p$ jest liczbą pierwszą, co prowadzi do sprzeczności. □

Skoro już wiemy, że liczb pierwszych jest nieskończenie wiele powstaje naturalne pytanie: jak wiele jest liczb pierwszych $\leq x$, gdzie $x$ jest ustaloną liczbą rzeczywistą? Innymi słowy interesuje nas szybkość wzrostu funkcji

\[ \pi (x)=|\{p:\;p\leq x\;\mbox {oraz}\;p\in \mathcal {P}\}|. \]

Funkcja $\pi (x)$ nazywana jest funkcją zliczającą liczby pierwsze. Gauss przypuszczał, zaś J. Hadamard ⁶ i Ch. J. de la Vallée-Poussin ⁷ udowodnili niezależnie tzw. Twierdzenie o liczbach pierwszych, tj. równość

\[ \lim _{x\rightarrow +\infty }\frac {\pi (x)\log x}{x}=1. \]

Dowód tego twierdzenia wymaga zastosowaniu zaawansowanego aparatu funkcji analitycznych. Można jednak podać zupełnie elementarny dowód dolnego oszacowania na funkcję $\pi (x)$, które wymaga tylko podstawowych własności liczb całkowitych. Dokładniej pokażemy dowód Erdősa⁸ następującego twierdzenia.

Twierdzenie 2.3.7. Dla $n\in \N $ prawdziwa jest nierówność

\[ \pi (n)\geq \frac {\log n}{2\log 2}. \]

Dowód. Zanim rozpoczniemy dowód przypomnijmy, że liczba naturalna nazywana jest bezkwadratową, jeśli nie jest podzielna przez kwadrat żadnej liczby pierwszej. Oznaczmy zbiór liczb bezkwadratowych przez $B$.

Dla $n\in \N $ rozważmy zbiór

\[ A(n)=\{(a,b)\in \N \times B:\;a^2b\leq n\} \]

i zauważmy, że $|A(n)|=n$. Istotnie, każdą liczbą naturalną $m$ można jednoznacznie zapisać w postaci $m=a^2b$, gdzie $a\in \N $ i $b\in B$.

Jeśli $(a,b)\in A(n)$, to mamy oczywiście $a^2\leq n$ i $b\leq n$, i w konsekwencji $a\leq \sqrt {n}$. Ponadto liczba $b$ jest bezkwadratowa, więc jest iloczynem różnych liczb pierwszych, z których każda jest $\leq n$. Oznacza to, że $b$ daje sie zapisać jako iloczyn liczb liczb ze zbioru $\{p_{1},p_{2},\ldots ,p_{\pi (n)}\}$. Możliwych iloczynów mamy $2^{\pi (n)}$. Podsumowując nasze rozważania widzimy, że jeśli $(a,b)\in A(n)$, to mamy co najwyżej $\sqrt {n}$ możliwych wyborów liczby $a$ oraz $2^{\pi (n)}$ możliwych postaci liczby $b$. Stąd $|A(n)|<\sqrt {n}2^{\pi (n)}$, ale $|A(n)|=n$, więc ostatecznie $n\leq \sqrt {n}2^{\pi (n)}$ i w konsekwencji

\[ \pi (n)\geq \frac {\log n}{2\log 2}. \]

□

W tej chwili istnieje całe multum dowodów nieskończoności zbioru wszystkich liczb pierwszych. Zaprezentowany powyżej dowód, w dość podobnej wersji jak w Elementach jest uznawany za pierwszy zapisany dowód przeprowadzony metodą niewprost i choćby z tego powodu jest tym dowodem, z którym warto się zapoznać.
Liczby pierwsze obecnie to punkt wyjścia do analizy całego bogactwa problemów nie tylko stricte teorioliczbowych, o których nie sposób opowiedzieć w kilku słowach. Wspomnieć jednak wypada o wciąż udoskonalanych testach pierwszości, których celem jest zbadanie pierwszości zadanej liczby, (nie zaś jej rozkład na liczby pierwsze co jest zagadnieniem znacznie trudniejszym). Już w okolicach 200 p.n.e. grecki matematyk Eratosthenes ⁹wprowadził metodę wyznaczania liczb pierwszych nie większych od ustalonej liczby $n$ zwaną odtąd ”sitem Eratosthenesa”. Jej działanie jest niezwykle proste - wypisujemy wszystkie liczby od 2 do $n$ następnie zakreślamy 2 jako liczbę pierwszą i wykreślamy jej wszystkie wielokrotności. Potem zakreślamy pierwszą pozostałą liczbę i wykreślamy wszystkie jej wielokrotności i tak kontynuujemy aż nie ma ”nietkniętych” liczb mniejszych lub równych od $\sqrt n$. W ten sposób otrzymamy tablicę liczb pierwszych nie większych od liczby wyjściowej.
Obecne, o wiele bardziej zaawansowane metody testowania pierwszości dzielą się na dwa rodzaje: testy deterministyczne i probablistyczne. Do tych pierwszych zaliczyć można m.in. test Lucasa-Lehmera, ¹⁰ (przy użyciu tego testu znaleziono największe liczby pierwsze, test dotyczy badania pierwszości tzw. liczb Mersenne’a) ¹¹, czy niektóre testy oparte na krzywych eliptycznych. Testy probablistyczne, choć nie pozwalają na zdecydowanie z pewnością, czy dana liczba jest pierwsza mają tę przewagę, że zwykle są dużo szybsze od testów deterministycznych. Liczby, którym udaje się przejść pozytywnie test probablistyczny, ale mimo to okazują się być jednak liczbami złożonymi znane są w kontekście liczb "pseudopierwszych". Istnieje wiele różnych rodzajów takich liczb, z których bodaj najbardziej znane to liczby pseudopierwsze Fermata, które mimo iż pozostają liczbami złożonymi to spełniają założenia Małego Twierdzenia Fermata, o którym opowiemy dalej. Przy okazji testów probablistycznych wypada wspomnieć o dwóch testach: teście Rabina-Millera, który jest wyjątkowo efektywnym testem probablistycznym oraz o tzw. teście AKS (od nazwisk twórców: Manindra Agrawala, Neeraja Kayala i Nitina Saxena, 2002), który to test deterministyczny sprawdza pierwszość zadanej liczby w czasie wielomianowym, słowem jego czas działania jest ograniczony za pomocą zależności wielomianowej od rozmiaru danych wejściowych. Do czasu pojawienia się tego testu zasadniczo nie było dowodu na to, iż test pierwszości zadanej liczby jest problemem rozwiązywalnym w czasie wielomianowym mimo, iż uważano że taka możliwość istnieje.

⁴ Carl Friedrich Gauss: matematyk, fizyk i astronom niemiecki, (1777-1855), nazywany „księciem matematyków”

⁵ Jean Prestet: matematyk francuski, (1648-1690)

⁶ Jacques Hadamard: matematyk francuski (1865–1963)

⁷ Charles Jean de la Vallée-Poussin: matematyk francuski (1866–1962)

⁸ Paul Erdős: matematyk węgierski, jednen z najwybitniejszych matematyków XX w. Autor ponad 1500 artykułów dotyczących głównie teorii liczb, kombinatoryki i teorii grafów (1913-1996)

⁹ Eratosthenes: grecki matematyk, poeta, geograf, astronom i filozof (276-194 p.n.e.)
¹⁰ Edouard Lucas, matematyk francuski 1842-1891, Derrick Henry Lehmer, matematyk amerykański, 1905-1991
¹¹ Liczby Mersenne’a: liczby postaci $2^p-1$, gdzie $p$ jest liczbą pierwszą, nazwane tak na cześć matematyka francuskiego Marina Mersenne’a, autora pierwszej tablicy liczb pierwszych tego typu, (niestety zawierającą błędy) - Marin Mersenne: matematyk, filozof i teolog francuski, (1588-1648)

Algebra

2.4 Kongruencje i ich własności, twierdzenie chińskie o resztach

Na pierwszej stronie swego dzieła Disquisitiones Arithmeticae Gauss wprowadza pojęcie „kongruencji”, czyli jak to określać będziemy dalej „przystawania”. Dzięki zastosowaniu tej notacji wiele własności i twierdzeń otrzymało prostszą postać, ale też znacznie ułatwiło to przeprowadzanie wielu operacji matematycznych.

Definicja 2.4.1 ( relacja przystawania modulo). Niech $m\in \N $. Mówimy, że liczby całkowite $k$, $l$ przystają modulo $m$, gdy $m|(k-l)$.

$\underline {\text { Oznaczenie:}}$ $k\equiv l (\text {mod}\ m)$.

Liczbę $m$ nazywa się modułem kongruencji.

Uwaga 2.4.2. Relacja przystawania modulo $m$ jest relacją równoważności w zbiorze liczb całkowitych.

Klasę równoważności liczby $k\in \Z $ względem relacji przystawania modulo $m$ oznaczamy przez $[k]_m$, zaś zbiór wszystkich klas równoważności w relacji przystawania modulo $m$ oznaczamy przez $\Z _m$. W dalszym ciągu wykładu często będziemy pisać po prostu $\Z _m=\{0,\ldots , m-1\}$, mając na myśli za każdym razem klasę równoważności reprezentowaną przez daną liczbę. Jest to poprawne, gdyż z algorytmu dzielenia z resztą wiemy, że liczby $0, \ldots , m-1$ wyczerpują wszystkie klasy równoważności.

Zauważmy, że relacja przystawania modulo jest zgodna z działaniami dodawania i mnożenia. Własności ta umożliwią w dalszej części wykładu wprowadzenia poprawnych działań w zbiorze $\Z _m$. Dokładniej, prawdziwe są następujące własności.

Własność 2.4.3 ( podstawowe własności kongruencji). Z: Niech $n\in \N $ oraz $k, l, k’, l’\in \Z $ będą takie, że $k\equiv k’\pmod {n}$ i $l\equiv l’\pmod {n}$.

T:
- (1) $k\pm l\equiv k’\pm l’\pmod {n}$,
- (2) $kl\equiv k’l’\pmod {n}$.

Dowód. Ćwiczenie. □

Z powyższej własności otrzymujemy natychmiastowy

Wniosek 2.4.4. Jeśli $f\in \Z [x]$ oraz $a, b\in \Z , m\in \N $ są takie, że $a\equiv b\pmod {m}$, to $f(a)\equiv f(b)\pmod {m}$.

Dowód. Niech $f(x)=\sum _{i=0}^{n}c_{i}x^{i}$. Jeśli $a\equiv b\pmod {m}$, to dla każdego $i\in \{0,\ldots ,n\}$ mamy, że

\[ a^{i}\equiv b^{i}\pmod {m}\;\mbox {oraz}\;c_{i}a^{i}\equiv c_{i}b^{i}\pmod {m}. \]

Dodając te kongruencje stronami otrzymujemy tezę naszego twierdzenia. □

Kolejny zestaw własności kongruencji znajdzie zastosowanie dalej przy rozwiązywaniu układów równań kongruencji. Własności te łatwo wynikają z zastosowania zasadniczego twierdzenia arytmetyki 2.3.5 lub np. tożsamości Bezouta 2.2.4.

Własność 2.4.5 ( własności kongruencji).
- (1) Jeśli $k,l\in \Z $, $m\in \Z ^\star $ są takie, że $m|kl$ oraz $m$ i $k$ są względnie pierwsze, to $m|l$. (lemat Gaussa)
- (2) Jeśli $a, m\in \N $, $k, l\in \Z $, to $ak\equiv al\pmod {am} \Longleftrightarrow k\equiv l\pmod {m}$,
- (3) Jeśli $m\in \N $, $a, k, l\in \Z $ są takie, że NWD$(a,m)=d$ i $ak\equiv al\pmod {m}$, to $k\equiv l \pmod {\frac {m}{d}}$.
- (4) Jeśli $a_1,\dots ,a_r\in \Z $, oraz liczba $k\in \Z $ jest względnie pierwsza z $a_i$ dla $i=1,\dots , r$, to $k$ jest względnie pierwsza z iloczynem $a_1\cdot \ldots \cdot a_r$.
- (5) Jeśli liczby $m_1,\dots ,m_r\in \Z ^\star $ są parami względnie pierwsze oraz $k\in \Z $ jest taka, że $m_i|k$ dla każdego $i=1,\dots ,r$, to $m_1\cdot \ldots \cdot m_r|k$.

Dowód. Ćwiczenie. □

Przejdziemy teraz do rozważania równań oraz układów kongruencji. Łatwo sprawdzić, że kongruencja postaci $ax\equiv b\pmod {m}$ posiada rozwiązanie całkowite wtedy i tylko wtedy, gdy $\nwd (a,m)|b$.

Własność 2.4.6 ( rozwiązanie kongruencji liniowej). Niech $a$, $b\in \Z $, $m\in \N $ i połóżmy $d=\nwd (a,m)$. Kongruencja $ax\equiv b\pmod {m}$ ma rozwiązanie całkowite wtedy i tylko wtedy, gdy $d|b$. Jeśli $d|b$, to kongruencja $ax\equiv b\pmod {m}$ ma dokładnie $d$ niekongruentnych rozwiązań całkowitych $x_{i}=x_{0}+\frac {m}{d}i, i=0,1,\ldots ,d-1$, gdzie $x_{0}$ jest jakimkolwiek rozwiązaniem.

Dowód. Zauważmy, że istnienie rozwiązania naszej kongruencji jest równoważne temu, że istnieje $x\in \Z $ takie, że $m|ax-b$ co z kolei jest równoważne stwierdzeniu, iż istnieje $y\in \Z $ takie, że $ax-b=my$ czyli $ax-my=b$. Równanie to ma rozwiązanie wtedy i tylko wtedy, gdy $d|b$ co jest konsekwencją twierdzenia 2.2.10. Jeśli teraz para $(x_{0}, y_{0})$ jest szczególnym rozwiązaniem równania $ax-b=my$, to korzystająć ponownie z tw. 2.2.10 otrzymujemy, że każde inne rozwiązanie spełnia warunki

\[ x\equiv x_{0}\left (\mymod {\frac {m}{d}}\right ),\quad y\equiv y_{0}\left (\mymod {\frac {m}{d}}\right ). \]

Zauważmy, że liczby

\[ x_{0},\quad x_{0}+\frac {m}{d},\;\ldots ,\;x_{0}+\frac {(d-1)m}{d} \]

są niekongruentne modulo $m$. Istotnie, jeśli $x_{0}+\frac {im}{d}\equiv x_{0}+\frac {jm}{d}\pmod {m}$ dla pewnych $i, j\in \{0,\ldots ,d-1\}$, to $i\equiv j\pmod {d}$, co oznacza, że $i=j$ i dotajemy sprzeczność. W konsekwencji każda z liczb $x_{0}+\frac {im}{d}$ dla $i\in \N $ przystaje do jednej z liczb $x_{0}+\frac {im}{d}$ dla $i\in \{0,\ldots ,d-1\}$ co kończy dowód naszego twierdzenia. □

W zastosowaniach często istnieje konieczność rozwiązywania układów kongruencji liniowych postaci

\[ u_{1}x\equiv v_{1}\pmod {m_{1}},\;u_{2}x\equiv v_{2}\pmod {m_{1}},\;\ldots ,\; u_{n}x\equiv v_{n}\pmod {m_{n}}, \]

gdzie $u_{i}, v_{i}\in \Z , m_{i}\in \N $ dla $i=1,\ldots , n$, są ustalone, zaś $x$ jest poszukiwaną liczbą. Jest jasne, że warunkiem koniecznym istnienia rozwiązania jest istnienie rozwiązania każdej z kongruencji wchodzącej w skład układu. Jest to równoważne koniunkcji warunków $\nwd (u_{i},m_{i})|v_{i}$ dla $i=1,2,\ldots ,n$. Oznacza to, że bez straty dla ogólności możemy założyć, że nasz układ ma postać

\[ x\equiv a_{1}\pmod {m_{1}},\; x\equiv a_{2}\pmod {m_{2}},\;\ldots ,\; x\equiv a_{n}\pmod {m_{n}}. \]

Możemy sformułować następujące ogólne

Twierdzenie 2.4.7 ( chińskie o resztach, TCR, wersja ogólna). Z: Niech $m_1,\dots ,m_n\in \N $ oraz $a_1,\dots ,a_n\in \Z $ będą ustalone.

T: Układ kongruencji

\[ x\equiv a_{1}\pmod {m_{1}},\; x\equiv a_{2}\pmod {m_{2}},\;\ldots ,\; x\equiv a_{n}\pmod {m_{n}} \]

ma rozwiązanie całkowite $x$ wtedy i tylko wtedy gdy dla dowolnych $i, j\in \{1,\ldots ,n\}, i\neq j$, spełniony jest warunek $\nwd (m_{i},m_{j})|(a_{i}-a_{j})$. Ponadto jeśli rozwiązanie istnieje to jest jedyne modulo $\nww (m_{1},\ldots ,m_{n})$.

Dowód. Na początek wykażamy, że sformułowany warunek jest konieczny. Istotnie, niech $i,j\in \{1,\ldots ,n\}, i\neq j$, i rozważmy kongruencje

\[ x\equiv a_{i}\pmod {m_{i}},\quad x\equiv a_{j}\pmod {m_{j}}. \]

Z pierwszej kongruencji dostajemy, że $x=a_{i}+m_{i}y$ dla pewnego $y\in \Z $. Wstawiając wyznaczoną wartość $x$ do drugiej kongruencji otrzymujemy kongruencję

\[ m_{i}y\equiv a_{j}-a_{i}\pmod {m_{j}}. \]

Kongruencja ta ma rozwiązanie wtedy i tylko wtedy, gdy $\nwd (m_{i},m_{j})|a_{i}-a_{j}$. Jeśli ten warunek jest spełniony, to $y$ jest wyznaczony jednoznacznie modulo $m_{j}/\nwd (m_{i},m_{j})$, zaś $x$ jest wyzaczony jednoznacznie modulo

\[ m_{i}m_{j}/\nwd (m_{i},m_{j})=\nww (m_{i},m_{j}). \]

Ponieważ własność ta musi zachodzić dla dowolnych $i, j\in \{1,\ldots ,n\}, i\neq j$, więc otrzymujemy konieczność naszego warunku.

Wykażemy teraz, że warunek $\nwd (m_{i},m_{j})|(a_{i}-a_{j})$ dla $i, j\in \{1,\ldots ,n\}, i\neq j$, jest również wystarczający. Rozważmy układ kongruencji

\[ x\equiv a_{1}\pmod {m_{1}},\quad x\equiv a_{2}\pmod {m_{2}} \]

i niech

\[ x\equiv a\pmod {\nww (m_{1},m_{2})} \]

będzie jej rozwiązaniem. Naszym celem jest wykazanie, że dla $i=3,\ldots ,n$ spełniony jest warunek $\nwd (m_{i},\nww (m_{1},m_{2}))|a_{i}-a$. Dla wygody obliczeń wprowadźmy oznaczenie $d_{i}:=\nwd (m_{i},\nww (m_{1},m_{2}))$. Niech $p\in \mathcal {P}$ będzie liczbą pierwwszą dzielącą $d_{i}$, zaś $\alpha $ będzie takie, że $p^{\alpha }||d_{i}$. Ponadto przez $\beta _{j}$ oznaczmy wykładnik liczby pierwszej $p$ w rozkładnie liczby $m_{j}$ na czynniki pierwsze dla $j=1,\ldots ,i$. Wiemy, że wykładnik $p$ w rozkładzie $\nww (m_{1},m_{2})$ wynosi $\max \{\beta _{1},\beta _{2}\}$. W konsekwencji dostajemy, że

\[ \alpha =\min \{\beta _{i},\max \{\beta _{1},\beta _{2}\}\}=\max \{\min \{\beta _{1},\beta _{i}\},\min \{\beta _{2},\beta _{i}\}\}. \]

Z założenia widzimy, że

\[ p^{\min \{\beta _{1},\beta _{i}\}}|(a_{1}-a_{i}),\quad p^{\min \{\beta _{2},\beta _{i}\}}|(a_{2}-a_{i}). \]

Ponieważ $p^{\beta _{k}}|(a_{k}-a)$ oraz $a_{k}-a_{i}=(a_{k}-a)+(a-a_{i})$ dla $k=1, 2$, otrzymujemy

\[ p^{\min \{\beta _{1},\beta _{i}\}}|(a_{i}-a),\quad p^{\min \{\beta _{2},\beta _{i}\}}|(a_{i}-a), \]

i w konsekwencji $p^{\alpha }|(a_{i}-a)$. Ponieważ $p^{\alpha }$ była dowolna potęgą liczby pierwszej dzielącej $d_{i}$, więc musi być

\[ d_{i}=\nwd (m_{i},\nww (m_{1},m_{2}))|(a_{i}-a). \]

Udowodniliśmy zatem, że układ kongruencji

\[ x\equiv a_{1}\pmod {m_{1}},\quad x\equiv a_{2}\pmod {m_{2}} \]

jest równoważny kongruencji

\[ x\equiv a\pmod {\nww (m_{1},m_{2})}. \]

Oznacza to, że rozwiązanie pierwszych dwóch kongruencji naszego układu $n$ kongruencji jest wyznaczone jednoznacznie modulo $\nww (m_{1},m_{2})$. Dodając kongruencję $x\equiv a_{3}\pmod {m_{3}}$ i powtarzając rozumowanie otrzymamy rozwiązanie układu kongruencji $x\equiv a_{i}\pmod {m_{i}}, i=1,2,3$, które jest jednoznaczne modulo $\nww (m_{3},\nww (m_{1},m_{2}))=\nww (m_{1},m_{2},m_{3})$. Kontynuując w ten sposób otrzymujemy tezę naszego twierdzenia. □

Powyższe twierdzenie daje nam warunek konieczny i wystarczający istnienie rozwiązania układu kongruencji liniowych. Warto jednak zanotować i udowodnić inną metodą szczególną wersję twierdzenia 2.4.7, gdy moduły $m_{1},\ldots ,m_{n}$ są parami względnie pierwsze.

Twierdzenie 2.4.8 ( chińskie o resztach, TCR, wersja szczególna). ?? Z: Niech $m_1,\dots ,m_n\in \N $ - parami względnie pierwsze, $a_1,\dots ,a_n\in \Z $. T:
- (1) Istnieje $x\in \Z $ takie, że $x\equiv a_i \pmod {m_i}$ dla każdego $i=1,\dots ,n$.
- (2) Jeśli $x_{1}$, $x_{2}$ spełniają (1), to $x_{1}\equiv x_{2}\pmod {M}$, gdzie $M=m_1\cdot \ldots \cdot m_n$.

Dowód. Z twierdzenia 2.4.7 wiemy, że rozwiązanie rozważanego układu istnieje i jest jednoznaczne modulo $M:=\nww (m_{1},\ldots ,m_{n})=m_1\cdot \ldots \cdot m_n$. Pokażemy teraz w jaki sposób skonstruować szukane rozwiązanie $x$. Niech $s_i:=\f {M}{m_i}$. Wtedy $s_i$ jest iloczynem liczb $m_j$ dla $j\ne i$ wobec tego jest iloczynem liczb względnie pierwszych z $m_i$. Z 2.4.5(4) wynika, że również liczby $m_i$ i $s_i$ są względnie pierwsze. Wobec tego istnieją $u_1,\dots ,u_n, v_1,\dots ,v_n\in \Z $ takie, że

\[u_im_i+v_is_i=1\quad \mbox {dla}\quad i=1,\dots ,r.\]

Określmy teraz $x:=a_1(v_1s_1)+\ldots +a_n(v_ns_n).$ Wykażemy, że tak dobrane $x$ spełnia kongruencję $x\equiv a_{i}\pmod {m_{i}}$ dla $i=1,\ldots ,n$.

Ustalmy $i_0\in \{1,\dots , n\}$. Wtedy

\[ x-a_{i_0}=a_1(v_1s_1)+\ldots +a_{i_0}(v_{i_0}s_{i_0}-1)+\ldots +a_n(v_ns_n). \]

Mamy jednak $m_{i_0}|u_{i_0}m_{i_0}=x-v_{i_0}s_{i_0}$. Ponadto $s_i$ dla $i\ne i_0$ są podzielne przez $m_{i_0}$ czyli $x\equiv a_{i_0}$(mod$\ m_{i_0}$), czego oczekiwaliśmy.

Niech teraz $x’$ spełnia również tę kongruencję, to oznacza, że $x’-x$ jest podzielne przez każde $m_i$. Wobec tego z 2.4.5(5) wynika, że $x’-x$ jest podzielne przez iloczyn $m_1\cdot \ldots \cdot m_n$ i mamy tezę. □

Zaletą powyższego dowodu jest jego algorytmiczny charakter, gdyż każdy układ kongruencji rozważanej postaci o modułach względnie pierwszych może być rozwiązany w przedstawiony sposób. Jednakże, mankamentem tej metody jest liczba i wielkość obliczeń, które trzeba przeprowadzić by otrzymać poszukiwane rozwiązanie. Dlatego też w przypadku małych układów stosuje się metodę eliminacji kongruencji, które jest podobna do metody Gaussa eliminacji zmiennych, którą wykorzystuje się przy rozwiązywaniu układów równań liniowych. By podać przykład zastosowania tej metody rozważmy układ kongruencji

\[ \begin {cases} x\equiv 2 \pmod {3}\\ x\equiv 3 \pmod {5}\\ x\equiv 1 \pmod {7} \end {cases}. \]

Z pierwszej kongruencji dostajemy, że $x=3a+2$ dla pewnego $a\in \Z $. Wstawiając tak wyznaczoną wartość do drugiej kongruencji otrzymujemy $3a+2\equiv 3\pmod {5}$ lub równoważnie $3a\equiv 1\pmod {5}$. Po przemnożeniu stronami przez 2 dostajemy, że $a\equiv 2\pmod {5}$, co implikuje, że $a=5b+2$ i $x=3(5b+2)+2=15b+8$ dla pewnego $b\in \Z $. Pozostaje nam zatem kongruencja $15b+8\equiv 1\pmod {7}$ lub równoważnie, po redukcji modulo 7, $b\equiv 0\pmod {7}$. Ostatecznie $b=7c$ i tym samy $x=105b+8$, co oznacza, że najmniejszym dodatniem rozwiązaniem naszego układu jest $x=8$.

Przedstawione podejście może być zastosowane również do układów kongruencji, których moduły nie są parami względnie pierwsze. Jeśli rozważany układ ma rozwiązanie (co oznacza, że warunek konieczny i wystarczający przedstawiony w sformułowaniu twierdzenia 2.4.7 zachodzi), to znajdziemy je eliminując kongruencje jedna po drugiej. Alternatywna metoda polega na sprowadzeniu rozważanego układu do sytuacji, gdy moduły są parami względnie pierwsze. Przykładowo rozważmy układ kongruencji

\[ \begin {cases} x\equiv 7 \pmod {8}\\ x\equiv 9 \pmod {10}\\ x\equiv 14 \pmod {15} \end {cases} \]

Układ ten jest równoważny następującym

\[ \begin {cases} x\equiv 7 \pmod {8}\\ x\equiv 9 \pmod {2}\\ x\equiv 9 \pmod {5}\\ x\equiv 14 \pmod {3}\\ x\equiv 14 \pmod {5} \end {cases} \Longleftrightarrow \begin {cases} x\equiv 7 \pmod {8}\\ x\equiv 4 \pmod {5}\\ x\equiv 2 \pmod {3} \end {cases}. \]

Moduły ostatniego układu są parami względnie pierwsze i oczywiście cały układ ma rozwiązanie (co może być również potwierdzone stosując twierdzenie 2.4.7).

Algebra

2.5 Funkcja Eulera, jej własności i zastosowania

W tym podrozdziale zapoznamy się z najważniejszą dla dalszych zastosowań, (w szczególności w teorii grup oraz w wykorzystaniu dalej m.in. w teorii ciał i teorii Galois) funkcją arytmetyczną ¹². Funkcję tę można definiować na różne sposoby, ale postawimy tu standardową definicję teorioliczbową.

Definicja 2.5.1 ( funkcja Eulera). Niech $\varphi : \N \str \N $ będzie funkcją przypisującą liczbie $n$ liczbę liczb $k\in \{1,\ldots n\}$ względnie pierwszych z $n$, tzn.

\[ \varphi (n)=\#\{k\in \{1,\ldots ,n\}:\;\nwd (k,n)=1\} \]

Funkcję $\varphi $ nazywamy funkcją Eulera.

Własność 2.5.2 ( podstawowe własności funkcji Eulera).
- (1) $\varphi (1)=1$, (jeden jest względnie pierwsze z jedynką).
- (2) Niech $p$ - liczba pierwsza. Wtedy: $\varphi (p)=p-1=p(1-\f {1}{p})$.
- (3) Niech $p$ - liczba pierwsza, $k\in \N $. Wtedy $\varphi (p^k)=p^{k}-p^{k-1}=p^{k}(1-\f {1}{p})$, gdyż mamy $p^{k-1}$ liczb całkowitych takich, że $1\leqslant l<p^k$, które są podzielne przez $p$.

Przypomnijmy, że funkcja arytmetyczna $f:\;N\rightarrow \C $ jest multiplikatywna wtedy i tylko wtedy gdy dla dowolnych względnie pierwszych $m, n\in \N $ spełniona jest równość $f(mn)=f(m)f(n)$. Udowodnimy teraz, że funkcja $\phi $ Eulera jest multiplikatywna.

Twierdzenie 2.5.3 ( multiplikatywność funkcji Eulera). Z: $m,n\in \N $ - względnie pierwsze. T: $\varphi (mn)=\varphi (m)\varphi (n)$.

Dowód. Niech

\[ I:=\{k\in \{1,\ldots ,m\}:\; \nwd (k,m)=1\},\quad J:=\{l\in \{1,\ldots ,n\}: \; \nwd (l,n)=1\} \]

oraz

\[ A:=\{s\in \{1,\ldots , m\cdot n\}: \; \nwd (s,m\cdot n)=1\}. \]

Wtedy oczywiście $\#(I\times J)=\varphi (m)\varphi (n)$, zaś $\#(A)=\varphi (mn)$. Skonstruujemy bijekcję między zbiorami $I\times J$ i $A$.

Zgodnie z twierdzeniem chińskim o resztach dla dowolnej pary liczb $(k,l)\in I\times J$ istnieje dokładnie jedna liczba $z_{k,l}\in \{1,\ldots ,mn\}$ spełniająca warunki

\[ \begin {cases} z_{k,l}\equiv k\pmod {m}\\ z_{k,l}\equiv l\pmod {n} \end {cases}\]

(jedyność wynika z żądania, aby $z_{k,l}\in \{1,\ldots ,mn\}$. Liczba ta jest względnie pierwsza z $m$ (bo $k$ była) oraz z $n$ (bo $l$ była) stąd jest względnie pierwsza z $mn$. Mamy więc dobrze określone odwzorowanie:

\[ \Phi : I\times J\ni (k,l)\str z_{k,l}\in A. \]

(1) Wykażemy, że $\Phi $ jest injekcją. Niech bowiem $z_{k,l}=z_{k’,l’}$ i na przykład $1\leqslant k<k’\leq m$. Wtedy $m|(z_{k,l}-k)$ i $m|(z_{k,l}-k’)$, skąd $m|(k’-k)$, co prowadzi do sprzeczności. (2) By dokończyć dowód wykażemy, że $\Phi $ jest surjekcją. Jeśli $z\in A$, to $z=\Phi (k,l)$ gdzie $k:=z\pmod {m}$ oraz $l:=z\pmod {n}$. Łatwo sprawdzić, że $(k,l)\in I\times J$. Wobec tego $\varphi (m)\varphi (n)=\#(I)\cdot \#(J)=\#(I\times J)=\# (A)=\varphi (mn)$ i dostajemy tezę. □

Wniosek 2.5.4. Jeśli $n\in \N $, to $\varphi (n)=n\prod \limits _{p|n}(1-1/p)$, gdzie iloczyn bierzemy po liczbach pierwszych dzielących $n$.

Dowód. Jeśli $n=p_1^{k_1}\cdot \ldots \cdot p_r^{k_r}$, gdzie $p_1,\ldots , p_r$ to parami różne liczby pierwsze oraz $k_1,\ldots , k_r>0$, to

\[ \varphi (n)=\varphi (p_1^{k_1})\cdot \ldots \cdot \varphi (p_r^{k_r})=p_1^{k_1}\left (1-\frac {1}{p_1}\right )\cdot \ldots \cdot p_r^{k_r}\left (1-\frac {1}{p_r}\right )=n\prod \limits _{i=1}^r\left (1-\frac {1}{p_i}\right ).\]

□

Udowodnimy teraz własność funkcji Eulera, która zostanie wykorzystana w ostatniej części wykładu przy badaniu własności grupy multiplikatywnej ciała skończonego.

Własność 2.5.5. Dla każdego $n\in \N $ prawdziwa jest równość $\sum \limits _{d|n}\varphi (d)=n$, gdzie sumujemy po wszystkich dodatnich dzielnikach $n$.

Dowód. Zauważmy, że jeśli $k\in \{1,\ldots , n\}$, to $\nwd (n,k)=n/d$ dla pewnego dzielnika $d$ liczby $n$. Jeżeli teraz:

\[ n_d:=\#\{k\in \N :\; k<n, \nwd (n,k)=n/d\}, \]

to $n=\sum \limits _{d|n}n_d$. Niech teraz liczba $k\in \{1,\ldots , n\}$ będzie taka, że $\nwd (n,k)=n/d=l$. Wtedy $k=lm$ dla pewnego $m<d$ oraz z równości $\nwd (n,k)=l$ otrzymujemy $\nwd (m,d)=l$. Oznacza to, że czyli liczby $k\in \{1,\ldots , n\}$ spełniające warunek $\nwd (n,k)=l$ są postaci $lm$, gdzie $m\in \{1,\ldots , d\}$ oraz $\nwd (m,d)=1$. Otrzymujemy stąd równość $n_d=\varphi (d)$. Łącząc oba fakty otrzymujemy tezę. □

¹² funkcja o dziedzinie $\Bbb N$ i wartościach zespolonych

Algebra

2.6 Małe twierdzenie Fermata, twierdzenie Eulera oraz twierdzenie Wilsona

W tym podrozdziale przedstawimy trzy podstawowe twierdzenia elementarnej teorii liczb: małe twierdzenie Fermata, twierdzenie Eulera i twierdzenie Wilsona. Zaczniemy od sformułowania tzw. "Małego Twierdzenia Fermata", którego w tym momencie dowodzić nie będziemy, ale któremu (wraz z wybranymi dowodami) poświęcimy osobną opowieść w aneksie. W tej chwili wykorzystamy fakt, że dziś możemy na niego patrzeć jak na wniosek z ogólniejszego twierdzenia Eulera, choć historycznie rzecz ujmując to MTF było pierwszą udowodnioną własnością. Więcej o tym „małym” wielkim twierdzeniu poczytać można w rozdziale ??.

Twierdzenie 2.6.1 ( Małe twierdzenie Fermata=MTF). Niech $p\in \mathcal {P}$ i $k\in \Z $.
- (1) Jeśli $\nwd (k,p)=1$, to $k^{p-1}\equiv 1\pmod {p}$.
- (2) Jeśli $\nwd (k,p)=p$, to $k^p\equiv k \pmod {p}$.

Nie prezentujemy dowódu powyższego twierdzenia, gdyż jest ono szczególnym przypadkiem ogólniejszego wyniku uzyskanego przez Eulera (nazywanego również czasem twierdzeniem Eulera-Fermata), które wykorzystuje wprowadzone wcześniej pojęcie funkcji Eulera. Zanim sformułujemy twierdzenie Eulera będzie nam potrzeba jeszcze jedna jedna definicja.

Definicja 2.6.2 (układ reszt, zredukowany układ reszt). Niech $n\in \N $ będzie ustalone. Układem reszt modulo $n$ nazywamy dowolny $n$ elementowy zbiór $U\subset \Z $ o tej własności, że dla dowolnego $i\in \{0,\ldots ,n-1\}$ istnieje dokładnie jeden element $u\in U$, że $i\equiv u\pmod {n}$.

Przykładowo, zbiór $\{-2,0,1,7\}$ jest układem reszt modulo 4.

Definicja 2.6.3 (zredukowany układ reszt). Niech $n\in \N $ będzie ustalone. Zredukowanym układem reszt modulo $n$ nazywamy dowolny $\phi (n)$ elementowy zbiór $U\subset \Z $ o tej własności, że dla dowolnego $i\in \{1,\ldots ,n\}, \nwd (i,n)=1$, istnieje dokładnie jeden element $u\in U$, że $i\equiv u\pmod {n}$.

Przykładowo, zbiór $\{-3,-2,1,9\}$ jest zredukowanym układem reszt modulo 5.

Jesteśmy gotowi by sformułować i udowodnić następujące.

Twierdzenie 2.6.4 ( Twierdzenie Eulera). Jeśli $m\in \N $, $k\in \Z $ oraz $\nwd (k,m)=1$, to $k^{\varphi (m)}\equiv 1\pmod {m}$.

Dowód. Niech $U_{m}:=\{a_{1},\ldots ,a_{\varphi (m)}\}$ będzie zredukowanym układem reszt modulo $m$. Zauważmy, że zbiór $kU_{m}=\{ka_{1},\ldots ,ka_{\phi (m)}\}$ również jest zredukowanym układem reszt modulo $m$. Jest to konsekwencja względnej pierwszości liczb $k$ i $m$. Oznacza to, że zachodzą związki

\[ \prod _{i=1}^{\varphi (m)}(ka_{i})=k^{\varphi (m)}\prod _{i=1}^{\varphi (m)}a_{i}\equiv \prod _{i=1}^{\varphi (m)}a_{i}\pmod {m}. \]

Ponieważ $\nwd \left (m,\prod _{i=1}^{\varphi (m)}\right )=1$, więc możemy podzielić skrajne strony powyższej kongruencji przez $\prod _{i=1}^{\varphi (m)}$ otrzymując w efekcie

\[ k^{\varphi (m)}\equiv 1\pmod {m}. \]

Na koniec zauważmy, ze jeśli $m=p$ jest liczbą pierwszą jak w sformułowaniu twierdzeniu Fermata, dostajemy dokładnie tezę tego twierdzenia, gdyż $\varphi (p)=p-1$.

□

Nasze wstępne rozważania teorio-liczbowe zakończymy następującym.

Twierdzenie 2.6.5 (twierdzenie Wilsona). Liczba $n\in \N $ jest pierwsza wtedy i tylko wtedy, gdy $(n-1)!\equiv -1\pmod {n}$.

Dowód. Jeśli $n=2$ lub $n=3$, to teza zachodzi. Załóżmy zatem, że $n\geq 4$. Jeśli $n$ jest liczbą złożoną, to jej wszystkie dzielniki znajdują się w zbiorze $A=\{1,2,\ldots ,n-1\}$. Rzecz jasna $\nwd ((n-1)!,n)>1$, co oznacza, że kongruencja $(n-1)!\equiv -1\pmod {n}$ jest niemożliwa. Jeśli $n$ jest liczbą pierwszą, to żadna z liczb $i\in A$ nie jest dzielnikiem $n$. Oznacza to, że $\nwd (i,n)=1$ dla $i\in A$. W konsekwencji, dla dowolnego $i\in A$ istnieje dokładnie jedna liczba $a_{i}\in A$, dla której $ia_{i}\equiv 1\pmod {n}$. Ponadto $i=a_{i}$ wtedy i tylko wtedy, gdy $i=1$ lub $i=n-1$ (bo $n$ jest liczbą pierwszą). Oznacza to, że pomijając liczby $i=1$ oraz $i=n-1$, zbiór $\{2,\ldots ,n-2\}$ można ustawić w pary różnych elementów o iloczynie równym 1, co prowadzi nas do kongruencji

\[ 2\cdot 3\cdot \ldots \cdot (n-2)\equiv 1\pmod {n}. \]

Mnożąc powyższą kongruencję stronami przez $n-1$ otrzymujemy

\[ (n-1)!\equiv n-1\equiv -1\pmod {n}, \]

co daje drugą część tezy i kończy dowód. □

Algebra

3 Działania i ich własności

Zanim zaczniemy omawiać podstawowe struktury algebraiczne wprowadzimy pojęcie działania oraz uporządkujemy własności działań, jakie możemy określić na wzór znanych działań liczbowych.

Definicja 3.0.1 ( działanie). Niech $X$ będzie zbiorem niepustym, zaś $X\times X:=\{(x,y): \ x\in X, y\in X\}$ iloczynem kartezjańskim tego zbioru przez siebie. Każde odwzorowanie przypisujące parze elementów z $X$, (czyli elementowi z $X\times X$) element z $X$:

\[\star : X\times X\ni (x,y)\str x\star y\in X\]

nazywamy działaniem na zbiorze $X$. (¹)

Przykład 3.0.2.
- $(1)$ $\Q \times \Q \ni (x,y)\str x\cdot y\in \Q $ jest działaniem na zbiorze liczb wymiernych, (iloczyn liczb wymiernych jest liczbą wymierną)
- $(2)$ $\N \times \N \ni (x,y)\str x-y\in \Z $ NIE jest działaniem na zbiorze $\N $ gdyż może parze liczb naturalnych przypisać liczbę ujemną.

Definicja 3.0.3 ( rodzaje działań). Niech $\star : X\times X\ni (x,y)\str x\star y\in X$ będzie działaniem na zbiorze $X$.
- $(1)$ Działanie $\star $ nazywamy łącznym, gdy $\forall \ x, y, z\in X: \ (x\star y)\star z=x\star (y\star z).$
- $(2)$ Działanie $\star $ nazywamy przemiennym, gdy $\forall \ x, y\in X: \ x\star y=y\star x.$
- $(3)$ Element $e\in X$ nazywamy elementem neutralnym działania $\star $ , gdy $\forall \ x\in X: \‚x\star e=e\star x=x.$ (²)
- $(4)$ Jeśli dla działania $\star $ istnieje element neutralny $e$, to dla dowolnego $x\in X$ element $\overline {x}$ nazywamy elementem symetrycznym do elementu $x$ względem działania $\star $, jeśli $x\star \overline {x}=\overline {x}\star x=e$. (³)
- $(5)$ Jeśli na zbiorze $X$ zadane są dwa działania: $\star $ oraz $\bullet $ to działanie $\bullet $ nazywamy rozdzielnym względem działania $\star ,$ gdy:
  
  \[\forall \ x, y, z\in X: \ (x\star y)\bullet z=(x\bullet z)\star (y\bullet z) \ i \ z\bullet (x\star y)=(z\bullet x)\star (z\bullet y).\]

¹ czasem fakt, że para punktów z $X$ przechodzi na punkt z $X$ nazywa się wewnętrznością działania

² uwaga: element neutralny nie zawsze musi istnieć, np. w $\N $ nie istnieje element neutralny dodawania

³ uwaga: element symetryczny może dla pewnych elementów istnieć, dla innych nie np. w zbiorze $\Z $ z działaniem mnożenia dla $1$ element symetryczny istnieje, ale nie istnieje np. dla $2$

3.1 Podstawowe przykłady działań

3.1.1 I. Kanoniczne przykłady liczbowe

$(1)$ Działania dodawania wprowadzone na zbiorach $\N $, $\Z $, $\Q $, $\R $, $\C $.
$(2)$ Działania mnożenia wprowadzone na zbiorach $\Q ^\star $, $\R ^\star $, $\C ^\star $.⁴

⁴ Wskazane działania można oczywiście wprowadzać także na innych zbiorach liczbowych (np. mnożenie możemy określić na zbiorze liczb całkowitych) - prezentujemy tu jednak umownie "kanonicznieżozumiane działania, które posiadają we wskazanych zbiorach szereg podstawowych własności

3.1.2 II. Działania w zbiorach macierzy

Bardzo ważnym typem działania jest działanie mnożenia na odpowiednio dobranych zbiorach macierzy. Najczęściej pracować będziemy z macierzami o wartościach liczbowych, (tzn. całkowitych, wymiernych, rzeczywistych lub zespolonych) ale rozważać będziemy też macierze o współczynnikach pochodzących np. z pierścieni reszt modulo.

Zbiór wszystkim macierzy kwadratowych wymiaru $n$ nad pewnym zbiorem liczbowym $A$ będziemy oznaczać przez $M_n(A)$. Na zbiorze tym rozważać będziemy domyślnie działanie dodawania macierzy.

Zbiór wszystkich macierzy nieosobliwych ⁵ wymiaru $n$ nad pewnym zbiorem liczbowym $A$ oznaczać będziemy $GL_n(A)$. W zbiorze tym rozważać będziemy domyślnie działanie mnożenia macierzy.

⁵ Pamiętamy, że macierz nieosobliwa to macierz o wyznaczniku różnym od zera

3.1.3 III. Zbiory odwzorowań i działania na nich

Definicja 3.1.1 ( permutacje zbioru).

Jeśli $X$ jest zbiorem niepustym, zaś $f: X\str X$ jest bijekcją zbioru $X$ na samego siebie, to odwzorowanie takie będziemy nazywać permutacją zbioru $X$.

Zbiór wszystkich permutacji zbioru $X$ będziemy oznaczać przez $S(X)$.

Szczególnym przypadkiem permutacji są permutacje zbioru skończonego.

Definicja 3.1.2 ( permutacje). Rozważmy zbiór $n$-elementowy: $\{1, 2, \ldots , n\}$. Każde odwzorowanie tego zbioru przypisujące jego elementowi dokładnie jeden element tego zbioru nazywać będziemy permutacją zbioru $\{1, \ldots , n\}$ i zwyczajowo oznaczać będziemy takie odwzorowania przez litery greckie np. $\sigma $. (⁶)

Każde z takich odwozorowań oznaczać będziemy dalej następująco:

\[\sigma =\left (\begin {array}{ccccc} 1 & 2 & \ldots & n \\ \sigma (1) & \sigma (2) & \ldots & \sigma (n) \end {array}\right )\]

gdzie oznaczenie to mówi, że nasze odwzorowanie $\sigma $ przeprowadza $1$ na $\sigma (1)$, $2$ na $\sigma (2)$ itd. aż do $n$ na $\sigma (n)$.

Zbiór permutacji zbioru $X$ będziemy rozważać domyślnie z działaniem składania tzn. $g\star f:= g\circ f$. Często, dla uproszczenia zamiast mówić śkładanie permutacji"będziemy stosować nazewnictwo "mnożenie permutacji"i zamiast pisać $\sigma \circ \tau $ napiszemy $\sigma \cdot \tau $ lub po prostu $\sigma \tau $.

Zbiór wszystkich permutacji zbioru $\{1,\ldots , n\}$ będziemy dalej oznaczać przez $S_n$.

⁶ Taka notacja przyjęła się za klasycznym podręcznikiem H.Wielandta,Finite Permutation Groups, Academic Press, New York, 1964

3.1.3.1 Tabela działania na zbiorze

Częstym sposobem zapisu działania na zbiorze skończonym jest tabela tego działania - tzw. tabliczka Cayleya. ⁷

Ułóżmy dla przykładu tabelę działania w zbiorze permutacji trzyelementowych.

Tabela działania składania/mnożenia permutacji $3$ elementowych $S_3=\{\sigma _1, \sigma _2, \ldots , \sigma _6\}$ gdzie $\sigma _1=\left (\begin {array}{ccccc} 1 & 2 & 3 \\ 1 & 2 & 3 \end {array}\right )$, $\sigma _2=\left (\begin {array}{ccccc} 1 & 2 & 3 \\ 2 & 1 & 3 \end {array}\right )$,
$\sigma _3=\left (\begin {array}{ccccc} 1 & 2 & 3 \\ 3 & 2 & 1 \end {array}\right )$, $\sigma _4=\left (\begin {array}{ccccc} 1 & 2 & 3 \\ 1 & 3 & 2 \end {array}\right )$, $\sigma _5=\left (\begin {array}{ccccc} 1 & 2 & 3 \\ 3 & 1 & 2 \end {array}\right )$,
$\sigma _6=\left (\begin {array}{ccccc} 1 & 2 & 3 \\ 2 & 3 & 1 \end {array}\right ).$

$\circ $	$\sigma _1$	$\sigma _2$	$\sigma _3$	$\sigma _4$	$\sigma _5$	$\sigma _6$
$\sigma _1$	$\sigma _1$	$\sigma _2$	$\sigma _3$	$\sigma _4$	$\sigma _5$	$\sigma _6$
$\sigma _2$	$\sigma _2$	$\sigma _1$	$\sigma _5$	$\sigma _6$	$\sigma _3$	$\sigma _4$
$\sigma _3$	$\sigma _3$	$\sigma _6$	$\sigma _1$	$\sigma _5$	$\sigma _4$	$\sigma _2$
$\sigma _4$	$\sigma _4$	$\sigma _5$	$\sigma _6$	$\sigma _1$	$\sigma _2$	$\sigma _3$
$\sigma _5$	$\sigma _5$	$\sigma _4$	$\sigma _2$	$\sigma _3$	$\sigma _6$	$\sigma _1$
$\sigma _6$	$\sigma _6$	$\sigma _3$	$\sigma _4$	$\sigma _2$	$\sigma _1$	$\sigma _5$

⁷ Arthur Cayley - matematyk i prawnik angielski (1821-1895) znany m.in. z prac na temat teorii grup. Pochodzi od niego m.in. dowód faktu, że każda grupa (zbiór z działaniem łącznym, dla którego istnieje element neutralny i każdy z elementów posiada symetryczny, 4.1.2) może być traktowana jako ćzęść"(formalnie: podgrupa 4.1.11) pewnej grupy permutacji.

3.1.4 IV. Kongruencje i działania modulo

Tę część trzeba przerobić odwołując się do części Teoria Liczb

Definicja 3.1.3 ( zbiór reszt modulo). Niech $m\in \N $, $k\in \Z $. Zbiór takich liczb całkowitych $l$ które dają tę samą resztę z dzielenia przez $m$ jak liczba $k$, (inaczej: $l\equiv k \pmod m$) nazywamy klasą równoważności liczby $k$ modulo $m$ i oznaczać ją będziemy dalej $[l]_m$. Zbiór wszystkich takich klas oznaczamy $\Z _m$.

Uwaga 3.1.4 ( uwagi notacyjne).
- $(i)$ Każdy ze zbiorów $\Z _m$ jest $m$-elementowy jako, że mamy $m$ różnych reszt z dzielenia przez $m$.
- $(ii)$ Często piszemy $\Z _m=\{0, 1, 2, \ldots , m-1\}$ zamiast $\Z _m=\{[0]_m, [1]_m, \ldots , [m-1]_m\}$ - pamiętać jednak należy, że wtedy oznaczenie $’0’$ mówi, że mamy na myśli wszystkie liczby podzielne przez $m$ itd.

Na zbiorze $\Z _m$ będziemy wprowadzać dwa działania: dodawania i mnożenia.

Definicja 3.1.5.
- $(i)$ Dla $[k]_m$, $[l]_m\in \Z _m$ definiujemy: $[k]_m+[l]_m:=[k+l]_m$
- $(ii)$ Dla $[k_m]$, $[l]_m\in \Z _m$ definiujemy: $[k]_m\cdot [l]_m:=[k\cdot l]_m$

Uwaga 3.1.6. Zauważmy, że działania wykonujemy więc w ten sposób, że dodajemy/mnożymy zadane liczby i potem bierzemy resztę z dzielenia wyniku przez $m$. Powyższa definicja działań w $\Z _m$ ma sens, tzn. jeśli weźmiemy liczby reprezentujące te same klasy z $\Z _m$ to wynik działania będzie taki sam - jak wiemy to z części poświęconej teorii liczb.

Zobaczmy to na przykładzie:

$[3]_5=[8]_5$, $[2]_5=[12]_5$ - gdy wymnożymy mamy: $[3]_5\cdot [2]_5=[6]_5=[1]_5$ i analogicznie $[8]_5\cdot [12]_5=[96]_5=[1]_5$.

($\star $) Tabela działania mnożenia modulo 5 w $\Z _5^\star =\{1, 2, 3, 4\}$

$\star $	1	2	3	4
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

Algebra

4 Podstawy teorii grup

Korzeni teorii grup należy się doszukiwać bardzo głęboko w rozwoju relacji między pojęciami klasycznej algebry, arytmetyki i geometrii - do powstania podstaw pojęcia grupy doprowadziły w dużej mierze próby znalezienia wspólnego opisu własności teorioliczbowych i geometrycznych. Te dwa elementy, wspierane bodźcem poszukiwania rozwiązań równań wyższych stopni zostały w końcu sprowadzone do wspólnej płaszczyzny tworząc zręby m.in. języka teorii grup. Postęp czyniony w badaniach geometrii nieeuklidesowych, dalej prace Gaussa, Eulera, Lagrange’a (¹) i wielu innych nad rozwiązalnością równań stopnia co najmniej 5 legły u podstaw badań Galois (²) i Abela. (³) Od czasu tych dwóch matematyków całe pokolenia następców podejmowały idee przez nich zapoczątkowane rozwijając teorię grup i ciał - by wspomnieć Dedekinda, (⁴) Kroneckera,(⁵) czy Jordana, (⁶). To oni wzbogacili wprowadzane wcześniej pojęcia i stosowali już teorię grup w mniej lub bardziej znanej nam dziś formie. Konkretny wkład większości z nich poznamy w dalszym ciągu wykładu. W przeciągu wieków pojęcie grupy przeszło długą ewolucję zanim nabrało współczesnego kształtu, a i dziś możliwe są dwa różne podejścia do charakteryzacji struktury grupowej. My oprzemy się na aksjomatycznym pojęciu grupy. (⁷)

¹ Joseph Louis Lagrange - matematyk i astronom włoskiego pochodzenia, pracujący głównie we Francji, (1736-1813)

² Evariste Galois: matematyk francuski, ”Mozart matematyki”, zginął mając zaledwie 21 lat, (1811-1832) pozostawiając po sobie ogromny wkład w rozwój teorii grup i nowoczesnej teorii równań algebraicznych

³ Niels Henrik Abel - matematyk norweski (1802-1829)

⁴ Julius Wilhelm Richard Dedekind - matematyk niemiecki, (1831-1916)

⁵ Leopold Kronecker - matematyk niemiecki (1823-1891)

⁶ Marie Eddemond Camille Jordan - matematyk francuski, (1838-1922)

⁷ Pojęcie grupy, jeszcze nienazwane, wystąpiło po raz pierwszy u Lagrange’a (grupa permutacji $n$ elementów). W swoim "Disquisitiones"Gauss wykorzystuje grupę addytywną i multiplikatywną reszt modulo $m$, bada też grupy klas form kwadratowych. Dość często autorstwo terminu "grupa"przypisuje się Galois który użył w jednym ze swoich rękopisów określenia "groupe", ale tę samą nazwę zastosował do tego, co dziś określamy jako warstwy grupy względem podgrupy, miał więc chyba bardziej na myśli po prostu źbiórńiż to co my rozumiemy jako grupę, czyli zbiór z działaniem o konkretnych własnościach. Z pewnością formalnym twórcą pojęcia grupy abstrakcyjnej jest Arthur Cayley, który zdefiniował je w 1854 roku w swoim pierwszym artykule o teorii grup opublikowanym w Philosophical Magazine. Do tego czasu zajmowano się jedynie grupami permutacji $n$ elementów. Dalej należy obecną formę pojęcia grupy wiązać z pracami Kroneckera, Burnside’a, von Dycka i H.M. Webera.

4.1 Podstawowe definicje i przykłady

4.1.1 Pojęcie grupy

Zanim wprowadzimy pojęcie grupy zacznijmy od prostej obserwacji.

Uwaga 4.1.1. Rozważmy działanie $\star $ na zbiorze $X$, które jest działaniem łącznym i posiada element neutralny. Wtedy:
- $(1)$ element neutralny jest wyznaczony jednoznacznie,
- $(2)$ jeśli dla elementu $x\in X$ istnieje element symetryczny, to jest on jedyny.

Dowód. (1) Wystarczy zauważyć, że jeśli $e\in X$ oraz $e’\in X$ są elementami neutralnymi dla działania $\star $, to $\tilde {e}=\tilde {e}\star e=e$.

(2) Jeśli $\bar {x}\in X$ oraz $\tilde {x}\in X$ są elementami symetrycznymi dla elementu $x\in G$, to

\[\tilde {x}=\tilde {x}\star e=\tilde {x}(x\bar {x})=(\tilde {x}\star x)\star \bar {x}=e\star \bar {x}=\bar {x}.\]

□

Definicja 4.1.2 ( grupa). Niech $G$ będzie zbiorem niepustym, zaś

\[\star : G\times G\ni (x,y)\str x\star y\in G\]

działaniem (3.0.1) na $G$, dla którego zachodzą następujące własności:
- $(1)$ jest ono łączne,
- $(2)$ posiada element neutralny $e\in G,$
- $(3)$ każdy element $x\in G$ posiada element symetryczny $\overline {x}\in G$.
Wtedy parę $(G,\star )$ nazywamy grupą z działaniem $\star $. Jeśli nie będzie to prowadziło do nieporozumień będziemy często pisali po prostu grupa $G$ zamiast grupa $(G, \star )$. W domyśle jednak grupa jest zawsze zbiorem wraz z działaniem.

Jeśli dodatkowo działanie $\star $ jest przemienne grupę nazywamy przemienną lub abelową.

Uwaga 4.1.3.
- $(1)$ Jeśli określone na $G$ działanie spełnia jedynie warunek łączności, to parę $(G,\star )$ nazywamy półgrupą.
- $(2)$ Jeśli $(G, \star )$ jest półgrupą i dodatkowo istnieje w $G$ element neutralny działania $\star $ to $(G, \star )$ nazywamy monoidem.

Definicja 4.1.4 ( rząd grupy). O grupie $G$ mówimy, że jest skończona, gdy zbiór $G$ jest skończony. Wówczas liczbę elementów $G$, czyli $\# G$ nazywamy rzędem grupy $G$ i oznaczamy $|G|$.

Jeśli zbiór $G$ jest nieskończony, to mówimy, że $G$ jest grupą o rzędzie nieskończonym i piszemy: $|G|=\infty $.

Przykład 4.1.5.
- $(1)$ Dla grup: $(\Z ,+)$, $(\Q ,+)$, $(\R ,+)$, $(\C ,+)$ mamy: element neutralny $e=0$, element symetryczny = liczba przeciwna - są to grupy abelowe.
- $(2)$ Dla grup: $(\Q ^\star ,\cdot )$, $(\R ^\star ,\cdot )$, $(\C ^\star ,\cdot )$ mamy: element neutralny $e=1$, element symetryczny = odwrotność liczby - są to grupy abelowe.
- $(3)$ Grupy reszt modulo:
  
  $(\Z _n,+_n)$, gdzie $[k]_n+_n[l]_n:=[k+l]_n$ - jest to grupa abelowa.
  
  $(\Z _n^\star ,\cdot _n)$, gdzie $[k]_n\cdot _n[l]_n:=[k\cdot l]_n$ - jest to grupa abelowa wtedy i tylko wtedy, gdy $n\in \mathbb {P}$, (ćw.)
- $(4)$ $(U(\Z _n),\cdot _n)$, gdzie $U(\Z _n):=\{k\in \Z _n: \ \textrm {NWD}(k,n)=1\}$ - grupa reszt modulo $n$ liczb względnie pierwszych z $n$. Jest to grupa abelowa.
  
  W dalszej części wykładu, jeśli będziemy mieć do czynienia z elementami zbioru $\Z _n$ to ich dodawanie i mnożenie oznaczać będziemy zwykłymi znakami: ”$+$” i ”$\cdot $” pamiętając o tym, że oznacza to wykonywanie tych działań modulo $n$. (trzeba zmienić w zależności od konwencji w części Teoria liczb)
- $(5)$ Grupy macierzy z działaniem dodawania macierzy: $(\text {M}_n(G), +)$ - grupa macierzy kwadratowych wymiaru $n$ o współczynnikach z $G$, gdzie $G$ oznacza zazwyczaj grupy addytywne $\Z $, $\Q $, $\R $ lub $\C $.
  
  Jeśli $F=\Q , \R , \C $ lub $\Z _p$ dla $p\in \mathbb {P}$, to $(\text {GL}_n(F),\cdot )$ - grupa nieosobliwych macierzy kwadratowych wymiaru $n$ o współczynnikach z $F$, z działaniem mnożenia macierzy o współczynnikach z $F$.
- $(6)$ Grupy symetryczne (ogólne grupy permutacji).
  
  Działanie składania wprowadza na zbiorze $S(X)$, (gdzie $X$ - zbiór niepusty) strukturę grupy. Grupa $(S(X),\circ )$ bywa nazywana grupą symetryczną.
  
  Dla $X:=\{1,\dots ,n\}$ grupę $(S_n,\circ )$ nazywamy grupą permutacji $n$-elementowych. Rząd tej grupy to $n!$ oraz grupa ta jest grupą nieprzemienną wtedy i tylko wtedy, gdy liczba elementów w zbiorze $X$ jest większa niż $2$ (ćw.)
- $(7)$ Grupa diedralna (dihedral(⁸)) - grupa symetrii wielokąta foremnego z działaniem składania. Można spotkać się z dwoma notacjami dla tej grupy: $D_n$ oraz $D_{2n}$ gdzie ta ostatnia związana jest z liczbą elementów grupy symetrii $n$-kąta foremnego, (grupa taka złożona jest z $n$ odbić i $n$-obrotów, (w tym obrotu o 360 stopni - identyczność).

W teorii grup używa się klasycznie dwóch notacji: multiplikatywnej i addytywnej.

	Działanie	Element neutralny	Element symetryczny
Nazwa	mnożenie	jedynka grupy	element odwrotny
Oznaczenie	$x\cdot y$ lub $xy$	$1_G$ lub $1$	$x^{-1}$

Tablica 4.1: Notacja multiplikatywna.

	Działanie	Element neutralny	Element symetryczny
Nazwa	dodawanie	zero grupy	element przeciwny
Oznaczenie	$x+y$	$0_G$ lub $0$	$-x$

Tablica 4.2: Notacja addytywna.

Często notacja addytywna stosowana jest w przypadku, gdy grupa jest abelowa. W skrypcie w dalszym ciągu teorii grup będziemy standardowo stosować notację multiplikatywną oraz skrótowo operować wyrażeniem "grupa $G$źamiast ”grupa $(G,\star )$” a także znakiem mnożenia $\cdot $, (często w ogóle pomijanym) zamiast $\star $ . Nie należy jednak zapominać o tym, że grupa to zawsze zbiór z działaniem, a na jednym zbiorze można wprowadzać różne rodzaje działań, które zadają istotnie różne z punktu widzenia teorii grup struktury (por. tu będzie odwołanie).

Definicja 4.1.6 ( iloczyn standardowy). Niech $G$ będzie grupą, $a_1,\dots , a_n\in G$. Wtedy określamy iloczyn elementów $\prod \limits _{i=1}^n a_i=a_1\cdot \ldots \cdot a_n$ następująco:

\[\prod \limits _{i=1}^na_i=a_1\cdot \ldots \cdot a_n:=\begin {cases} a_1, & \ \text {dla} \ n=1\\ \left (\prod \limits _{i=1}^{n-1}a_i\right )a_n, & \ \text {dla} \ n>1.\end {cases}\]

Zauważmy, że wprowadzając pojęcie grupy zażądaliśmy, by działanie było działaniem łącznym, co oznaczało możliwość "przestawiania nawiasów"w sytuacji $a\star (b\star c)$. Teraz, gdy umiemy już mnożyć więcej niż dwa elementy naturalnym jest pytanie o możliwość stawiania nawiasów w dowolnym miejscu. Między innymi o takiej możliwości mówi kolejna własność.

Własność 4.1.7 ( podstawowe własności działania w grupie). Niech $G$ będzie grupą oraz niech $a_1,\ldots ,a_n\in G$.
- $(1)$ Zachodzi uogólnione prawo łączności, tzn. $(a_1\cdot \ldots \cdot a_k)(a_{k+1}\cdot \ldots \cdot a_n)=a_1\cdot \ldots \cdot a_n$ dla dowolnego $0<k<n$.
- $(2)$ Zachodzi wzór $(a_1\cdot \ldots \cdot a_n)^{-1}=a_n^{-1}\cdot \ldots \cdot a_1^{-1}$.
- $(3)$ Jeśli dodatkowo grupa $G$ jest przemienna, to zachodzi uogólnione prawo przemienności, tzn. $a_{\sigma (1)}\cdot \ldots \cdot a_{\sigma (n)}= a_1\cdot \ldots \cdot a_n$ dla dowolnej permutacji $\sigma \in S_n$.
- Dowód. Dowody wszystkich podpunktów przeprowadzamy indukcyjnie względem $n$.
- $(1)$ Gdy $n=1$ lub $n=2$, to teza jest oczywista, zaś jeśli $n>2$, to w oparciu o łączność działania w grupie zauważmy, że
  $ \seteqsection {4} $
  \begin{align*} (a_1\cdot \ldots \cdot a_k)(a_{k+1}\cdot \ldots \cdot a_n) & =(a_1\cdot \ldots \cdot a_k)\big ((a_{k+1}\cdot \ldots \cdot a_{n-1})a_n\big )\\ & =\big ((a_1\cdot \ldots \cdot a_k)(a_{k+1}\cdot \ldots \cdot a_{n-1})\big )a_n\\ & =(a_1\cdot \ldots \cdot a_{n-1})a_n\\ & =a_1\cdot \ldots \cdot a_n. \end{align*}
- $(2)$ W oczywisty sposób zaczynamy od $n=2$ Wówczas zauważamy, że $(a_1a_2)(a_2^{-1}a_1^{-1})=1$, czyli z jedyności elementu odwrotnego mamy tezę.
  
  Jeśli $n>2$ oraz teza jest prawdziwa dla $(n-1)$ elementów, to
  
  \[(a_1\cdot \ldots \cdot a_n)^{-1}=a_n^{-1}(a_1\cdot \ldots \cdot a_{n-1})^{-1}=a_n^{-1}\cdot \ldots \cdot a_1^{-1}.\]
- $(3)$ Dla $n=2$ teza to nic innego jak przemienność działania w grupie.
  
  Niech więc $n>2$ oraz niech $1\le j\le n$ będzie takie, że $\sigma (j)=n$. Możemy założyć, że $1<j<n$ (z sytuacją $j=1$ lub $j=n$ radzimy sobie prosto, stosując założenie indukcyjne bezpośrednio do pozostałych elementów i ewentualnie wykorzystując dodatkowo przemienność grupy). Mamy teraz
  $ \seteqsection {4} $
  \begin{align*} a_{\sigma (1)}\cdot \ldots \cdot a_{\sigma (n)} & =(a_{\sigma (1)}\cdot \ldots \cdot a_{\sigma (j-1)})a_n(a_{\sigma (j+1)}\cdot \ldots \cdot a_{\sigma (n)})\\ & =(a_{\sigma (1)}\cdot \ldots \cdot a_{\sigma (j-1)}a_{\sigma (j+1)}\cdot \ldots \cdot a_{\sigma (n)})a_n\\ & =(a_{\varrho (1)}\cdot \ldots \cdot a_{\varrho (n-1)})a_n\\ & =(a_1\cdot \ldots \cdot a_{n-1})a_n\\ & =a_1\cdot \ldots \cdot a_n, \end{align*} gdzie permutacja $\varrho \in S_{n-1}$ dana jest wzorem
  
  $ \seteqsection {4} $
  
  \begin{equation*} \varrho (k)=\begin {cases}\sigma (k), & \text {gdy }1\le k\le j-1,\\ \sigma (k+1), & \text {gdy }j\le k\le n-1.\end {cases} \qedhere \end{equation*}
  
  ’Opisowo’ możemy streścić powyższe rozumowanie następująco: szukamy miejsca, w którym jest $a_n$ a następnie korzystając z łączności i przemienności grupy (bierzemy jako jeden element $a_n$ a jako drugi iloczyn tych które stoją ’za nim’) przesuwamy go na koniec. Do pierwszej części, która jest permutacją $(n-1)$-elementową stosujemy założenie indukcyjne.

Zauważmy dodatkowo prostą, a jednocześnie bardzo użyteczną własność, która wynika wprost z łączności i istnienia elementu odwrotnego do dowolnego elementu grupy.

Własność 4.1.8 ( prawo skracania). Jeśli $a$, $b$, $c$ są elementami grupy $G$, to z faktu, że $ab=ac$ lub $ba=ca$ wynika, że $b=c$.

Warto tu przypomnieć fakt, o którym pisaliśmy już w notce historycznej przy okazji definicji wprowadzonej przez Webera. Mianowicie prawo skracania jest równoważne istnieniu elementu odwrotnego w przypadku gdy zbiór $G$ jest skończony, (ćw.) Warto jednocześnie poszukać przykładu takiego monoidu nieskończonego 4.1.3 nie będącego grupą, w którym zachodzi prawo skracania.

Definicja 4.1.9 ( potęgowanie). Gdy $G$ jest grupą, $a\in G$ oraz $k\in \Z $, to określamy

\[a^k:=\begin {cases}\prod \limits _{i=1}^ka, & \text {gdy }k>0,\\ 1, & \text {gdy }k=0,\\ (a^{-1})^{-k}, & \text {gdy }k<0.\end {cases}\]

Inaczej ostatnią równość możemy zapisać $a^{-k}=(a^{-1})^k$ dla $k>0$. Zauważmy, że w półgrupie możliwe jest potęgowanie z wykładnikiem $>0$, natomiast w monoidzie określone są potęgi o wykładniku $\ge 0$.

Własność 4.1.10 ( własności potęg). Jeśli $G$ jest grupą, $a\in G$ oraz $k,l\in \Z $, to $a^ka^l=a^{k+l}$ oraz $(a^k)^l=a^{kl}$.
- Dowód. Są to bezpośrednie wnioski z własności 4.1.7 i definicji potęgi. □

⁸ Dihedral group - określenie to oznacza dokładnie "grupę dwuścianu"

4.1.2 Podgrupy

Definicja 4.1.11 ( podgrupa). Jeśli $(G,\star )$ jest grupą, to podzbiór $H\subset G$ nazywamy podgrupą grupy $G$, gdy:
- $(1)$ $H\ne \vn $,
- $(2)$ zawężenie $\star |_{H\times H}$ przyjmuje wartości w $H$, (czyli jest to działanie na $H$)
- $(3)$ $(H,\star |_{H\times H})$ ma strukturę grupy.

Działanie $\star $ po zawężeniu do $H\times H$ nazywamy działaniem indukowanym. Inaczej mówiąc $H$ jest podgrupą $G$, jeśli jest grupą z działaniem indukowanym z $G$. Piszemy wtedy $H< G$.

Własność 4.1.12 ( warunki równoważne na podgrupę). Gdy $G$ jest grupą oraz $H\s G$, to następujące warunki są równoważne:
- $(1)$ $H$ jest podgrupą $G$,
- $(2)$ $H\ne \vn $ oraz spełnione są dwa warunki:
  - $(i)$ dla dowolnych $x$, $y\in H$ zachodzi $xy\in H$,
  - $(ii)$ dla dowolnego $x\in H$ zachodzi $x^{-1}\in H$.
- $(3)$ $H\ne \vn $ oraz spełniony jest warunek:
  - $(i)$ dla dowolnych $x$, $y\in H$ zachodzi $xy^{-1}\in H$.

Dowód. Zauważmy, że oczywiście jeśli $H$ jest podgrupą to spełnione są warunki z (2), zaś jeśli spełnione są warunki z (2) to zachodzi także warunek z (3), gdyż jeśli $x$, $y\in H$ to na podstawie(2)(ii) mamy $y^{-1}\in H$ a z (2)(i) mamy $xy^{-1}\in H$.

Niech teraz spełniony będzie warunek (3). Zauważmy najpierw, że skoro $H\ne \emptyset $ to istnieje $x\in H$ więc zgodnie z warunkiem (3) mamy $1_G\in x\cdot x^{-1}\in H$. Jeśli teraz $z\in H$ jest dowolnym elementem to biorąc $x:=1_G\in H$, $y:=z\in H$ dostaniemy, że $z^{-1}=1_Gz^{-1}\in H$.

Ostatecznie niech $a$, $b\in H$. Wiemy już, że wtedy też $b^{-1}\in H$, biorąc więc $x:=a$, $y=b^{-1}$ i stosując warunek (3) mamy $ab=xy^{-1}\in H$. Ponieważ łączność działania zachodzi dla każdych elementów w $G$, więc i dla każdych elementów podzbioru $G$ jakim jest $H$ wykazaliśmy, że $H$ jest podgrupą $G$. □

Poniższa uwaga, której dowód pozostawiamy jako ćwiczenie mówi, że sytuacja jeszcze bardziej się upraszcza, gdy mamy do czynienia z podzbiorem skończonym.

Uwaga 4.1.13. Gdy $H$ jest skończonym i niepustym podzbiorem grupy $G$, to wystarczy wykazać, że działanie w grupie $G$ zawężone do $H\times H$ przyjmuje wartości w $H$, aby podzbiór $H$ stanowił podgrupę $G$.

Uwaga ta oczywiście nie jest prawdziwa w przypadku nieskończonego podzbioru, co można łatwo zauważyć rozważając np. $H=\N $ w grupie $(\Z ,+)$.

Przykład 4.1.14.
$(1)$ $(\Z ,+)<(\Q ,+)<(\R ,+)<(\C ,+)$.
$(2)$ $(\Q ^*,\cdotp )<(\R ^*,\cdotp )<(\C ^*,\cdotp )$.
$(3)$ Dla $n>0$ określamy $U_n(\C )=\{z\in \C :z^n=1\}$. Wtedy $(U_n(\C ),\cdotp )<(\C ^*,\cdotp )$.
$(4)$ Jeśli $G$ jest grupą, to podzbiór

\[C(G):=\{x\in G:xa=ax\text { dla wszystkich }a\in G\}\fn {zdarza siÄŹ, Åĳe w podrÄŹcznikach \textbf {centrum grupy} jest oznaczane przez $Z(G)$ - pochodzi to od notacji z wersji niemieckiej}\]

nazywamy centrum grupy $G$. Łatwo sprawdzić, że centrum $C(G)$ jest podgrupą w $G$ i jest to podgrupa abelowa.

Własność 4.1.15 ( charakteryzacja podgrup w $\Z $). Niepusty podzbiór $H$ zbioru liczb całkowitych $\Z $ jest podgrupą grupy $(\Z ,+)$ wtedy i tylko wtedy, gdy $H=n\Z $ dla pewnego $n\in \N _0$.
- Dowód. Sprawdzenie, że każdy podzbiór postaci $n\Z $ jest podgrupą pozostawiamy jako proste ćwiczenie. Udowodnimy teraz, że każda podgrupa ma taką postać. Jeśli $H=\{0\}$, to wystarczy przyjąć $n=0$. Załóżmy więc, że $H\ne \{0\}$ i przyjmijmy (korzystając z zasady minimum)
  
  \[n=\min \{k\in \N : \ k\in H\}.\]
  
  Ponieważ $n\in H$, więc $n\Z \s H$. Jeśli zaś $k\in H$, to możemy podzielić $k$ przez $n$ z resztą (por. Odwołanie do algorytmu dzielenia !) otrzymując takie $(q,r)\in \Z \times \Z $, że $k=qn+r$ oraz $0\le r<n$. Oczywiście $r=k-qn\in H$, co wobec minimalności $n$ daje $r=0$. W takich razie $k=qn\in n\Z $ oraz $H\s n\Z $. □

Uwaga 4.1.16.
$(1)$ Każda grupa $G$ posiada zawsze dwie (czasem równe) podgrupy: całą grupę $G$ oraz podgrupę trywialną $\{1_G\}$ złożoną tylko z elementu neutralnego. Podgrupę $G$ nazywamy podgrupą niewłaściwą grupy $G$. Każdą podgrupę $H< G$ różną od $G$ nazywamy podgrupą właściwą.
$(2)$ Jeśli $G$ jest grupą, $K< H$ oraz $H< G$, to wtedy $K<G$.
$(3)$ Jeśli $G$ jest grupą, $\{H_i\}_{i\in I}$ jest niepustą rodziną podgrup $G$, to przecięcie

\[\bigcap \limits _{i\in I}H_i:=\{x\in G: \ x\in H_i, \forall \ i\in I\}\]

również jest podgrupą $G$.
$(4)$ Suma mnogościowa podgrup nie musi być podgrupą. Przykładowo $H_1=2\Z $ oraz $H_2=3\Z $ są podgrupami $\Z $, jednak $H_1\cup H_2$ nie jest podgrupą $\Z $, bo $5=2+3\notin H_1\cup H_2$.

Jako proste ćwiczenie proponujemy wykazanie faktu, że dla dwóch podgrup $H$ i $K$ grupy $G$ zachodzi równoważność: $H\cup K$ jest podgrupą $G$ wtedy i tylko wtedy, gdy $H\subset K$ lub $K\subset H$.

Algebra

Indeks

algorytm Euklidesa, NWD i NWW w $Z$

centrum, Podgrupy

działanie, Działania i ich własności

działanie indukowane, Podgrupy

działanie przemienne, Działania i ich własności

działanie łączne, Działania i ich własności

dzielenie z resztą, Podzielność w $\protect \mathbb {Z}$

element neutralny działania, Działania i ich własności

element symetryczny (odwrotny), Działania i ich własności

funkcja Eulera, Funkcja Eulera, jej własności i zastosowania

grupa, Pojęcie grupy

grupa abelowa, Pojęcie grupy

grupa diedralna, Pojęcie grupy

grupa nieskończona, Pojęcie grupy

grupa przemienna, Pojęcie grupy

grupa skończona, Pojęcie grupy

identyczność Bacheta-Bezouta, NWD i NWW w $Z$

iloczyn standardowy, Pojęcie grupy

jedność w $\Z $, O liczbach pierwszych i ich własnościach

liczba pierwsza, O liczbach pierwszych i ich własnościach

liniowe równanie diofantyczne, NWD i NWW w $Z$

małe twierdzenie Fermata, Małe twierdzenie Fermata, twierdzenie Eulera oraz twierdzenie Wilsona

monoid, Pojęcie grupy

NWD, NWW, NWD i NWW w $Z$

permutacje, III. Zbiory odwzorowań i działania na nich

podgrupa, Podgrupy

podgrupa właściwa, Podgrupy

podgrupy w $\Z $, Podgrupy

podzielność, Podzielność w $\protect \mathbb {Z}$

potęga, Pojęcie grupy

półgrupa, Pojęcie grupy

rozdzielność działania względem innego działania, Działania i ich własności

rząd grupy, Pojęcie grupy

twierdzenie Eulera, Małe twierdzenie Fermata, twierdzenie Eulera oraz twierdzenie Wilsona

twierdzenie Wilsona, Małe twierdzenie Fermata, twierdzenie Eulera oraz twierdzenie Wilsona

układ reszt, Małe twierdzenie Fermata, twierdzenie Eulera oraz twierdzenie Wilsona, Małe twierdzenie Fermata, twierdzenie Eulera oraz twierdzenie Wilsona

\(\circ \)	\(\sigma _1\)	\(\sigma _2\)	\(\sigma _3\)	\(\sigma _4\)	\(\sigma _5\)	\(\sigma _6\)
\(\sigma _1\)	\(\sigma _1\)	\(\sigma _2\)	\(\sigma _3\)	\(\sigma _4\)	\(\sigma _5\)	\(\sigma _6\)
\(\sigma _2\)	\(\sigma _2\)	\(\sigma _1\)	\(\sigma _5\)	\(\sigma _6\)	\(\sigma _3\)	\(\sigma _4\)
\(\sigma _3\)	\(\sigma _3\)	\(\sigma _6\)	\(\sigma _1\)	\(\sigma _5\)	\(\sigma _4\)	\(\sigma _2\)
\(\sigma _4\)	\(\sigma _4\)	\(\sigma _5\)	\(\sigma _6\)	\(\sigma _1\)	\(\sigma _2\)	\(\sigma _3\)
\(\sigma _5\)	\(\sigma _5\)	\(\sigma _4\)	\(\sigma _2\)	\(\sigma _3\)	\(\sigma _6\)	\(\sigma _1\)
\(\sigma _6\)	\(\sigma _6\)	\(\sigma _3\)	\(\sigma _4\)	\(\sigma _2\)	\(\sigma _1\)	\(\sigma _5\)

Algebra

Spis treści

Algebra

1 Wstęp

1.1 Oznaczenia, konwencje i podstawowe twierdzenia

Algebra

2 Podstawy teorii liczb

2.1 Podzielność w \(\Z \)

Algebra

2.2 NWD i NWW w \(Z\)

Algebra

2.3 O liczbach pierwszych i ich własnościach

Algebra

2.4 Kongruencje i ich własności, twierdzenie chińskie o resztach

Algebra

2.5 Funkcja Eulera, jej własności i zastosowania

Algebra

2.6 Małe twierdzenie Fermata, twierdzenie Eulera oraz twierdzenie Wilsona

Algebra

3 Działania i ich własności

3.1 Podstawowe przykłady działań

3.1.1 I. Kanoniczne przykłady liczbowe

3.1.2 II. Działania w zbiorach macierzy

3.1.3 III. Zbiory odwzorowań i działania na nich

3.1.3.1 Tabela działania na zbiorze

3.1.4 IV. Kongruencje i działania modulo

Algebra

4 Podstawy teorii grup

4.1 Podstawowe definicje i przykłady

4.1.1 Pojęcie grupy

4.1.2 Podgrupy

Algebra

Indeks

	720	546
720	1	0
546	0	1

	720	546
546	0	1
174	1	-1

	720	546
174	1	-1
24	-3	4

	720	546
24	-3	4
6	22	-29