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.
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.
Dowód. Ćwiczenie. □
Z powyższej własności otrzymujemy natychmiastowy
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).