Liczby przystające modulo \( n>0 \) to takie dwie liczby \( a,b\in\mathbb{Z} \), dla których różnica \( a-b \) jest wielokrotnością \( n \). Fakt ten zapisujemy jako \( a\ \equiv_{n}b \). Innymi słowy, \( a\ \equiv_{n}b \) jeśli \( a \) i \( b \) mają te same reszty w dzieleniu przez \( n \).
Obserwacja 11.
Dla dowolnych \( a,b,c \) oraz \( n>0 \) zachodzi:
Powyższe własności świadczą o tym, że przystawanie \( \equiv_{n} \) modulo \( n \) jest relacją równoważności na zbiorze \( \mathbb{Z} \). Dlatego czasem relacja ta nazywana jest równością modulo \( n \). Okazuje się też, że relacja \( \equiv_n \) jest zgodna z działaniami arytmetycznymi: dodawania, odejmowania i mnożenia, a więc jest kongruencją ze względu na te działania.
Obserwacja 11.2
Dla dowolnych \( a,b,c,d \) oraz \( n>0 \) mamy:
Podane w dwu poprzednich obserwacjach własności relacji równości modulo \( n \) pozwalają na wprowadzenie działań w zbiorze ilorazowym \( \mathbb{Z}/\equiv_n \), tzn. w zbiorze klas równoważności. \( {\{ {[a]_n : a\in \mathbb{Z}} \} } \), poprzez:
Ponieważ w każdej klasie \( [a]_n \) jest jakaś liczba spośród \( 0,1,2,\ldots,n-1 \), a mianowicie reszta z dzielenia liczby \( a \) przez \( n \), to wygodniej jest po prostu mówić o arytmetyce (modularnej) na zbiorze tych reszt \( {\{ {0,1,2,\ldots,n-1} \} } \) i pisać np.:
Tak więc, dla \( n>0 \) możemy zidentyfikować zbiór ilorazowy \( \mathbb{Z}/\equiv_n \) ze zbiorem \( \mathbb{Z}_n={\{ {0,\ldots n-1} \} } \) reszt modulo \( n \). Po wprowadzeniu do tego zbioru działań arytmetycznych dostajemy pierścień, przemienny z jedynką \( \mathbb{Z}_n=({\{ {0,\ldots n-1} \} },+,\cdot) \). Pierścień ten nie zawsze jest jednak ciałem. Istotnie, nie zawsze możemy skracać w mnożeniu czynnik zachowując kongruencję. Dla przykładu: \( 2\cdot2=4\ \equiv_{6}10 =2\cdot5 \), ale \( 2\not\equiv_6 5 \). Okazuje się, że w równości modulo \( n \) możemy skracać czynniki względnie pierwsze z \( n \).
Obserwacja 11.3 [Reguła skracania]
Dla \( n>0 \), jeśli \( ad\ \equiv_{n}bd \) i \( d\perp n \), to \( a\ \equiv_{n}b \).
Dowód
Ponieważ \( {\sf NWD}\ (d,n)=1 \), rozszerzony algorytm Euklidesa gwarantuje istnienie \( x,y\in \mathbb{Z} \) takich, że \( xd+yn=1 \), czyli \( dx\ \equiv_{n}1 \). Mnożąc teraz obie strony \( ad\ \equiv_{n}bd \) przez \( x \), otrzymujemy \( adx\ \equiv_{n}bdx \), czyli \( a=a1 \equiv_n adx \equiv_n bdx \equiv_n b1=b \).
Przykład
Chcąc móc skracać w pierscieniu \( \mathbb{Z}_n \) dowolne niezerowe czynniki wymagamy, by wszystkie liczby \( 1,2,\ldots,n-1 \) były względnie pierwsze z \( n \). To nic innego, jak wymaganie, by \( n \) było liczbą pierwszą.
Obserwacja 11.4
Pierścień \( \mathbb{Z}_n=({\{ {0,\ldots n-1} \} },+,\cdot) \) jest ciałem, wtedy i tylko wtedy, gdy \( n \) jest liczba pierwszą.
Oczywiście w ciele, każde równanie postaci \( ax=b \) ma dokładnie jedno rozwiązanie \( x \), o ile \( a\neq 0 \). Zobaczmy czy są, jak wyglądają i jak otrzymać rozwiązania \( x \) równania modularnego postaci \( ax\equiv_n b \) w liczbach całkowitych \( x \), gdzie \( a,b\in \mathbb{Z} \) oraz \( a\neq 0 \).
Obserwacja 11.5
Dla \( a,b \in \mathbb{Z}, a\neq 0 \) rozwiązania równania modularnego z jedną niewiadomą \( x \):
\( ax\ \equiv_{n}b , \)
zależą od wielkości \( {\sf NWD}\ (a,n)=1 \) w następujący sposób:
to istnieje nieskończenie wiele rozwiązań; wszystkie one są postaci \( x=x_0+kn \), gdzie \( 0\leq x_0 < n \) jest jakimś rozwiązaniem, a \( k\in\mathbb{Z} \),
to równanie ma rozwiązanie wtedy i tylko wtedy, gdy również \( d|b \). W tym przypadku rozwiązania równania \( ax\ \equiv_{n}b \) pokrywają się z rozwiązaniami równania \( \frac{a}{d}x\ \equiv_{\frac{n}{d}}\frac{b}{d} \).
Ponadto,
równania \( ax\ \equiv_{n}b \), lub jego brak, można wskazać wykonując \( O(lg^3{n}) \) operacji bitowych.
Dowód
Zauważmy najpierw, że jeśli \( a',b' \) są resztami z dzielenia odpowiednio \( a \) i \( b \) przez \( n \), to rozwiązania równań \( ax\ \equiv_{n}b \) i \( a'x\ \equiv_{n}b' \) są takie same. Istotnie, wynika to natychmiast z tego, że \( a'x\ \equiv_{n}ax \) oraz \( b'\ \equiv_{n}b \). Możemy więc przyjąć, że \( 0\leq a,b < n \). Ponadto odnotujmy, że z tych samych powodów, jeśli \( x_0 \) spełnia równanie, to spełnia je również każda liczba postaci \( x_0+kn \), gdzie \( k\in\mathbb{Z} \).
Załóżmy najpierw, że \( {\sf NWD}\ (a,n)=1 \). Rozszerzony algorytm Euklidesa gwarantuje istnienie \( y,z \) takich, że \( 1\ \equiv_{n}ya+zn \equiv_n ya \). Łatwo teraz sprawdzić, że reszta \( x_0 \) z dzielenia \( yb \) przez \( n \) jest rozwiązaniem. A więc i wszystkie liczby postaci \( x_0+kn \), są również rozwiązaniami. Pozostaje pokazać, że wszystkie rozwiązania są takiej właśnie postaci. Niech więc \( ax\equiv_n b\equiv_n ax_0 \). Ponieważ \( a\perp n \), to \( a \) możemy skrócić otrzymując \( x\ \equiv_{n}x_0 \), co implikuje że \( x=x_0+kn \), dla pewnej liczby całkowitej \( k \).
Niech teraz \( {\sf NWD}\ (a,n)=d>1 \). Najpierw pokażemy, że jeśli równanie \( ax\ \equiv_{n}b \) ma rozwiązanie, to \( d|b \). Rzeczywiście, jeśli \( ax_0\ \equiv_{n}b \) dla pewnego \( x_0 \), to \( n|ax-b \), a więc i \( d|ax-b \). Ale \( d|a \), więc \( d|b \). Na odwrót, gdy \( d|b \), to liczby \( a,b,n \) są podzielne przez \( n \). Niech więc \( a'=a/d \), \( b'=b/d \) i \( n'=n/d \). Wtedy \( {\sf NWD}\ (a',n')=1 \) i, na mocy pierwszego punktu, równanie \( a'x\ \equiv_{n'}b' \) ma nieskończenie wiele rozwiązań. Pozostaje pokazać, że są to te same rozwiązania, co dla równania \( ax\ \equiv_{n}b \). Niech więc \( n'|a'x-b' \). Wtedy \( n=dn'|d(a'x-b') = ax-b \). Gdy zaś \( ax\ \equiv_{n}b \), to \( ax=b+kn \) dla pewnego \( k\in\mathbb{Z} \). A zatem \( da'x=db'+kdn' \) i, po wydzieleniu przez \( d>1 \), dostajemy \( a'x=b'+kn' \), czyli \( a'x\ \equiv_{n'}b' \).
Na podstawie dowodu poprzednich dwu punktów wiemy więc, że by rozwiązać równanie \( ax\ \equiv_{n}b \) wystarczy:
W pierwszym punkcie rozszerzony algorytm Euklidesa pracuje w czasie \( O(\lg^3{n}) \), bo \( a,b < n \). W kolejnych punktach wykonywane są jedynie podstawowe operacje arytmetyczne, a więc wykonywanych jest \( O(\lg^2{n}) \) operacji bitowych. Podsumowując, aby znaleźć rozwiązanie rozważanego równania (bądź stwierdzić ich brak) wystarczy \( O(\lg^3{n}) \) operacji bitowych.
Wniosek 11.6
Jeśli \( p \) jest liczbą pierwszą, to równania postaci \( ax\ \equiv_{p}b \) dla dowolnych \( 0 < a < p \) i \( 0\leq b < p \) zawsze mają rozwiązanie i można je znaleźć wykonując \( O(lg^3{p}) \) operacji bitowych.
Przykład
Rozwiążemy równanie \( 3x\equiv_7 4 \).
czyli zbiór rozwiązań to \( {\{ {-2\cdot4+7k: k\in\mathbb{Z}} \} }={\{ {7k-1:k\in\mathbb{Z}} \} } \).
A następnie równanie \( 3x\equiv_{12}4 \).
Wreszcie rozważmy równanie \( 9x\equiv_{21}12 \).
czyli zbiór rozwiązań to \( {\{ {-2\cdot\frac{12}{3}+ \frac{21}{3}k : k\in\mathbb{Z}} \} }={\{ {13+7k : k\in\mathbb{Z}} \} } \).
Czasem jedną kongruencję wygodnie jest zamienić na układ kongruencji wykorzystując następującą własność.
Obserwacja 11.7
Niech \( a,b,m,n\in\mathbb{Z} \), gdzie \( m,n>0 \) i \( m\perp n \). Wtedy \( a\ \equiv_{mn}b \) jest równoważne temu, że równocześnie \( a\ \equiv_{m}b \) i \( a\ \equiv_{n}b \).
Dowód
Jeśli \( a\ \equiv_{mn}b \), to \( mn|a-b \). A więc oczywiście \( m|a-b \) i \( n|a-b \), co jest równoważne z \( a\ \equiv_{m}b \) i \( a\ \equiv_{n}b \). Dla dowodu implikacji odwrotnej, że jest ona trywialna dla \( a=b \) i wobec tego przyjmijmy (bez straty ogólności), że \( a>b \). Załóżmy też, że \( m|a-b \) i \( n|a-b \). Ponieważ \( m\perp n \), to rozkłady liczb \( m \) i \( n \) nie mają wspólnych czynników pierwszych. Natomiast rozkład \( a-b \) musi zawierać wszystkie liczby pierwsze z rozkładów \( m \) i \( n \) w odpowiednio wysokich potęgach. To dowodzi, iż \( mn|a-b \), czyli \( a\ \equiv_{mn}b \).
Poprzednia obserwacja prowadzi do twierdzenia powszechnie znanego jako Chińskie Twierdzenie o Resztach. Udowodnił je chiński matematyk Sun Tzu w III wieku n.e. ( nie mylić z Sun Tzu, myślicielem, filozofem, autorem Sztuki wojny).
Twierdzenie 11.7 [Chińskie twierdzenie o resztach]
Niech \( n_1,\ldots,n_k\in\mathbb{N}-{\{ {0} \} } \) będą parami względnie pierwsze, tzn. \( n_i\perp n_j \) dla \( i\neq j \). Wtedy dla dowolnych \( a_1,\ldots,a_k \) istnieje dokładnie jedna liczba \( 0\leq x < n_1\cdot\ldots\cdot n_k \) taka, że:
\( \begin{align*} x & \equiv_{n_1} & a_1,\nonumber \\ x & \equiv_{n_2} & a_2,\nonumber \\ & \vdots & \\ x & \equiv_{n_k} & a_k.\nonumber \end{align*} \)
Dowód
Niech \( N=n_1\cdot\ldots\cdot n_k \). Dla liczby \( a \) rozważmy ciąg \( \overline{a}=(a_1,\ldots,a_k) \) reszt z dzielenia \( a \) odpowiednio przez \( n_1,\ldots,n_k \).
Niech teraz \( 0\leq a < b < N \). Gdyby \( \overline{a}=\overline{b} \), to
\( \begin{align*} a & \equiv_{n_1} & b, \\ a & \equiv_{n_2} & b, \\ & \vdots & \\ a & \equiv_{n_k} & b. \end{align*} \)
Z drugiej strony \( n_1\ldots n_i \perp n_{i+1} \), więc stosując wielokrotnie Obserwację 11.7 otrzymujemy \( i\ \equiv_{N}j \), czyli \( N|j-i \), co jest niemożliwe wobec \( 0 < j-i < N \). Sprzeczność ta pokazuje, że liczby ze zbioru \( {\{ {0,1,\ldots,N-1} \} } \) mają różne ciągi reszt. Oznacza to, że ciągów postaci \( \overline{a} \) jest dokładnie \( N \), czyli tyle ile wszystkich możliwych ciągów w \( \mathbb{Z}_{n_1}\times\ldots\times\mathbb{Z}_{n_k} \). Tym samym przyporządkowanie \( \mathbb{Z}_N \ni a \mapsto \overline{a} \in \mathbb{Z}_{n_1}\times\ldots\times\mathbb{Z}_{n_k} \) jest bijekcją, co kończy dowód twierdzenia.
Chińskie Twierdzenie o Resztach podaje warunki wystarczające na istnienie rozwiązania układu równań modularnych (1). Nie podaje jednak metody jego uzyskania.
Niech \( N_j=N/n_j \), czyli \( N_j \) jest iloczynem wszystkich \( n_i \) poza \( n_j \). Oczywiście, \( {\sf NWD}\ (n_i,N_i)=1 \). Rozszerzony algorytm Euklidesa pozwala więc znaleźć liczby \( x_i \) takie, że \( N_ix_i\ \equiv_{n_i}1 \). Połóżmy
\( \displaystyle x=\sum_{i=1}^k a_i x_i N_i. \)
Wtedy \( n_i \) dzieli wszystkie czynniki sumy poza \( i \)-tym, ponieważ \( n_i|N_j \) dla \( j\neq i \). A więc, dla dowolnego \( i \) mamy:
\( x\equiv_{n_i}a_ix_iN_i\equiv_{n_i} a_i \cdot 1 =a_i. \)
To oznacza, że \( x \) jest rozwiązaniem układu równań modularnych (1).
Oszacujmy czas działania tego algorytmu. Niech \( l_1,\ldots,l_k \) będą długościami odpowiednio \( n_1,\ldots,n_k \). Wtedy \( N \) ma długość co najwyżej \( l=l_1+\ldots+l_k \). Kroki algorytmu można wykonać kolejno w czasie:
Podsumowując wszystkie kroki zostaną wykonane w czasie \( O(k\lg^3{N}) \).
Przykład
Rozważmy układ równań:
\( \begin{align*} x & \equiv_3 & 2, \\ x & \equiv_{10} & 7, \\ x & \equiv_{11} & 10, \\ x & \equiv_7 & 1. \end{align*} \)
czyli możemy zaaplikować Chińskie Twierdzenie o Resztach,
Zgodnie z procedurą czterokrotnie używamy rozszerzonego algorytmu Euklidesa otrzymując \( x_1,\ldots,x_4 \):
Pozostaje policzyć \( x \):
\( \begin{align*} x & =2\cdot2\cdot770+7\cdot1\cdot231+10\cdot1\cdot210+1\cdot1\cdot330 \\ & =3080+1617+2100+330 \\ & =7127\equiv_{2310} 197. \end{align*} \)
A więc \( 197 \) jest najmniejszym dodatnim rozwiązaniem naszego układu równości.
Przykład
Rozważmy jeszcze jeden układ równań:
\( \begin{align*} x & \equiv_2 & 0, \\ x & \equiv_{13} & 12, \\ x & \equiv_{15} & 2. \end{align*} \)
czyli możemy zaaplikować Chińskie Twierdzenie o Resztach,
Pozostaje nam obliczenie \( x \):
\( \begin{align*} x & =0\cdot1\cdot195+12\cdot10\cdot30+2\cdot26\cdot11=4172\equiv_{390}=272. \end{align*} \)
Zatem \( 272 \) jest najmniejszym dodatnim rozwiązaniem naszego układu równań.