(image)

Algebra

Ewa Cygan, Maciej Ulas

Spis treści

Algebra — Wstęp

(image)

Algebra

1 Wstęp

1.1 Oznaczenia, konwencje i podstawowe twierdzenia

  • 1. Moc zbioru \(X\) oznaczamy przez \(|X|\) lub \(\# X\).

  • 2. Funkcja „signum” jest określona na \(\R \) następująco

    \[\sgn (a):=\begin {cases}-1, & \text {gdy }a<0,\\ 0, & a=0,\\ 1, & \text {gdy }a>0.\end {cases}\]

Ponadto przyjmujemy oznaczenia:

\begin{align*} \PP \ & =\ \text {zbiÃşr liczb pierwszych}\ =\ \{2,3,5,\ldots \},\\ \N \ & =\ \text {zbiÃşr liczb naturalnych}\ =\ \{1,2,\ldots \},\\ \N _0\ & =\ \text {zbiÃşr liczb naturalnych z zerem}\ =\ \{0,1,2,\ldots \},\\ \Z \ & =\ \text {zbiÃşr liczb caÅĆkowitych},\hskip 9mm \Z ^\star =\Z \setminus \{0\},\\ \Q \ & =\ \text {zbiÃşr liczb wymiernych}, \hskip 8mm \Q ^\star =\Q \setminus \{0\},\\ \R \ & =\ \text {zbiÃşr liczb rzeczywistych}, \hskip 5mm \R ^\star =\R \setminus \{0\},\\ \C \ & =\ \text {zbiÃşr liczb zespolonych}, \hskip 8mm \C ^\star =\C \setminus \{0\}. \end{align*}

Algebra — Podstawy teorii liczb

(image)

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ównież 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, że \(b\) dzieli \(a\) (lub inaczej \(b\) jest dzielnikiem \(a\)), gdy istnieje takie \(c\in \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 poniż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 wyżej, ogólniejszego rezultatu.

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

    (\(\bullet \)) istnieje dokładnie jedna taka para \((q,r)\in \Z \times \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, ż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, ż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łóżmy, ż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, ż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 — NWD i NWW w

(image)

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. Należy jednak zaznaczyć, że istnieje definicja tych pojęć w ogólniejszych strukturach algebraicznych, w których na ogół nie możemy mówić o pojęciu „najmniejszy” czy „największy”. Wspomnianą defincję przdstawimy dalszej części naszyh rozważ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, że przynajmniej jedna z liczb jest niezerowa) nazywamy największą liczbę całkowitą, która dzieli wszystkie \(a_1, \ldots , a_r\). 1

      \(\underline {Oznaczenie:}\) \(\nwd (a_1,\dots ,a_r)\) (w literaturze również: \((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 każdą z liczb \(a_1,\ldots , a_r\).

      \(\underline { Oznaczenie:}\) \(\nww (a_1,\dots ,a_r)\) (w literaturze również: \([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 }\). Zauważmy, że z określenia \(\nwd (a, b)\) wynika, ż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 2. Oczywiście, jeśli \(a\in \Z ^\star \), \(b=0\), to \(\nwd (a,b)=|a|\). W dalszej części naszych rozważań zakładamy, że obie liczby są niezerowe.

Algorytm Euklidesa 3

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, ż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, ż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, ż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ść moż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)\). Wykażemy, że \(d=d’\). Ponieważ \(d|a\) i \(d|b\), więc istnieją takie liczby \(k_{1}, k_{2}\in \Z \), że \(a=dk_{1}, b=dk_{2}\). Z założenia otrzymujemy równość \(r=a-qb=d(k_{1}-qk_{2})\). Oznacza to, ż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, że \(b=d’k_{3}, r=d’k_{4}\). Stąd \(a=qb+r=d’(qk_{3}+k_{4})\) i dostajemy, że \(d’|a\). Oznacza to, ż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ę.  □

Wykażemy teraz, że prawdziwe jest następujące

  • Twierdzenie 2.2.4Z: 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 wykażemy równość \(\nwd (a,b)=r_{n}\). Z opisu algorytmu Euklidesa wynika, że istnieją takie ciągi liczb całkowitych \(r_{i}, i=1,\ldots , n, q_{i}, i=1, \ldots , n+1\), ż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

    \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 już wiemy, że dla danej pary liczb \(a, b\in \Z ^{\star }\) można łatwo wyznaczyć ich największy wspólny dzielnik pojawia się naturalne pytanie: jak duż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łoż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 można wykazać, że \(n\)-ta iczba Fibonacciego wyraż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 można wykazać, ż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, że \(\nwd (a,b)=r_{n}\). Z opisu algorytmu Euklidesa wynika, że istnieją takie ciągi liczb całkowitych \(r_{i}, i=1,\ldots , n, q_{i}, i=1, \ldots , n+1\), ż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, że \(q_{i}\geq 1\) oraz \(q_{n+1}\geq 2\). Otrzymujemy zatem, że

    \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}\). Ponieważ \(\log _{10}\phi =0.208988\ldots >\frac {1}{5}\), więc \(\log _{10}b>\frac {1}{5}(n-1)\) lub równoważnie

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

    Zauważmy teraz, ż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\). Ponieważ prawdziwa jest równość \(m=\lfloor \log _{10}b\rfloor +1\), więc dostajemy tezę.  □

  • Uwaga 2.2.6 Należy zauważyć, że teza w powyższym twierdzeniu nie może być wzmocniona. Istotnie, z dowodu wynika, jeśli \(a=F_{n+1}, b=F_{n}\), to w nierównościach wiążą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}\), umoż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łóżmy, że con jamniej jedna z tych liczb jest niezerowa.

    T: Istnieją takie liczby \(k_1,\ldots , k_n\in \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 rozważmy zbiór \(T=\{ax+by: \ ax+by>0, x, y\in \Z \}\). Oczywiście, jedna z liczb \(\pm a\), \(\pm b\) należy do naszego zbioru bo któraś z liczb \(a\), \(b\) jest niezerowa. Wobec tego zbiór ten jest niepusty. Ponieważ zawiera wyłącznie liczby naturalne, to posiada element najmniejszy, powiedzmy \(d\). Istnieją więc takie liczby \(x_0\), \(y_0\in \Z \), że \(d=ax_0+by_0\). Udowodnimy, że \(d\) jest poszukiwanym największym wspólnym dzielnikiem \(a\) i \(b\).

    Udowodnimy najpierw, że \(d|a\). Z algorytmu dzielenia z resztą wiemy, że istnieją \(q\), \(r\) takie, ż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, że \(d|b\).

    Załóżmy teraz, że \(0<t\) jest taką liczbą całkowitą, która dzieli i \(a\) i \(b\). To oznacza, ż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, że każdy wspólny dzielnik liczb \(a\) i \(b\) jest dzielnikiem \(d\), co oznacza, że \(d=\nwd (a,b)\).

    Przypuśćmy teraz, że \(n>2\) i nasze twierdzenie jest prawdziwe dla mniej niż \(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łożeniem indukcyjnym wiemy, że istnieją takie liczby \(l_1,\ldots , l_{n-1}, k, l\in \Z \), że

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

    Udowodnimy, ż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, że \(d\) dzieli \(d_0\) oraz \(a_n\). Ponieważ \(d_0\) dzieli każ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, że \(\tilde d|d_0\), a tym samym liczba \(\tilde d\) dzieli \(d\). Oznacza to, że \(\tilde d\leqslant d\) i wobec tego \(d=\)NWD\((a_1,\ldots , a_n)\).

    Jednocześnie, ponownie dzięki \((\star )\), wiemy, ż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\), ż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, że znajomość rozkładu liczb całkowitych \(a, b\) na czynniki pierwsze umoż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, że \(p_i\ne p_j\) dla \(i\ne j\), \(k_i\geqslant 0\) oraz \(t_i=\)min\((k_i,l_i)>0\) dla każdego \(i\)), to \(\nwd (a,b)=p_1^{t_1}\cdot \ldots \cdot p_s^{t_s}\). Nie wspominamy dokładniej o tej metodzie, gdyż odwołuje się ona do zasadniczego twierdzenia arytmetyki, o którym opowiemy w dalszej części naszych rozważań. Należy jednak zwrócić uwagę, że ta metoda wyznaczania \(\nwd (a,b)\) ma istotną słabość, gdyż 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ą duże, powiedzmy \(>10^{100}\), i wybrane w sposób losowy, to problem ich rozkładu jest trudny.

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

  • Wniosek 2.2.9 ( zależ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 umoż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łóżmy, ż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 każ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 zauważmy, ż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, że para \(\left (x_{0}+\frac {b}{d}t,y_{0}-\frac {a}{d}t\right )\) również 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, że \(aX+bY=c=ax_{0}+by_{0}\) i w konsekwencji

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

    Ponieważ \(\nwd (a/d,b/d)=1\), więc \(\frac {a}{d}|y_{0}-Y\) oraz \(\frac {b}{d}|X-x_{0}\). Onzacza to, że istnieje taka liczba całkowita \(t\), ż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ążemy liniowe równanie diofantyczne

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

    By rowiązać powyższe równanie wyznaczymy najpierw \(\nwd (720,546)\), a dokładniej takie liczby całkowite \(x_{0}, y_{0}\), że \(\nwd (720,546)= 720x_{0}+546y_{0}\). Zanim jednak to zrobimy zauważmy, że przedstawienie \(\nwd \) dwóch liczb za pomocą kombinacji liczb wyjściowych można oczywiście uzyskać „wracając” krok po kroku drogą wykonywanego algorytmu Euklidesa. Jest to jednak czasochłonne, gdyż wymaga wielu operacji arytmetycznych. Procedurę tę można uprościć wyrażając w każ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, że \(720=1\cdot 546+174\). Mnożą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 mnoż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 też przedstawienie \(6=22\cdot 720+(-29)\cdot 546\). Mamy zatem, ż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. \]

