Przejdź do zawartości

Teoria grup przemiennych/Chińskie twierdzenie o resztach

Z Wikibooks, biblioteki wolnych podręczników.

Problem najmniejszej wspólnej wielokrotności (NWW) liczb całkowitych ni można przeformułować jako układ kongruencji: x ≡ 0 mod ni. To pozwala go uogólnić, wprowadzając „niejednorodność” w sensie niezerowych reszt: xai mod ni. Taki układ kongruencji znany jest jako chiński problem reszt. Parametry tych kongruencji (ni) bywają nazywane modułami.

Takie zagadki mogą się wydawać czysto akademickie lub rozrywkowo-sportowe, z zastosowaniem głównie w konkursach matematycznych, ale okazują się bardzo cenne. Przykładowo można tak dość szybko policzyć zgromadzonych ludzi, np. żołnierzy w oddziale. Można im kazać najpierw się ustawić w dwuszeregu, a potem w trójszeregu. Bez sprawdzania liczby par i trójek można szybko zobaczyć, czy ktoś zostaje bez kompletu; czy liczba osób jest parzysta (x mod 2) i jaką resztę daje w dzieleniu przez trzy (x mod 3). Jest tu 6 możliwych przypadków:

  • x ≡ 0 mod 2, x ≡ 0 mod 3:
  • x ≡ 0 mod 2, x ≡ 1 mod 3:
  • x ≡ 0 mod 2, x ≡ 2 mod 3:
  • x ≡ 1 mod 2, x ≡ 0 mod 3:
  • x ≡ 1 mod 2, x ≡ 1 mod 3:
  • x ≡ 1 mod 2, x ≡ 2 mod 3:

Okazuje się, że taki układ zawsze daje się rozwiązać – niezależnie od modułów, ich reszt ani nawet liczby kongruencji. Fakt ten nazywa się chińskim twierdzeniem o resztach. Fakt ten nie jest tylko dygresją o własnościach kongruencji liczb całkowitych; wtedy znalazłby się w dodatku. ChToR znalazło się w głównej treści kursu, bo opisuje pewien izomorfizm grup – a konkretniej rozkład skończonych grup cyklicznych na grupy p-cykliczne.

Fakt ten można uogólnić, tzn. rozważać w innych kontekstach niż liczby całkowite; przykładem są tutaj wielomiany. Przykładem rozwiązania chińskiego problemu reszt dla wielomianów jest np. interpolacja Lagrange’a. Relacje podzielności, kongruencji i ich układy można też rozważać w innych grupach przemiennych wzbogaconych o działanie mnożenia rozdzielnego względem dodawania, zwanych pierścieniami; jednak jest to temat bardzo rozległy, hermetyczny i wybiegający daleko poza ten kurs.


« Małe twierdzenie Fermata