Główna zawartość

Przystawanie modulo

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

A, \equiv, B, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis

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, start text, space, m, o, d, space, end text, 5, equals, 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, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis

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

Przeanalizujmy dokładniej powyższe wyrażenie

\equiv jest symbolem przystawania (kongruencji), który oznacza, że liczby A i B należą do tej samej klasy równoważności.
left parenthesis, start text, m, o, d, space, end text, C, right parenthesis mówi nam, jakie działanie zastosowaliśmy do Ai B.
mając dane jedno i drugie, nazywamy “\equiv” przystawaniem modulo C.

np. 26, \equiv, 11, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis

26, start text, space, m, o, d, space, end text, 5, equals, 1 więc jest to klasa równoważności z 1,
11, start text, space, m, o, d, space, end text, 5, equals, 1 również jest to klasa równoważności z 1.

Zauważ, że jest to różne od A, start text, space, m, o, d, space, end text, C: 26, does not equal, 11, start text, space, m, o, d, space, end text, 5.

Uwagi dotyczące przystawania Modulo

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, comma, 1, comma, 2, comma, dots, comma, C, minus, 2, comma, C, minus, 1.
Następnie, każdą liczbę całkowitą przyporządkowujemy przyporządkowujemy kawałkowi indeksowanego przez resztę z dzielenia tej liczby przez start text, m, o, d, space, end text, 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:

dots, comma, minus, 3, C, comma, minus, 2, C, comma, minus, C, comma, 0, comma, C, comma, 2, C, comma, 3, C, comma, dots

Jeśli zajrzymy do wiaderka oznakowanego 1, znajdziemy:

dots, comma, 1, minus, 3, C, comma, 1, minus, 2, C, comma, 1, minus, C, comma, 1, comma, 1, plus, C, comma, 1, plus, 2, C, comma, 1, plus, 3, C, comma, dots

Jeśli zajrzymy do wiaderka oznakowanego 2, znajdziemy:

dots, comma, 2, minus, 3, C, comma, 2, minus, 2, C, comma, 2, minus, C, comma, 2, comma, 2, plus, C, comma, 2, plus, 2, C, comma, 2, plus, 3, C, comma, dots

Jeśli zajrzymy do wiaderka C, minus, 1 ,znadziemy:

dots, comma, minus, 2, C, minus, 1, comma, minus, C, minus, 1, comma, minus, 1, comma, C, minus, 1, comma, 2, C, minus, 1, comma, 3, C, minus, 1, comma, 4, C, minus, 1, dots

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ść C.
Oznacza to, że różnica dowolnych dwu wartości w danym kawałku jest pewną wielokrotnością C
Spostrzeżenie to pomoże nam następnie zrozumieć równoważne stwierdzenia i klasy równoważności.

Chcesz dołączyć do dyskusji?

Zaloguj się

Sortuj według

Na razie brak głosów w dyskusji

Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.

Informatyka

Kurs: Informatyka > Rozdział 2

Przystawanie modulo