1 Zauważmy, że stwierdzenie największa liczba ma tutaj sens: rozważamy naturalny porządek w zbiorze liczb całkowitych, zaś potencjalne dzielniki są ograniczone z góry przez \(|a_i|\)

2 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

3 Nazwa algorytm pochodzi od brzmienia fragmentu nazwiska arabskiego matematyka Muhammada ibn Musa al.-Chorezmiego, którego uznaje się za prekursora metod obliczeniowych w matematyce. Ż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 — O liczbach pierwszych i ich wlasnościach

(image)

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 moż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}\).

    Każdą liczbę naturalną większą od jedynki, nie będącą liczbą pierwszą nazywamy liczbą złożoną.

Pamiętajmy dalej o umowie, iż liczba jeden nie jest ani liczbą pierwszą ani też liczbą złoż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ć, że własność 2.3.2 charakteryzuje liczby pierwsze. Dokładniej, stosując tę własność można wprowadzić definicję liczby pierwszej. Jest to o tyle ciekawe z naszego punktu widzenia, ż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) okażą się być nierównoważ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 4 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 też gaussowskie uogólnienie lematu Euklidesa. Jak się często podkreśla „lemat Gaussa” pojawia się już jednak wcześniej w pracy Nouveaux éléments de mathématiques Jeana Presteta 5 z XVII wieku.

