262080403

MATEMATYKA DYSKRETNA 2010

5.2.3. Chińskie Twierdzenie o Resztach.

Twierdzenie 22 (Sun Ze ok. 450 r.). Niech a,b,n,k będą liczbami całkouńtymi, n,k > 0, n J_ k. Wówczas istnieje dokładnie jedno rozwiązanie xq € Z, 0 < xq < nk układu równań:

{x = a ( mod n) x = b ( mod k)

Co więcej, każde rozwiązanie tego układu różni się od xq o wielokrotność nk.

Dow. ... (Warto znać, bo zawiera algorytm roawiązywania układów modularnych, o których mówi twierdzenie!)

Na koniec wykładu była anegdota o cesarzu (chińskim), a de facto pewne zastosowanie twierdzenia do policzenia liczności zbioru, bez liczenia wszystkich jego elementów.