Модульная арифметика и классы эквивалентности

Модульная арифметика неявно приводит к ещё одной важной штуке в изучении алгебре — понятию эквивалентности. Пятиклассник, который всё никак не уйдёт от моих постов, знает только один вид эквивалентности — равентство, когда 4=4 или неравенство, когда 5≠7. Но вообще так-то нам даже для модульной арифметики пришлось вводить ≡, и можно подобным же образом ввести ≢, чтобы записывать выражения в духе 15 ≡ 3 (mod 12) и 16 ≢ 3 (mod 12). Словами на часах это будет «3 часа дня всегда три часа дня, а четыре часа дня никогда не три часа дня» (для душнил заметим, что пятикласснику незачем грузить себя таймзонами).

И дальше можно обощать это: по аналогии с бинарной операцией *, для соотношения эквивалентности можно ввести ~, чтобы говорить что «15 это эквивалентно трём по модулю 12». Это подводит к прикольной идее о наличии классов эквивалетности и необходимости их формально обсуждать. Ну типа потому что получается что операция взятия остатка от по модулю "разбивает" исследуемую группу (или множество) на родственные между собой подгруппы. Для этого вводят обычно следующее определение

Соотношение ~ на множестве 𝘟 является соотношением эквивалентности тогда и только тогда когда

1️⃣ Оно рефлексивно:
∀x∈𝘟, x~x

2️⃣ Оно симметрично:
∀x,y∈𝘟, если x~y то и y~x

3️⃣ Оно транзитивно:
∀x,y,z∈𝘟, если x~y и y~z, то x~z

Я же говорил, что рефлексия пригодится в математике! Прикольная особенность, на которую стоит обратить внимание, что хотя эта штука используется с двумя элементами, она формально не является бинарной операцией в том же смысле как бинарная операция . В группе у нас элементы xy приводят нас в элемент какой-то тоже той же группы, например, а тут как бы нет такого, выражение x~y нас никуда не "приводит". Тут программисты потянутся к типизации и булевым типам, но у нас тут с вами нормальный пятиклассник, надеюсь, он такой ерундой голову себе пока не забил. (Мы ему потом поможем её забить этим сами)

Но программиста всё же можно порадовать тем, что эти все классы эквивалентности, а также то, как смежные классы разбивают группу (или множество) на подгруппы (подмножества). Оно тоже называется знакомо — партиционирование. Само понятие эквивалентности в криптографии помогает определять классы эквивалентности ключей, в базах данных оптимизировать запросы и индексацию, а в распределённых системах балансировать нагрузку и шардировать всякое туда-сюда.