Definicja, którą teraz wprowadzimy moż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 niż 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, ż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, ż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, ż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, że: \(\forall \ i\in \{1,\dots ,r\}: \ p_i=q_{\sigma (i)}\).

  • Twierdzenie 2.3.5 ( Zasadnicze twierdzenie arytmetyki) Każ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łóżmy, że teza jest spełniona dla takich liczb naturalnych \(m\), ż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łożenia indukcyjnego liczby \(a\) i \(b\) są liczbami pierwszymi bądź iloczynami liczb pierwszych. W konsekwencji \(n\) również 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, że pozostałe liczby pierwsze \(p_j\) dzielą jedynkę co jest niemoż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, ż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 możemy przyjąć, ż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, ż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łożenia indukcyjnego otrzymujemy \(r=s\) i istnieje taka bijekcja \(\widetilde \sigma \) zbioru \(\{2,\ldots , n\}\) na siebie, (permutacja tego zbioru), ż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, że \(\mathcal {P}=\{p_1,\dots , p_r\}\) i zdefinujmy liczbę \(M:=p_1\cdot \ldots \cdot p_r+1\). Jest jasne, że ż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 już wiemy, ż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 6 i Ch. J. de la Vallée-Poussin 7 udowodnili niezależ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. Moż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 pokażemy dowód Erdősa8 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, że liczba naturalna nazywana jest bezkwadratową, jeśli nie jest podzielna przez kwadrat żadnej liczby pierwszej. Oznaczmy zbiór liczb bezkwadratowych przez \(B\).

    Dla \(n\in \N \) rozważmy zbiór

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

    i zauważmy, że \(|A(n)|=n\). Istotnie, każdą liczbą naturalną \(m\) moż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óżnych liczb pierwszych, z których każda jest \(\leq n\). Oznacza to, że \(b\) daje sie zapisać jako iloczyn liczb liczb ze zbioru \(\{p_{1},p_{2},\ldots ,p_{\pi (n)}\}\). Możliwych iloczynów mamy \(2^{\pi (n)}\). Podsumowując nasze rozważania widzimy, że jeśli \((a,b)\in A(n)\), to mamy co najwyżej \(\sqrt {n}\) możliwych wyborów liczby \(a\) oraz \(2^{\pi (n)}\) moż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 powyż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ąż 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). Już w okolicach 200 p.n.e. grecki matematyk Eratosthenes 9wprowadził 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 aż 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ć można m.in. test Lucasa-Lehmera, 10 (przy użyciu tego testu znaleziono największe liczby pierwsze, test dotyczy badania pierwszości tzw. liczb Mersenne’a) 11, 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ę, że zwykle są dużo szybsze od testów deterministycznych. Liczby, którym udaje się przejść pozytywnie test probablistyczny, ale mimo to okazują się być jednak liczbami złożonymi znane są w kontekście liczb "pseudopierwszych". Istnieje wiele różnych rodzajów takich liczb, z których bodaj najbardziej znane to liczby pseudopierwsze Fermata, które mimo iż pozostają liczbami złożonymi to spełniają założ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ą zależności wielomianowej od rozmiaru danych wejściowych. Do czasu pojawienia się tego testu zasadniczo nie było dowodu na to, iż test pierwszości zadanej liczby jest problemem rozwiązywalnym w czasie wielomianowym mimo, iż uważano że taka możliwość istnieje.

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

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

