Processing math: 100%

3.6 Kineska teorema o ostacima

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: r0,r1,,rn1 i m: m0,m1,,mn1 pri čemu za svaki par brojeva niza m važi da su uzajamno prosti. Odrediti najmanji pozitivan broj x za koji važi:

xmodm0=r0xmodm1=r1xmodmn1=rn1

Traži se, dakle, da se reši sledeći sistem kongruencija po modulu.

xr0 (mod m0)xr1 (mod m1)xrn1 (mod mn1)(1)

Teorema 3.6.1. [Kineska teorema o ostacima]

Postoji broj x koji zadovoljava sistem kongruencija (1) i on je jedinstven po modulu M=m0m1mn1.

3.6.1 Gruba sila

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; 
} 

3.6.2 Algoritam zasnovan na prosejavanju

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 m0 daje ostatak r0 onda je on sigurno jedan od članova aritmetičkog niza r0, r0+m0, r0+2m0, U petlji redom proveravamo ove brojeve sve dok ne naiđemo na prvi element koji pri deljenju sa m1 daje ostatak r1. Kada takav broj r01 nađemo (on će biti najmanji pozitivan broj sa osobinom da pri deljenju sa m0 i m1 daje redom ostatke r0 i r1), znamo da će svaki naredni broj koji zadovoljava to svojstvo biti član aritmetičkog niza r01, r01+m0m1, r01+2m0m1, Redom pretražujemo elemente ovog niza dok ne naiđemo na element r012 koji pri deljenju sa m2 daje ostatak r2. Postupak se nastavlja tako što se nakon pronalaženja r012 posmatraju brojevi r012, r012+m0m1m2, r012+2m0m1m2 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 (r0,m0)=(2,3), (r1,m1)=(3,5) i (r2,m2)=(2,7). Važi da je M=m0m1m2=105.

Posmatramo prvo aritmetički niz r0+km0 čiji su članovi 2, 5, 8, 11, itd. i u njemu tražimo prvi broj koji pri deljenju sa m1=5 daje traženi ostatak r1=3. Prvi takav broj je r01=8.

Sada posmatramo niz r01+k(m0m1), tj. niz 8, 23, 38 itd. i u njemu tražimo prvi element koji pri deljenju sa m2=7 daje traženi ostatak 2. To je broj r012=23, koji je konačan rezultat.

3.6.3 Algoritam zasnovan na Lagranževom pristupu

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 w0,w1,,wn1 takve da za svako i važi da wi pri deljenju sa mi (datim u postavci problema) daje ostatak 1, dok pri deljenju sa svim drugim brojevima mj, ji daje ostatak 0, tj. da imamo niz brojeva wi koji zadovoljava uslove date u narednoj tabeli.

mod m0 mod m1 mod mn1
w0 1 0 0
w1 0 1 0
wn1 0 0 1

Množenjem brojeva wi sa ri (datim u postavci problema) dobijaju se brojevi pri deljenju sa mj daju ostatak 0 za ji i ri za j=i. Zato se jedno x koje zadovoljava dati sistem kongruencija može konstruisati kao x=r0w0++rn1wn1. Neka je M=m0m1mn1. Najmanje rešenje x koje zadovoljava sistem kongruencija se dobija kao x=(r0w0++rn1wn1)modM i dokazaćemo da je to jedino rešenje manje od broja M.

Pokazaćemo sada na koji način se mogu konstruisati brojevi wi. Pošto broj wi mora da bude deljiv svim brojevima mj za 0j<n i ji, a oni su uzajamno prosti, on mora biti neki umnožak njihovog proizvoda. Uvedimo oznake za te proizvode. Neka je:

z0=Mm0, z1=Mm1 ,, zn1=Mmn1

Dakle, zi je proizvod svih brojeva mj za 0j<n i ji. Za svako 0i<n važi sledeće:

  1. zi0 (mod mj) za ji;
  2. zi i mi su uzajamno prosti brojevi.
  3. zi pri deljenju sa mi ne daje ostatak 1, nego zimodmi (koji može, ali ne mora biti jednak 1).

Prva dva uslova nam odgovaraju, ali posednji ne. Da bismo od ostatka zimodmi dobili željeni ostatak 1, dobijeni proizvod zi treba nekako podeliti brojem zimodmi. Da radimo sa realnim brojevima, vrednost 1 bismo dobili realnim deljenjem sa zimodmi, tj. množenjem sa koeficijentom 1/(zimodmi). U modularnoj aritmetici deljenje se izvodi množenjem inverznim elementom. Stvar zato možemo popraviti tako što zi pomnožimo modularnim inverzom broja zimodmi po modulu mi (a koji je isti kao modularni inverz broja zi po modulu mi). Naime, množenje bilo kojim brojem ne može narušiti deljivost i svi ostaci koji su bili nula ostaće nula. Broj zi tj. zimodmi ima modularni multiplikativni inverz po modulu mi (jer su zi i mi uzajamno prosti), pa njegovo množenje tim inverzom daje vrednost 1 po modulu mi. Dakle, koeficijent kojim množimo treba da bude jednak modularnom multiplikativnom inverzu broja zi tj. zimodmi po modulu mi. Obeležimo taj inverz sa yi. Važi:

y0z10 (mod m0)y1z11 (mod m1)yn1z1n1 (mod mn1)

Ove inverze možemo odrediti, na primer, proširenim Euklidovim algoritmom. Dakle, ako umesto zi posmatramo brojeve yizi dobijamo brojeve za koje važe oba željena svojstva:

  1. yizi0 (mod mj) za ji;
  2. yizi1 (mod mi).

