Twierdzenie Chińskie o Resztach

Prezentujemy tutaj:

Podstawowe własności kongruencji.
Dowód Chińskiego Twierdzenia o Resztach.
Podstawowe własności Funkcji Eulera.
Przykładowe implementacje efektywnych algorytmów obliczania powyższych rzeczy. Zamieszczamy tutaj rozwiązywanie układu kongruencji w czasie O(nlogn) oraz obliczanie wartości Funkcji Eulera w czasie O(sqrt(n)).
Zadania z olimpiad zahaczające powyższą tematykę.

Opracowali: Rafał Byczek i Mateusz Tokarz

Przy okazji chciałbym serdecznie podziękować Mateuszowi za jak zwykle udaną współpracę!