6 Jacques Hadamard: matematyk francuski (1865–1963)

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

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

9 Eratosthenes: grecki matematyk, poeta, geograf, astronom i filozof (276-194 p.n.e.)
10 Edouard Lucas, matematyk francuski 1842-1891, Derrick Henry Lehmer, matematyk amerykański, 1905-1991
11 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 — Kongruencje i ich wlasności, twierdzenie chińskie o resztach

(image)

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 też znacznie ułatwiło to przeprowadzanie wielu operacji matematycznych.

  • Definicja 2.4.1 ( relacja przystawania modulo) Niech \(m\in \N \). Mówimy, ż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ównoważności w zbiorze liczb całkowitych.

    Klasę równoważności liczby \(k\in \Z \) względem relacji przystawania modulo \(m\) oznaczamy przez \([k]_m\), zaś zbiór wszystkich klas równoważ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 każdym razem klasę równoważności reprezentowaną przez daną liczbę. Jest to poprawne, gdyż z algorytmu dzielenia z resztą wiemy, że liczby \(0, \ldots , m-1\) wyczerpują wszystkie klasy równoważności.

Zauważmy, że relacja przystawania modulo jest zgodna z działaniami dodawania i mnożenia. Własności ta umoż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, ż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 powyż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, ż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 każdego \(i\in \{0,\ldots ,n\}\) mamy, ż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. toż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, ż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, ż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, że \(m_i|k\) dla każdego \(i=1,\dots ,r\), to \(m_1\cdot \ldots \cdot m_r|k\).

  • Dowód. Ćwiczenie. □