Ova svojstva nam omogućavaju da definišemo brojeve w0,w1,,wn1 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):

w0=(y0z0)modMw1=(y1z1)modM...wn1=(yn1zn1)modM

Neposredno se proverava da broj

x=(r0w0++rn1wn1)modM

predstavlja rešenje sistema (1) tj. daje ostatak ri pri deljenju sa mi. Naime,

xmodmi=((r0y0z0+r1y1z1++rn1yn1zn1)modM)modmi=(r0y0z0+r1y1z1++rn1yn1zn1)modmi=riyizimodmi=ri

Druga jednakost u ovom nizu važi na osnovu toga što je Mmodmi=0, treća na osnovu toga što je yjzj0 (mod mi) za ji, a četvrta na osnovu svojstva yizi1 (mod mi) i činjenice da je 0ri<mi.

Pokažimo da sva rešenja sistema (1) daju isti ostatak pri deljenju sa M. Razmotrimo dva rešenja x1 i x2. Važi:

m0 | (x1x2), m1 | (x1x2),, mn1 | (x1x2).

S obzirom na to da su svi m0,m1,,mn1 uzajamno prosti, važi i da

m0m1mn1 | (x1x2).

Dakle, važi da je x1x2 (mod M), tj. rešenje je jedinstveno po modulu M=m0m1mn1.

Pošto u intervalu [0,M) ne postoji broj različit od x=(r0w0++rn1wn1)modM 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.

Na ovoj ideji zasniva se i efikasniji algoritam za rešavanje polaznog problema. Pretpostavljamo da su brojevi mi i ri predstavljeni mašinskim tipovima i da je broj uslova (broj n) mali, pa su izračunavanje proizvoda M i proizvoda zi operacije složenosti O(1). Najzahtevnija operacija je pronalaženje modularnih inverza brojeva zi, i ona se izvršava u vremenu O(logM) (jer je ziM), š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: x4 (mod 9)x0 (mod 11)x1 (mod 13)x3 (mod 19)

Označimo sa M=9111319=24453 i sa: z0=M9=2717, z1=M11=2223, z2=M13=1881, z3=M19=1287.

Izračunajmo modularne multiplikativne inverze ovih brojeva: y0=z10=27171mod9=81mod9=8y1=z11=22231mod11=11mod11=1y2=z12=18811mod13=91mod13=3y3=z13=12871mod19=141mod19=15

Na osnovu ovih vrednosti, možemo izračunati potrebne brojeve wi: w0=y0z0modM=82717mod24453=21736w1=y1z1modM=12223mod24453=2223w2=y2z2modM=31881mod24453=5643w3=y3z3modM=151287mod24453=19305

Napokon dobijamo:

x=(r0w0++rn1wn1)modM=(421736+02223+15643+319305)mod24453=3784

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;
}

3.6.4 Algoritam zasnovan na Bezuovoj teoremi

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 m1 i m2, na osnovu Bezuove teoreme mogu se pronaći brojevi y1 i y2 takvi da važi da je y1m1+y2m2=1. Može se lako pokazati da koeficijent y1 predstavlja modularni inverz broja m1 po modulu m2, dok koeficijent y2 predstavlja modularni inverz broja m2 po modulu m1. Zato broj x12=r1y2m2+r2y1m1 tj. njegov ostatak po modulu m1m2, eventualno uvećan za m1m2 ako je negativan, pri deljenju sa m1 daje ostatak r1, a pri deljenju sa m2 daje ostatak r2.

Važi da je

x12=r1y2m2+r2y1m1=r1y2m2+r2y1m1+r1y1m1r1y1m1=r1(y2m2+y1m1)+y1m1(r2r1)=r1+y1m1(r2r1)

Zato je ostatak pri deljenju x12 brojem m1 jednak r1.

Slično se dokazuje i da je x12=r2+y2m2(r1r2) pa je ostatak pri deljenju x12 brojem m2 jednak r2.

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 m1m2 daje ostatak x12, a pri deljenju sa m3 daje ostatak r3. 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 ri i mi 32-bitni celih brojevi i ako se moduli računaju pre i nakon svake operacije množenja. Naime, u formuli (r1y2m2+r2y1m1)mod(m1m2) se množe dva puta po tri 32-bitna broja, a modul m1m2 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 (r1y2m2)mod(m1m2)=m2((r1y2)modm1) i da je (r2y1m1)mod(m1m2)=m1((r2y1)modm2).

Primer 3.6.3. Prikažimo prethodni algoritam na jednom primeru. Neka je (r1,m1)=(2,3), (r2,m2)=(3,5) i (r3,m3)=(2,7). Važi da je M=m0m1m2=105.

Pronađimo prvo brojeve y1 i y2 takve da je y1m1+y2m2=3y1+5y2=1. Važi, na primer, da je y1=2 i y2=1, jer je 32+5(1)=1. Traženi broj je x12=r1y2m2+r2y1m1=2(1)5+323=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 m1m2=15 daje ostatak r12=x12=8, a pri deljenju sa m3=7 daje ostatak r3=2. Zato određujemo brojeve y1 i y2 takve da je 15y1+7y2=1. To mogu biti brojevi y1=1 i y2=2. Traženi broj je tada 87(2)+2151=82 tj. 82+105=23 (pošto je 82 negativan uvećavamo ga za (m1m2)m3=105).

Zadaci: