Teoria liczb II | Informatyka MIMUW

Arytmetyka modularna

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:

$a\ \equiv_{n}a$ ,

$a\ \equiv_{n}b$ wtedy i tylko wtedy, gdy $b\ \equiv_{n}a$ ,

jeśli $a\ \equiv_{n}b$ i $b\ \equiv_{n}c$ to $a\ \equiv_{n}c$ .

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:

jeśli $a\ \equiv_{n}b$ i $c\ \equiv_{n}d$ , to $a+c\ \equiv_{n}b+d$ ,

jeśli $a\ \equiv_{n}b$ i $c\ \equiv_{n}d$ , to $a-c\ \equiv_{n}b-d$ ,

jeśli $a\ \equiv_{n}b$ i $c\ \equiv_{n}d$ , to $ac\ \equiv_{n}bd$ .

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:

$[a]_n + [b]_n = [a+b]_n$ ,

$[a]_n - [b]_n = [a-b]_n$ ,

$[a]_n \cdot [b]_n = [a\cdot b]_n$ ,

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

$3+5\ \equiv_{6}2$ ,

$3-5\ \equiv_{6}4$ ,

$3 \cdot 5\ \equiv_{6}3$ .

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

$15=3\cdot5\equiv_7 10\cdot5=50$ oraz $5\perp7$ implikuje $3\equiv_7 10$ ,

$8=2^3\equiv_3 2$ oraz $2\perp3$ implikuje $4=2^2\equiv_3 1$ .

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

Rozwiązywanie równań modularnych

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:

jeśli ${\sf NWD}\ (a,n)=1$ ,

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}$ ,

jeśli ${\sf NWD}\ (a,n)=d>1$ ,

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,

ponadto, jeśli $0\leq a,b < n$ , to rozwiązanie $0\leq x_0 < n$

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:

policzyć $d:={\sf NWD}\ (a,n)$ oraz współczynniki $y,z$ takie, że $ya+zn=d$ ,

jeśli $d=1$ , to $x_0 =yb \ {\sf mod} \ n$ jest poszukiwanym rozwiązaniem,

jeśli $d>1$ i $d\not| b$ , to równanie nie posiada rozwiązań,

jeśli $d>1$ i $d|b$ , to $y\frac{b}{d}$ jest szukanym rozwiązaniem.

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

${\sf NWD}\ (3,7)=1$ , czyli równanie ma nieskończenie wiele rozwiązań,

$1=1\cdot7-2\cdot3$ ,

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

${\sf NWD}\ (3,12)=3$ , ale $3\not| 4$ , czyli równanie nie ma rozwiązania.

Wreszcie rozważmy równanie $9x\equiv_{21}12$ .

${\sf NWD}\ (9,21)=3$ oraz $3|12$ , czyli równanie ma nieskończenie wiele rozwiązań,

$3=1\cdot21-2\cdot9$ ,

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.

Konstrukcja rozwiązania.

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:

$O(kl)$ na wyliczenie wszystkich iloczynów postaci $N_i$ oraz całego iloczynu $N$ ,

$O(kl^3)$ na wyliczenie kolejnych współczynników $x_i$ , czyli $k$ -krotną aplikację rozszerzonego algorytmu Euklidesa dla liczb $n_i, N_i\leq N$ ,

$O(kl^2)$ na obliczenie $x$ , czyli $O(k)$ mnożeń i dodawań.

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*}$

${\sf NWD}\ (3,10)={\sf NWD}\ (3,11)={\sf NWD}\ (3,7)={\sf NWD}\ (10,11)={\sf NWD}\ (10,7)={\sf NWD}\ (11,7)=1,$

czyli możemy zaaplikować Chińskie Twierdzenie o Resztach,

$N=3\cdot7\cdot10\cdot11=2310$ ,

$N_1=\frac{2310}{3}=770$ ,

$N_2=\frac{2310}{10}=231$ ,

$N_3=\frac{2310}{11}=210$ ,

$N_4=\frac{2310}{7}=330$ .

Zgodnie z procedurą czterokrotnie używamy rozszerzonego algorytmu Euklidesa otrzymując $x_1,\ldots,x_4$ :

${\sf NWD\ }(3,770)=1=257\cdot3-1\cdot770$ , $x_1=-1\equiv_3 2$ ,

${\sf NWD}\ (10,231)=1=-23\cdot10+1\cdot231$ , $x_2=1$ ,

${\sf NWD}\ (11,210)=1=-19\cdot11+1\cdot210$ , $x_3=1$ ,

${\sf NWD}\ (7,330)=1=-47\cdot7+1\cdot330$ , $x_4=1$ .

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*}$

${\sf NWD}\ (2,13)={\sf NWD}\ (2,15)={\sf NWD}\ (13,15)=1$ ,

czyli możemy zaaplikować Chińskie Twierdzenie o Resztach,

$N=2\cdot13\cdot15=390$ ,

$N_1=\frac{390}{2}=195$ ,

$N_2=\frac{390}{13}=30$ ,

$N_3=\frac{390}{15}=26$ ,

${\sf NWD}\ (2,195)=1=-97\cdot2+1\cdot195$ , $x_1=1$ ,

${\sf NWD}\ (13,30)=1=7\cdot13-3\cdot30$ , $x_2=-3\equiv_{13} 10$ ,

${\sf NWD}\ (15,26)=1=7\cdot15-4\cdot26$ , $x_3=-4\equiv_{15}11$ .

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