Przystawanie modulo

Możesz spotkać się z wyrażeniem:

To oznacza, że $A$‍ jest zbieżne do $B$‍ modulo $C$‍.

Przedyskutujemy znaczenie przystawania modulo przeprowadzając następujący eksperyment myślowy z wykorzystaniem operacji dzielenia modulo.

Wyobraźmy sobie, że obliczamy modulo 5 dla wszystkich liczb całkowitych:

Załóżmy, że oznaczyliśmy 5 plastrów liczbami 0, 1, 2, 3, 4. Następnie każdą liczbę całkowitą, stawiamy na kawałek, który indeksuje reszta z dzielenia tej liczby przez 5.
Pomyśl, że plastry są jak kosze, które zawierają w sobie zbiory liczb. Na przykład, 26 włożymy do kawałka oznaczonego przez 1 ponieważ $26\text{ mod }5=\mathbf{1}$‍.
Powyżej znajduje się rysunek przedstawiający niektóre z liczb, które możemy znaleźć w każdym z kawałków.

Przydałoby się nam pojęcie wyrażające fakt, że dane liczby całkowite należą do tego samego kawałka. (Zauważmy, że w powyższym przykładzie 26 znajduje się w tym samym kawałku, co 1, 16, 11, 16, 21).

Aby wyrazić, że dwie liczby znajdują się w tym samym kawałku, mówimy, że należą one do tej samej klasy równoważności.
Relację tą oznaczamy symbolicznie, dla operacji mod C, przez : $A\equiv B(\text{mod }C)$‍

Powyższe wyrażenie wymawia się: $A$‍ jest przystające do $B$‍ modulo $C$‍.

Przeanalizujmy dokładniej powyższe wyrażenie

np. $26\equiv 11(\text{mod }5)$‍

$26\text{ mod }5=1$‍ więc jest to klasa równoważności z 1,
$11\text{ mod }5=1$‍ również jest to klasa równoważności z 1.

Zauważ, że jest to różne od $A\text{ mod }C$‍: $26\ne 11\text{ mod }5$‍.

Możemy zrozumieć lepiej znaczenie przystawania modulo powtarzając ten sam eksperyment myślowy, tyle że z inną dodatnią liczbą całkowitą $C$‍.
Najpierw numerujemy $C$‍ kawałków, $0,1,2,\dots ,C-2,C-1$‍.
Następnie, każdą liczbę całkowitą przyporządkowujemy przyporządkowujemy kawałkowi indeksowanego przez resztę z dzielenia tej liczby przez $\text{mod }C$‍.
Poniżej znajdują się przykładowe przyporządkowania liczb do kolejnych kawałków.

Jeśli zajrzelibyśmy na kawałek indeksowany przez 0, znaleźlibyśmy:

Jeśli zajrzymy do wiaderka oznakowanego 1, znajdziemy:

Jeśli zajrzymy do wiaderka oznakowanego 2, znajdziemy:

Jeśli zajrzymy do wiaderka $C-1$‍ ,znadziemy:

W oparciu o ten eksperyment możemy sformułować następujące spostrzeżenie:
Wartości w każdym z kawałków równe są liczbie indeksującej kawałek, plus lub minus pewna wielokrotność $\mathbf{C}$‍.
Oznacza to, że różnica dowolnych dwu wartości w danym kawałku jest pewną wielokrotnością $\mathbf{C}$‍
Spostrzeżenie to pomoże nam następnie zrozumieć równoważne stwierdzenia i klasy równoważności.