Przejdziemy teraz do rozważania równań oraz układów kongruencji. Łatwo sprawdzić, ż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łóż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. Zauważmy, że istnienie rozwiązania naszej kongruencji jest równoważne temu, że istnieje \(x\in \Z \) takie, że \(m|ax-b\) co z kolei jest równoważne stwierdzeniu, iż istnieje \(y\in \Z \) takie, ż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, że każ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 ). \]

    Zauważmy, ż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, że \(i=j\) i dotajemy sprzeczność. W konsekwencji każ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, że warunkiem koniecznym istnienia rozwiązania jest istnienie rozwiązania każdej z kongruencji wchodzącej w skład układu. Jest to równoważne koniunkcji warunków \(\nwd (u_{i},m_{i})|v_{i}\) dla \(i=1,2,\ldots ,n\). Oznacza to, że bez straty dla ogólności możemy założyć, ż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}}. \]

Moż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 wykażamy, że sformułowany warunek jest konieczny. Istotnie, niech \(i,j\in \{1,\ldots ,n\}, i\neq j\), i rozważmy kongruencje

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

    Z pierwszej kongruencji dostajemy, ż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}). \]

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

    Wykażemy teraz, że warunek \(\nwd (m_{i},m_{j})|(a_{i}-a_{j})\) dla \(i, j\in \{1,\ldots ,n\}, i\neq j\), jest również wystarczający. Rozważ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, ż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, ż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, że wykładnik \(p\) w rozkładzie \(\nww (m_{1},m_{2})\) wynosi \(\max \{\beta _{1},\beta _{2}\}\). W konsekwencji dostajemy, że

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

    Z założenia widzimy, że

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

    Ponieważ \(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)\). Ponieważ \(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, że układ kongruencji

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

    jest równoważny kongruencji

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

    Oznacza to, ż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.  □

Powyż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, że \(x\equiv a_i \pmod {m_i}\) dla każ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, że rozwiązanie rozważanego układu istnieje i jest jednoznaczne modulo \(M:=\nww (m_{1},\ldots ,m_{n})=m_1\cdot \ldots \cdot m_n\). Pokaż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, że również 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, ż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).\) Wykażemy, ż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ównież tę kongruencję, to oznacza, że \(x’-x\) jest podzielne przez każde \(m_i\). Wobec tego z 2.4.5(5) wynika, że \(x’-x\) jest podzielne przez iloczyn \(m_1\cdot \ldots \cdot m_n\) i mamy tezę.  □

Zaletą powyższego dowodu jest jego algorytmiczny charakter, gdyż każdy układ kongruencji rozważanej postaci o modułach względnie pierwszych może być rozwiązany w przedstawiony sposób. Jednakże, mankamentem tej metody jest liczba i wielkość obliczeń, które trzeba przeprowadzić by otrzymać poszukiwane rozwiązanie. Dlatego też 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 rozważ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, ż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ównoważnie \(3a\equiv 1\pmod {5}\). Po przemnożeniu stronami przez 2 dostajemy, że \(a\equiv 2\pmod {5}\), co implikuje, ż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ównoważnie, po redukcji modulo 7, \(b\equiv 0\pmod {7}\). Ostatecznie \(b=7c\) i tym samy \(x=105b+8\), co oznacza, że najmniejszym dodatniem rozwiązaniem naszego układu jest \(x=8\).

Przedstawione podejście może być zastosowane również do układów kongruencji, których moduły nie są parami względnie pierwsze. Jeśli rozważany układ ma rozwiązanie (co oznacza, ż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 rozważanego układu do sytuacji, gdy moduły są parami względnie pierwsze. Przykładowo rozważ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ównoważ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 może być również potwierdzone stosując twierdzenie 2.4.7).

