Prema jednoj kineskoj legendi, general Han Xin je, da bi izbegao da špijuni saznaju sa kolikom je vojskom krenuo u boj, svom kuriru davao samo informaciju o ostatku broja vojnika u pravougaonoj formaciji. Njegove poruke su bile u narednoj formi: “Kada se vojnici organizuju u redove od po \(9\), preostaje njih \(4\); ako su u redovima od po \(11\), niko ne preostaje; ako su u redovima od po \(13\), samo jedan preostaje, a ako su u redovima od po \(19\), preostaje njih trojica”. General je takođe svom kuriru preneo da je broj vojnika drugo najmanje rešenje ovog problema. Pitanje koje se postavlja je kolikim brojem vojnika je general zapovedao. Ovaj problem odgovara tzv. Kineskoj teoremi o ostacima, jednom od standardnih problema elementarne teorije brojeva. Formulišimo ovaj problem u standardnim terminima.
Problem. Data su dva niza brojeva \(r\): \(r_0, r_1,\ldots, r_{n-1}\) i \(m\): \(m_0, m_1,\ldots, m_{n-1}\) pri čemu za svaki par brojeva niza \(m\) važi da su uzajamno prosti. Odrediti najmanji pozitivan broj \(x\) za koji važi:
\[ \begin{array}{lcr} x \,\mathrm{mod}\,m_0 &=& r_0 \\ x \,\mathrm{mod}\,m_1 &=& r_1 \\ &\ldots& \\ x \,\mathrm{mod}\,m_{n-1} &=& r_{n-1} \end{array} \]
Traži se, dakle, da se reši sledeći sistem kongruencija po modulu.
\[ \begin{array}{l} x \equiv r_0\ (\mathrm{mod}\ m_0) \\ x \equiv r_1\ (\mathrm{mod}\ m_1) \\ \ldots \\ x \equiv r_{n-1}\ (\mathrm{mod}\ m_{n-1}) \end{array} \](1)
Teorema 3.6.1. [Kineska teorema o ostacima]
Postoji broj \(x\) koji zadovoljava sistem kongruencija (1) i on je jedinstven po modulu \(M = m_0\cdot m_1\cdot\ldots\cdot m_{n-1}\).
U naivnom pristupu rešavanju ovog problema razmatraju se redom brojevi od \(1\) naviše po skupu prirodnih brojeva i proverava se da li tekući broj zadovoljava date uslove. Pošto uvek postoji broj koji zadovoljava ovaj skup jednačina, na ovaj način bismo došli do rešenja, ali u broju koraka proporcionalnom traženoj vrednosti \(x\), što je u najgorem slučaju \(O(M)\).
int izracunajMinX(const vector<int>& m, const vector<int>& r) {
int n = m.size();
// inicijalizujemo vrednost x
int x = 1;
// prema tvrđenju Kineske teoreme o ostacima
// ova petlja ce se uvek zaustaviti
while (true) {
int j;
// za svako i od 0 do n-1 proveravamo
// da li je ostatak pri deljenju broja x sa m_i jednak r_i
for (i = 0; i < n; i++)
if (x % m[i] != r[i])
break;
// ako su sve iteracije prosle uspesno
// nasli smo vrednost za x
if (i == n)
return x;
// inace nastavljamo sa pretragom
x++;
}
return x;
} Postoji jedan postupak koji nije previše matematički zahtevan, ali koji nije optimalan u smislu efikasnosti (no, mnogo je bolji od grube sile i često uspeva da reši problem unutar zadatih vremenskih ograničenja). Pristup je zasnovan na pametnoj pretrazi. Ako broj \(x\) sa brojem \(m_0\) daje ostatak \(r_0\) onda je on sigurno jedan od članova aritmetičkog niza \(r_0\), \(r_0 + m_0\), \(r_0 + 2m_0\), \(\ldots\) U petlji redom proveravamo ove brojeve sve dok ne naiđemo na prvi element koji pri deljenju sa \(m_1\) daje ostatak \(r_1\). Kada takav broj \(r_{01}\) nađemo (on će biti najmanji pozitivan broj sa osobinom da pri deljenju sa \(m_0\) i \(m_1\) daje redom ostatke \(r_0\) i \(r_1\)), znamo da će svaki naredni broj koji zadovoljava to svojstvo biti član aritmetičkog niza \(r_{01}\), \(r_{01} + m_0\cdot m_1\), \(r_{01} + 2\cdot m_0\cdot m_1\), \(\ldots\) Redom pretražujemo elemente ovog niza dok ne naiđemo na element \(r_{012}\) koji pri deljenju sa \(m_2\) daje ostatak \(r_2\). Postupak se nastavlja tako što se nakon pronalaženja \(r_{012}\) posmatraju brojevi \(r_{012}\), \(r_{012} + m_0\cdot m_1 \cdot m_2\), \(r_{012} + 2\cdot m_0\cdot m_1 \cdot m_2\) i tako dalje, sve dok se ne nađe broj koji zadovoljava sva data ograničenja.
Primer 3.6.1. Prikažimo prethodni algoritam na jednom primeru. Neka je \((r_0, m_0) = (2, 3)\), \((r_1, m_1) = (3, 5)\) i \((r_2, m_2) = (2, 7)\). Važi da je \(M = m_0 \cdot m_1 \cdot m_2 = 105\).
Posmatramo prvo aritmetički niz \(r_0 + k\cdot m_0\) čiji su članovi \(2\), \(5\), \(8\), \(11\), itd. i u njemu tražimo prvi broj koji pri deljenju sa \(m_1 = 5\) daje traženi ostatak \(r_1 = 3\). Prvi takav broj je \(r_{01} = 8\).
Sada posmatramo niz \(r_{01} + k\cdot (m_0\cdot m_1)\), tj. niz \(8\), \(23\), \(38\) itd. i u njemu tražimo prvi element koji pri deljenju sa \(m_2 = 7\) daje traženi ostatak \(2\). To je broj \(r_{012} = 23\), koji je konačan rezultat.
Dokažimo tvrđenje kineske teoreme o ostacima. Dokaz je konstruktivan i daje opšti algoritam za konstruisanje traženog broja \(x\).
Dokaz. Osnovna ideja je ista kao i u konstrukciji Lagranžovog interpolacionog polinoma. Pretpostavimo da umemo da odredimo cele brojeve \(w_0,w_1,\ldots, w_{n-1}\) takve da za svako \(i\) važi da \(w_i\) pri deljenju sa \(m_i\) (datim u postavci problema) daje ostatak \(1\), dok pri deljenju sa svim drugim brojevima \(m_j,\ j\neq i\) daje ostatak \(0\), tj. da imamo niz brojeva \(w_i\) koji zadovoljava uslove date u narednoj tabeli.
| mod \(m_0\) | mod \(m_1\) | … | mod \(m_{n-1}\) | |
|---|---|---|---|---|
| \(w_0\) | 1 | 0 | … | 0 |
| \(w_1\) | 0 | 1 | … | 0 |
| … | … | … | … | … |
| \(w_{n-1}\) | 0 | 0 | … | 1 |
Množenjem brojeva \(w_i\) sa \(r_i\) (datim u postavci problema) dobijaju se brojevi pri deljenju sa \(m_j\) daju ostatak \(0\) za \(j \neq i\) i \(r_i\) za \(j=i\). Zato se jedno \(x\) koje zadovoljava dati sistem kongruencija može konstruisati kao \(x=r_0\cdot w_0+\ldots+r_{n-1}\cdot w_{n-1}\). Neka je \(M=m_0\cdot m_1\cdot \ldots \cdot m_{n-1}\). Najmanje rešenje \(x\) koje zadovoljava sistem kongruencija se dobija kao \(x=(r_0\cdot w_0+\ldots+r_{n-1}\cdot w_{n-1}) \,\mathrm{mod}\,M\) i dokazaćemo da je to jedino rešenje manje od broja \(M\).
Pokazaćemo sada na koji način se mogu konstruisati brojevi \(w_i\). Pošto broj \(w_i\) mora da bude deljiv svim brojevima \(m_j\) za \(0 \leq j < n\) i \(j \neq i\), a oni su uzajamno prosti, on mora biti neki umnožak njihovog proizvoda. Uvedimo oznake za te proizvode. Neka je:
\[z_0 = \frac{M}{m_0},\ z_1 = \frac{M}{m_1}\ ,\ldots,\ z_{n-1} = \frac{M}{m_{n-1}}\]
Dakle, \(z_i\) je proizvod svih brojeva \(m_j\) za \(0 \leq j < n\) i \(j \neq i\). Za svako \(0\leq i < n\) važi sledeće:
Prva dva uslova nam odgovaraju, ali posednji ne. Da bismo od ostatka \(z_i \,\mathrm{mod}\,m_i\) dobili željeni ostatak \(1\), dobijeni proizvod \(z_i\) treba nekako podeliti brojem \(z_i \,\mathrm{mod}\,m_i\). Da radimo sa realnim brojevima, vrednost \(1\) bismo dobili realnim deljenjem sa \(z_i \,\mathrm{mod}\,m_i\), tj. množenjem sa koeficijentom \(1/(z_i \,\mathrm{mod}\,m_i)\). U modularnoj aritmetici deljenje se izvodi množenjem inverznim elementom. Stvar zato možemo popraviti tako što \(z_i\) pomnožimo modularnim inverzom broja \(z_i \,\mathrm{mod}\,m_i\) po modulu \(m_i\) (a koji je isti kao modularni inverz broja \(z_i\) po modulu \(m_i\)). Naime, množenje bilo kojim brojem ne može narušiti deljivost i svi ostaci koji su bili nula ostaće nula. Broj \(z_i\) tj. \(z_i \,\mathrm{mod}\,m_i\) ima modularni multiplikativni inverz po modulu \(m_i\) (jer su \(z_i\) i \(m_i\) uzajamno prosti), pa njegovo množenje tim inverzom daje vrednost \(1\) po modulu \(m_i\). Dakle, koeficijent kojim množimo treba da bude jednak modularnom multiplikativnom inverzu broja \(z_i\) tj. \(z_i \,\mathrm{mod}\,m_i\) po modulu \(m_i\). Obeležimo taj inverz sa \(y_i\). Važi:
\[\begin{eqnarray*} && y_0 \equiv z_0^{-1}\ (\mathrm{mod}\ m_0) \\ && y_1 \equiv z_1^{-1}\ (\mathrm{mod}\ m_1) \\ && \ldots\\ && y_{n-1} \equiv z_{n-1}^{-1}\ (\mathrm{mod}\ m_{n-1}) \end{eqnarray*}\]
Ove inverze možemo odrediti, na primer, proširenim Euklidovim algoritmom. Dakle, ako umesto \(z_i\) posmatramo brojeve \(y_i\cdot z_i\) dobijamo brojeve za koje važe oba željena svojstva:
Ova svojstva nam omogućavaju da definišemo brojeve \(w_0, w_1, \ldots, w_{n-1}\) koji zadovoljavaju zahteve date u prethodnoj tabeli na sledeći način (računanjem ostatka sa \(M\) svojstva ostaju da važe, a vrednosti brojeva se potencijalno smanjuju što olakšava račun):
\[\begin{eqnarray*} w_0 &=& (y_0\cdot z_0) \,\mathrm{mod}\,M \\ w_1 &=& (y_1\cdot z_1) \,\mathrm{mod}\,M \\ &...& \\ w_{n-1} &=& (y_{n-1}\cdot z_{n-1}) \,\mathrm{mod}\,M \end{eqnarray*}\]
Neposredno se proverava da broj
\[x=(r_0\cdot w_0+\ldots+r_{n-1}\cdot w_{n-1}) \,\mathrm{mod}\,M\]
predstavlja rešenje sistema (1) tj. daje ostatak \(r_i\) pri deljenju sa \(m_i\). Naime,
\[\begin{eqnarray*} x\,\mathrm{mod}\,m_i &=& ((r_0y_0z_0 + r_1y_1z_1 + \ldots + r_{n-1}y_{n-1}z_{n-1}) \,\mathrm{mod}\,M) \,\mathrm{mod}\,{m_i}\\ &=& (r_0y_0z_0 + r_1y_1z_1 + \ldots + r_{n-1}y_{n-1}z_{n-1}) \,\mathrm{mod}\,{m_i}\\ &=& r_iy_iz_i \,\mathrm{mod}\,{m_i}\\ &=& r_i \end{eqnarray*}\]
Druga jednakost u ovom nizu važi na osnovu toga što je \(M \,\mathrm{mod}\,m_i = 0\), treća na osnovu toga što je \(y_j\cdot z_j \equiv 0\ (\mathrm{mod}\ m_i)\) za \(j\neq i\), a četvrta na osnovu svojstva \(y_i\cdot z_i \equiv 1\ (\mathrm{mod}\ m_i)\) i činjenice da je \(0 \leq r_i < m_i\).
Pokažimo da sva rešenja sistema (1) daju isti ostatak pri deljenju sa \(M\). Razmotrimo dva rešenja \(x_1\) i \(x_2\). Važi:
\[m_0\ |\ (x_1-x_2),\ m_1\ |\ (x_1-x_2),\ldots,\ m_{n-1}\ |\ (x_1-x_2).\]
S obzirom na to da su svi \(m_0,m_1,\ldots,m_{n-1}\) uzajamno prosti, važi i da
\[m_0\cdot m_1\cdot \ldots \cdot m_{n-1}\ |\ (x_1-x_2).\]
Dakle, važi da je \(x_1 \equiv x_2\ (\mathrm{mod}\ M)\), tj. rešenje je jedinstveno po modulu \(M = m_0\cdot m_1\cdot \ldots \cdot m_{n-1}\).
Pošto u intervalu \([0,M)\) ne postoji broj različit od \(x=(r_0\cdot w_0+\ldots+r_{n-1}\cdot w_{n-1}) \,\mathrm{mod}\,M\) koji je kongruentan sa \(x\) po modulu \(M\), \(x\) je jedino pozitivno rešenje sistema (1) manje od \(M\). Time je dokazana Kineska teorema o ostacima. \(\Box\)
Na ovoj ideji zasniva se i efikasniji algoritam za rešavanje polaznog problema. Pretpostavljamo da su brojevi \(m_i\) i \(r_i\) predstavljeni mašinskim tipovima i da je broj uslova (broj \(n\)) mali, pa su izračunavanje proizvoda \(M\) i proizvoda \(z_i\) operacije složenosti \(O(1)\). Najzahtevnija operacija je pronalaženje modularnih inverza brojeva \(z_i\), i ona se izvršava u vremenu \(O(\log{M})\) (jer je \(z_i \leq M\)), što je i složenost celog algoritma.
Primer 3.6.2. Vratimo se na polazni primer i izračunajmo kolikom je vojskom general Han Xin rukovodio. Ako sa \(x\) označimo broj vojnika, onda zadate uslove možemo da zapišemo na sledeći način: \[\begin{eqnarray*} &&x \equiv 4\ (\mathrm{mod}\ 9)\\ &&x \equiv 0\ (\mathrm{mod}\ 11)\\ &&x \equiv 1\ (\mathrm{mod}\ 13)\\ &&x \equiv 3\ (\mathrm{mod}\ 19) \end{eqnarray*}\]
Označimo sa \(M=9\cdot 11\cdot 13\cdot 19=24453\) i sa: \(z_0 = \frac{M}{9}=2717,\ z_1 = \frac{M}{11}=2223,\ z_{2} = \frac{M}{13}=1881,\ z_{3} = \frac{M}{19}=1287.\)
Izračunajmo modularne multiplikativne inverze ovih brojeva: \[\begin{eqnarray*} y_0 &=& z_0^{-1}=2717^{-1} \,\mathrm{mod}\,{9} = 8^{-1} \,\mathrm{mod}\,{9} = 8 \\ y_1 &=& z_1^{-1}=2223^{-1} \,\mathrm{mod}\,{11} = 1^{-1} \,\mathrm{mod}\,{11} = 1 \\ y_2 &=& z_2^{-1}=1881^{-1} \,\mathrm{mod}\,{13} = 9^{-1} \,\mathrm{mod}\,{13} = 3 \\ y_3 &=& z_3^{-1}=1287^{-1} \,\mathrm{mod}\,{19} = 14^{-1} \,\mathrm{mod}\,{19} = 15 \end{eqnarray*}\]
Na osnovu ovih vrednosti, možemo izračunati potrebne brojeve \(w_i\): \[\begin{eqnarray*} w_0 &=& y_0\cdot z_0 \,\mathrm{mod}\,M = 8\cdot 2717 \,\mathrm{mod}\,24453 = 21736 \\ w_1 &=& y_1\cdot z_1 \,\mathrm{mod}\,M = 1\cdot 2223 \,\mathrm{mod}\,24453 = 2223 \\ w_2 &=& y_2\cdot z_2 \,\mathrm{mod}\,M = 3\cdot 1881 \,\mathrm{mod}\,24453 = 5643 \\ w_3 &=& y_3\cdot z_3 \,\mathrm{mod}\,M = 15\cdot 1287 \,\mathrm{mod}\,24453 = 19305 \end{eqnarray*}\]
Napokon dobijamo:
\[\begin{eqnarray*} x&=&(r_0\cdot w_0+\ldots+r_{n-1}\cdot w_{n-1}) \,\mathrm{mod}\,M \\ &=& (4\cdot 21736 + 0\cdot 2223+ 1\cdot 5643 + 3\cdot 19305) \,\mathrm{mod}\,{24453} \\ &=& 3784 \end{eqnarray*}\]
S obzirom na to da je rečeno da je broj vojnika drugo najmanje rešenje ovog problema, ukupan broj vojnika jednak je \(x=3784+24453=28237\)
Razmotrimo sada implementaciju rešenja polaznog problema zasnovanog na tvrđenju Kineske teoreme o ostacima. Zasebno su implementirane sabiranja i množenja po modulu (ovim se ostatak pri deljenju računa i češće nego što je to zaista neophodno, ali je dobijeni program pregledniji).
// na osnovu Kineske teoreme o ostacima se izracunava rezultat tako da
// za sve elemente nizova m i a vazi da je rezultat mod m[i] = r[i]
// funkcija vraca da li je rezultat bilo moguce naci
bool kto(int m[], int r[], int n, long long& rezultat) {
// racunamo proizvod svih modula
long long M = 1;
for (int i = 0; i < n; i++)
M *= m[i];
rezultat = 0;
for (int i = 0; i < n; i++) {
// racunamo zi
long long zi = M / m[i];
long long yi;
// racunamo yi kao inverz broja zi po modulu m[i]
if (!modInverz(zi, m[i], yi))
return false;
// na rezultat dodajemo sabirak ri*yi*zi mod M
// funkcija pm racuna proizvod, a zm zbir po modulu M
rezultat = zm(rezultat, pm(r[i], yi, zi, M), M);
}
return true;
}
int main() {
// ucitavamo ulazne podatke
int r[3], m[3];
for (int i = 0; i < 3; i++)
cin >> r[i] >> m[i];
// rezultat izracunavamo na osnovu Kineske teoreme o ostacima
long long rezultat;
if (kto(m, r, 3, rezultat))
// ispisujemo rezultat
cout << rezultat << endl;
return 0;
}Pored opšteg postupka za rešavanje problema za \(k\) ostataka, u slučaju samo dva ostatka postoji i veoma sličan, ali malo drugačije formulisan postupak, koji se zasniva na tome da umemo da rešimo sistem od dve jednačine (dve kongruencije), primenom Bezuove teoreme.
Za uzajamno proste brojeve \(m_1\) i \(m_2\), na osnovu Bezuove teoreme mogu se pronaći brojevi \(y_1\) i \(y_2\) takvi da važi da je \(y_1\cdot m_1 + y_2\cdot m_2 = 1\). Može se lako pokazati da koeficijent \(y_1\) predstavlja modularni inverz broja \(m_1\) po modulu \(m_2\), dok koeficijent \(y_2\) predstavlja modularni inverz broja \(m_2\) po modulu \(m_1\). Zato broj \(x_{12} = r_1\cdot y_2 \cdot m_2 + r_2 \cdot y_1\cdot m_1\) tj. njegov ostatak po modulu \(m_1\cdot m_2\), eventualno uvećan za \(m_1 \cdot m_2\) ako je negativan, pri deljenju sa \(m_1\) daje ostatak \(r_1\), a pri deljenju sa \(m_2\) daje ostatak \(r_2\).
Važi da je
\[ \begin{aligned} x_{12} &= r_1\cdot y_2 \cdot m_2 + r_2 \cdot y_1\cdot m_1\\ &= r_1\cdot y_2 \cdot m_2 + r_2 \cdot y_1\cdot m_1 + r_1\cdot y_1\cdot m_1 - r_1\cdot y_1 \cdot m_1\\ &= r_1\cdot (y_2 \cdot m_2 + y_1\cdot m_1) + y_1\cdot m_1\cdot (r_2 - r_1)\\ &= r_1 + y_1\cdot m_1 \cdot (r_2 - r_1) \end{aligned} \]
Zato je ostatak pri deljenju \(x_{12}\) brojem \(m_1\) jednak \(r_1\).
Slično se dokazuje i da je \(x_{12} = r_2 + y_2\cdot m_2 \cdot (r_1 - r_2)\) pa je ostatak pri deljenju \(x_{12}\) brojem \(m_2\) jednak \(r_2\).
Dakle, ako Kinesku teoremu o ostacima primenjujemo na dva broja, ne moramo dva puta nezavisno računati modularni inverz, nego oba potrebna koeficijenta možemo dobiti jednom primenom proširenog Euklidovog algoritma.
Ako ima više brojeva na koje je potrebno primeniti Kinesku teoremu o ostacima, nakon određivanja rešenja za prva dva, isti postupak se primenjuje da se odredi broji koji pri deljenju sa \(m_1\cdot m_2\) daje ostatak \(x_{12}\), a pri deljenju sa \(m_3\) daje ostatak \(r_3\). Ako je \(k > 3\), postupak se nastavlja na isti način, dok se ne dobije konačan rezultat.
Privremeni rezultati mogu da prekorače opseg 64-bitnog tipa, čak iako su svi \(r_i\) i \(m_i\) 32-bitni celih brojevi i ako se moduli računaju pre i nakon svake operacije množenja. Naime, u formuli \((r_1\cdot y_2 \cdot m_2 + r_2 \cdot y_1\cdot m_1) \,\mathrm{mod}\,(m_1\cdot m_2)\) se množe dva puta po tri 32-bitna broja, a modul \(m_1\cdot m_2\) može biti prilično veliki broj (jer je dobijen množenjem dva 32-bitna broja). To se može preduprediti ako se primeti da je \((r_1\cdot y_2\cdot m_2) \,\mathrm{mod}\,(m_1\cdot m_2) = m_2 \cdot ((r_1 \cdot y_2) \,\mathrm{mod}\,m_1)\) i da je \((r_2\cdot y_1\cdot m_1)\,\mathrm{mod}\,(m_1\cdot m_2) = m_1\cdot ((r_2\cdot y_1) \,\mathrm{mod}\,m_2)\).
Primer 3.6.3. Prikažimo prethodni algoritam na jednom primeru. Neka je \((r_1, m_1) = (2, 3)\), \((r_2, m_2) = (3, 5)\) i \((r_3, m_3) = (2, 7)\). Važi da je \(M = m_0 \cdot m_1 \cdot m_2 = 105\).
Pronađimo prvo brojeve \(y_1\) i \(y_2\) takve da je \(y_1\cdot m_1 + y_2\cdot m_2 = 3y_1 + 5y_2 = 1\). Važi, na primer, da je \(y_1=2\) i \(y_2=-1\), jer je \(3 \cdot 2 + 5 \cdot (-1) = 1\). Traženi broj je \(x_{12} = r_1 \cdot y_2 \cdot m_2 + r_2 \cdot y_1 \cdot m_1 = 2 \cdot (-1) \cdot 5 + 3 \cdot 2 \cdot 3 = 8\). On pri deljenju sa \(3\) daje ostatak \(2\), a pri deljenju sa sa \(5\) daje ostatak \(3\).
U narednom koraku tražimo broj takav da pri deljenju sa \(m_1 \cdot m_2 = 15\) daje ostatak \(r_{12} = x_{12} = 8\), a pri deljenju sa \(m_3 = 7\) daje ostatak \(r_3=2\). Zato određujemo brojeve \(y_1'\) i \(y_2'\) takve da je \(15y_1' + 7y_2' = 1\). To mogu biti brojevi \(y_1'=1\) i \(y_2'=-2\). Traženi broj je tada \(8\cdot 7 \cdot (-2) + 2 \cdot 15 \cdot 1 = -82\) tj. \(-82 + 105 = 23\) (pošto je \(-82\) negativan uvećavamo ga za \((m_1m_2)m_3 = 105\)).
Zadaci: