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 ??.
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.
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.
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. □