Algebra — Funkcja Eulera, jej wlasności i zastosowania

(image)

Algebra

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

W tym podrozdziale zapoznamy się z najważ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ą 12. Funkcję tę można definiować na róż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})\), gdyż mamy \(p^{k-1}\) liczb całkowitych takich, że \(1\leqslant l<p^k\), które są podzielne przez \(p\).

Przypomnijmy, ż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, ż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 żą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) Wykażemy, ż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 wykażemy, ż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ć, ż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óż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 każdego \(n\in \N \) prawdziwa jest równość \(\sum \limits _{d|n}\varphi (d)=n\), gdzie sumujemy po wszystkich dodatnich dzielnikach \(n\).

  • Dowód. Zauważmy, że jeśli \(k\in \{1,\ldots , n\}\), to \(\nwd (n,k)=n/d\) dla pewnego dzielnika \(d\) liczby \(n\). Jeż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, ż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, ż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ę.  □

12 funkcja o dziedzinie \(\Bbb N\) i wartościach zespolonych

Algebra — Male twierdzenie Fermata, twierdzenie Eulera oraz twierdzenie Wilsona

(image)

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, że dziś moż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ć moż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 powyższego twierdzenia, gdyż jest ono szczególnym przypadkiem ogólniejszego wyniku uzyskanego przez Eulera (nazywanego również 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, że dla dowolnego \(i\in \{0,\ldots ,n-1\}\) istnieje dokładnie jeden element \(u\in U\), ż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, że dla dowolnego \(i\in \{1,\ldots ,n\}, \nwd (i,n)=1\), istnieje dokładnie jeden element \(u\in U\), ż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\). Zauważmy, że zbiór \(kU_{m}=\{ka_{1},\ldots ,ka_{\phi (m)}\}\) również jest zredukowanym układem reszt modulo \(m\). Jest to konsekwencja względnej pierwszości liczb \(k\) i \(m\). Oznacza to, ż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}. \]

    Ponieważ \(\nwd \left (m,\prod _{i=1}^{\varphi (m)}\right )=1\), więc możemy podzielić skrajne strony powyższej kongruencji przez \(\prod _{i=1}^{\varphi (m)}\) otrzymując w efekcie

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

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

     □

Nasze wstępne rozważ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łóżmy zatem, że \(n\geq 4\). Jeśli \(n\) jest liczbą złożoną, to jej wszystkie dzielniki znajdują się w zbiorze \(A=\{1,2,\ldots ,n-1\}\). Rzecz jasna \(\nwd ((n-1)!,n)>1\), co oznacza, że kongruencja \((n-1)!\equiv -1\pmod {n}\) jest niemożliwa. Jeśli \(n\) jest liczbą pierwszą, to żadna z liczb \(i\in A\) nie jest dzielnikiem \(n\). Oznacza to, ż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, że pomijając liczby \(i=1\) oraz \(i=n-1\), zbiór \(\{2,\ldots ,n-2\}\) można ustawić w pary róż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}. \]

    Mnożąc powyż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 — Dzialania i ich wlasności

(image)

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 moż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. Każ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\). (1)

  • 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 \) gdyż moż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.\) (2)

    • \((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\). (3)

    • \((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).\]

1 czasem fakt, że para punktów z \(X\) przechodzi na punkt z \(X\) nazywa się wewnętrznością działania

2 uwaga: element neutralny nie zawsze musi istnieć, np. w \(\N \) nie istnieje element neutralny dodawania

3 uwaga: element symetryczny może dla pewnych elementów istnieć, dla innych nie np. w zbiorze \(\Z \) z działaniem mnoż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 mnożenia wprowadzone na zbiorach \(\Q ^\star \), \(\R ^\star \), \(\C ^\star \).4

4 Wskazane działania można oczywiście wprowadzać także na innych zbiorach liczbowych (np. mnożenie możemy określić na zbiorze liczb całkowitych) - prezentujemy tu jednak umownie "kanonicznieżozumiane działania, które posiadają we wskazanych zbiorach szereg podstawowych własności

3.1.2 II. Działania w zbiorach macierzy

Bardzo ważnym typem działania jest działanie mnoż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 rozważać będziemy też 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 rozważać będziemy domyślnie działanie dodawania macierzy.

Zbiór wszystkich macierzy nieosobliwych 5 wymiaru \(n\) nad pewnym zbiorem liczbowym \(A\) oznaczać będziemy \(GL_n(A)\). W zbiorze tym rozważać będziemy domyślnie działanie mnożenia macierzy.

5 Pamiętamy, że macierz nieosobliwa to macierz o wyznaczniku róż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) Rozważmy zbiór \(n\)-elementowy: \(\{1, 2, \ldots , n\}\). Każ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 \). (6)

