Chińskie twierdzenie o resztach

Chińskie twierdzenie o resztach mówi, że układ kongruencji:

(1)    x ≡ y1 mod n1,     x ≡ y2 mod n2,         ………………….. ,        x ≡ yk mod nk,

gdzie y1, y2, …, yk są dowolnymi liczbami całkowitymi, a liczby n1, n2, …, nk to liczby parami względnie pierwsze), spełnia dokładnie jedna liczba x z przedzialu:

(2)    1 ≤  x ≤  n1∙ n2∙…∙nk.

Jest to jedno z najważniejszych twierdzeń w teorii liczb i kryptografii.

Nazwa twierdzenia związana jest z chińskim matematykiem Sun Zi, który około roku 100. naszej ery rozwiązał problem znajdowania tych liczb całkowitych, które przy dzieleniu przez 3, 5 oraz 7 dają odpowiednio reszty 2, 3 i 2.

Jak tego dokonał?

Zapewne używał metody generowania kolejnych wielokrotności (która jest mało wydajnym algorytmem, aczkolwiek prawdopodobnie najlepszym do obliczania „ręcznego”):

( 1′)    x≡2 mod 3,    x≡3 mod 5,    x≡2 mod 7.

Ogólne rozwiązanie pierwszego równania wynika bezpośrednio z definicji relacji mod i jest  to x=2 + 3i

Następnie znajdujemy najmniejsze takie i, że x = 2 + 3i spełnia drugie równanie:

wstawiając za i kolejne liczby naturalne otrzymujemy 2 (dla i=0), 5 (dla i=1), 8 (dla i=2),        11 (dla i=3), 14 (dla i=4).

Najmniejsze takie i to 2, bo x=2+3⋅2= 8, zaś 8 mod 5 to rzeczywiście 3.

Z tych dwóch pierwszych równań otrzymujemy zatem kongruencję:

x≡ 8 mod (3∙5)= 8 mod 15.

Ogólne rozwiązanie dwóch pierwszych równań to 8 + (3 · 5)j.

Znajdujemy najmniejsze takie j, że x = 8 + 15j spełnia trzecie równanie:

8 (dla j=0), 23 (dla j=1), 38 (dla i=2), 53 (dla j=3), 68 (dla j=4).

Czyli najmniejsze rozwiązanie to 23, bo 21 mod 7=2.  Zatem ogólne rozwiązanie układu tych trzech kongruencji będzie      x=23 + (3 · 5 ∙7)k, dla k=0,1,2,3,4….

Podobno twierdzenie to służyło w armii chińskiej do przeliczania stanu osobowego żołnierzy. Po ustawieniu żołnierzy kolejno w trójszeregu, pięcioszeregu i siedmioszeregu wystarczyło zanotować ilość żołnierzy, którzy pozostawali poza szeregiem (reszty!). Stan osobowy podawał (wyliczał) algorytm matematyczny.

Istnieje algorytm wyliczania x na podstawie takiego układu równań:

Algorytm rozwiązywania układu kongruencji (1).

Niech M=n1∙n2∙n3∙….∙nk oraz Mi = M / ni (i ≤ k). Wówczas na podstawie założenia  ni oraz Mi są względnie pierwsze i korzystając z rozszerzonego algorytmu Euklidesa istnieją takie liczby całkowite fi, gi (i ≤ k), że

(3)         fi ni +gi Mi =1

Niech ei = gi Mi (i ≤ k). Wówczas

      ei ≡1 mod ni

oraz ei ≡0 mod nj   , gdy j ≠ i.

Wtedy x zdefiniowany wzorem

(4)         x=i=1∑k yiei

spełnia powyższy układ kongruencji; jest to jedno z rozwiązań – pozostałe różnią się o wielokrotność M.

Aby się upewnić sprawdźmy to. Dla dowolnego nio, gdzie 1≤io≤k, mamy:

x (mod nio) ≡i=1∑k yiei  ≡yioeio (mod nio) ≡yio (mod nio) ≡yio,

bo  yiei ≡ 0 (mod nio) dla i≠io, zaś eio ≡ 1 (mod nio).

Czyli rzeczywiście x spełnia układ kongruencji (1).

 

A teraz pytanie dotyczące ilości kongruencji koniecznych do wyznaczenia szukanej liczby x.

Jeśli mielibyśmy dodaną następną kongruencję (8 jest względnie pierwsza z 3, 5 i 7):

x≡ 7 (mod 8)

Sprawdzamy najmniejsze takie k, że x=23+105k spełnia czwarte równanie:

23 (dla k=0), 128 (dla k=1),…

Czyli najmniejsze rozwiązanie to 23 +(3⋅5⋅7⋅8)⋅l=23+840l

Wniosek wynika z nierówności (2). Jeżeli znamy przybliżoną wartość x (lub jego rząd wielkości), to nie ma sensu męczyć żołnierzy nieustannym formowaniem się w szyki. Czyli, po prostu, warto po każdym przeformatowaniu szyku sprawdzić,  czy aktualna wartość ∏ ni przewyższa przewidywaną liczebność żołnierzy.

Przypuśćmy jednak, że dowódca nie zorientował się, że nie warto dalej działać i rozkazał ustawić się w ośmioszeregu (a może chciał sprawdzić, jak daje sobie radę algorytm w takim przypadku?!!). Oto wynik:

x ≡ 7 (mod 8).

Zdradzę sekret utworzenia powyższej kongruencji: Żołnierzy było tylko 23. Ale na razie: cicho, sza!

Można jeszcze dodać, że gdyby żołnierzy było x=23+105⋅2 = 233 (dla k=2), to dodana kongruencja miałaby postać    x ≡ 1 (mod 8).

Stwórzmy tabelkę z Danymi:

1 2 3 4
ni 3 5 7 8
yi 2 3 2 7
Mi 280 168 120 105

Do konstrukcji szukanego x wykorzystamy wzór (4).

Najpierw jednak wykorzystamy moc rozszerzonego algorytmu Euklidesa czyli znajdziemy liczby fi, gi  z równań (3). Zatem:

  1. f1 n1 +g1 M1 = (-93)⋅3+1⋅280 = 1, stąd e1 = 280
  2. f2 n2 +g2 M2 = (-67)⋅5+2⋅168 = 1, stąd e2 = 336
  3. f3 n3 +g3 M3 = (-93)⋅7+1⋅120 = 1, stąd e3 = 120
  4. f4 n4 +g4 M4 = (-13)⋅8+1⋅105 = 1, stąd e4 = 105

Zatem x = 2⋅280 + 3⋅336 + 2⋅120 + 7⋅105 + k⋅840 = 2543 + k⋅840.

Teraz zerknijmy na (2)   i obiecaną przez teorię możność znalezienia rozwiązania zawartego w przedziale       1 ≤  x ≤  n1∙ n2∙…∙n4 = 840

I rzeczywiście, dla k = -3 otrzymamy x = 23.