Każ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, że nasze odwzorowanie \(\sigma \) przeprowadza \(1\) na \(\sigma (1)\), \(2\) na \(\sigma (2)\) itd. aż do \(n\) na \(\sigma (n)\).

Zbiór permutacji zbioru \(X\) będziemy rozważ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 "mnoż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\).

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

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

Tabela działania składania/mnoż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\)

7 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, że każda grupa (zbiór z działaniem łącznym, dla którego istnieje element neutralny i każdy z elementów posiada symetryczny, 4.1.2) moż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ównoważ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)\) Każdy ze zbiorów \(\Z _m\) jest \(m\)-elementowy jako, że mamy \(m\) róż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 należy, że wtedy oznaczenie \(’0’\) mówi, że mamy na myśli wszystkie liczby podzielne przez \(m\) itd.

Na zbiorze \(\Z _m\) będziemy wprowadzać dwa działania: dodawania i mnoż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 Zauważmy, że działania wykonujemy więc w ten sposób, że dodajemy/mnożymy zadane liczby i potem bierzemy resztę z dzielenia wyniku przez \(m\). Powyż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 wymnoż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 mnoż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 — Podstawy teorii grup

(image)

Algebra

4 Podstawy teorii grup

Korzeni teorii grup należ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 duż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ń wyż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 (1) i wielu innych nad rozwiązalnością równań stopnia co najmniej 5 legły u podstaw badań Galois (2) i Abela. (3) 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, (4) Kroneckera,(5) czy Jordana, (6). To oni wzbogacili wprowadzane wcześniej pojęcia i stosowali już 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ś możliwe są dwa różne podejścia do charakteryzacji struktury grupowej. My oprzemy się na aksjomatycznym pojęciu grupy. (7)

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

2 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

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

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

5 Leopold Kronecker - matematyk niemiecki (1823-1891)

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

7 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 też grupy klas form kwadratowych. Dość często autorstwo terminu "grupa"przypisuje się Galois który uż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ńiż 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 należ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.  Rozważ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 zauważyć, ż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)\) każ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, ż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, ż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 mnożenie oznaczać będziemy zwykłymi znakami: ”\(+\)” i ”\(\cdot \)” pamiętając o tym, że oznacza to wykonywanie tych działań modulo \(n\). (trzeba zmienić w zależ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 mnoż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 niż \(2\) (ćw.)

    • \((7)\) Grupa diedralna (dihedral(8)) - grupa symetrii wielokąta foremnego z działaniem składania. Moż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łożona jest z \(n\) odbić i \(n\)-obrotów, (w tym obrotu o 360 stopni - identyczność).

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

Działanie Element neutralny Element symetryczny
Nazwa mnoż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ć wyrażeniem "grupa \(G\)źamiast ”grupa \((G,\star )\)” a także znakiem mnożenia \(\cdot \), (często w ogóle pomijanym) zamiast \(\star \) . Nie należy jednak zapominać o tym, że grupa to zawsze zbiór z działaniem, a na jednym zbiorze można wprowadzać różne rodzaje działań, które zadają istotnie róż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}\]

Zauważmy, że wprowadzając pojęcie grupy zażądaliśmy, by działanie było działaniem łącznym, co oznaczało możliwość "przestawiania nawiasów"w sytuacji \(a\star (b\star c)\). Teraz, gdy umiemy już mnożyć więcej niż dwa elementy naturalnym jest pytanie o możliwość stawiania nawiasów w dowolnym miejscu. Między innymi o takiej moż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 zauważmy, że

      \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 zauważamy, ż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, że \(\sigma (j)=n\). Możemy założyć, że \(1<j<n\) (z sytuacją \(j=1\) lub \(j=n\) radzimy sobie prosto, stosując założenie indukcyjne bezpośrednio do pozostałych elementów i ewentualnie wykorzystując dodatkowo przemienność grupy). Mamy teraz

      \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

      \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’ możemy streścić powyż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łożenie indukcyjne.

Zauważmy dodatkowo prostą, a jednocześnie bardzo uż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, że \(ab=ac\) lub \(ba=ca\) wynika, że \(b=c\).

Warto tu przypomnieć fakt, o którym pisaliśmy już w notce historycznej przy okazji definicji wprowadzonej przez Webera. Mianowicie prawo skracania jest równoważ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ść możemy zapisać \(a^{-k}=(a^{-1})^k\) dla \(k>0\). Zauważmy, że w półgrupie moż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.  □

8 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ęż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ęż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ównoważne na podgrupę) Gdy \(G\) jest grupą oraz \(H\s G\), to następujące warunki są równoważ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. Zauważmy, ż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 także warunek z (3), gdyż 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). Zauważmy najpierw, ż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, że \(z^{-1}=1_Gz^{-1}\in H\).

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

Poniższa uwaga, której dowód pozostawiamy jako ćwiczenie mówi, ż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ć, że działanie w grupie \(G\) zawęż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 można łatwo zauważyć rozważ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ÄŹ, Åije w podrÄŹcznikach \textbf {centrum grupy} jest oznaczane przez $Z(G)$ - pochodzi to od notacji z wersji niemieckiej}\]

    nazywamy centrum grupy \(G\). Łatwo sprawdzić, ż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, że każdy podzbiór postaci \(n\Z \) jest podgrupą pozostawiamy jako proste ćwiczenie. Udowodnimy teraz, że każda podgrupa ma taką postać. Jeśli \(H=\{0\}\), to wystarczy przyjąć \(n=0\). Załóżmy więc, że \(H\ne \{0\}\) i przyjmijmy (korzystając z zasady minimum)

      \[n=\min \{k\in \N : \ k\in H\}.\]

      Ponieważ \(n\in H\), więc \(n\Z \s H\). Jeśli zaś \(k\in H\), to możemy podzielić \(k\) przez \(n\) z resztą (por. Odwołanie do algorytmu dzielenia !) otrzymując takie \((q,r)\in \Z \times \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)\) Każda grupa \(G\) posiada zawsze dwie (czasem równe) podgrupy: całą grupę \(G\) oraz podgrupę trywialną \(\{1_G\}\) złożoną tylko z elementu neutralnego. Podgrupę \(G\) nazywamy podgrupą niewłaściwą grupy \(G\). Każdą podgrupę \(H< G\) róż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ównież 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, że dla dwóch podgrup \(H\) i \(K\) grupy \(G\) zachodzi równoważność: \(H\cup K\) jest podgrupą \(G\) wtedy i tylko wtedy, gdy \(H\subset K\) lub \(K\subset H\).

Algebra — Indeks

(image)

Algebra

Indeks

A

algorytm Euklidesa, NWD i NWW w \(Z\)

C

centrum, Podgrupy

D

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}\)

E

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

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

F

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

G

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

I

identyczność Bacheta-Bezouta, NWD i NWW w \(Z\)

iloczyn standardowy, Pojęcie grupy

J

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

L

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

liniowe równanie diofantyczne, NWD i NWW w \(Z\)

M

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

monoid, Pojęcie grupy

N

NWD, NWW, NWD i NWW w \(Z\)

P

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

R

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

rząd grupy, Pojęcie grupy

T

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

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

U

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