Основное содержание
Информатика
Course: Информатика > Модуль 2
Урок 5: Модульная арифметика- Что такое модульная арифметика?
- Оператор модуля
- Испытание по модульной арифметике
- Равенство по модулю
- Отношение равенства
- Отношения эквивалентности
- Теорема о делимости целых чисел с остатком
- Сложение и вычитание по модулю
- Сложение по модулю
- Испытание по теме «Модульная арифметика» (сложение и вычитание)
- Умножение по модулю
- Умножение по модулю
- Возведение в степень по модулю
- Быстрое возведение в степень по модулю
- Быстрое возведение в степень по модулю
- Обратное число по модулю
- Алгоритм Евклида
Отношения эквивалентности
Отношения эквивалентности
Прежде всего важно понимать, что следующие выражения эквивалентны
- C, space, vertical bar, space, left parenthesis, A, minus, B, right parenthesis (Символ | означает «делит», то есть является делителем)
- A, equals, B, plus, K, dot, C (здесь K — это некое целое число)
Это поможет нам переключаться между разными способами выражения одной и той же мысли.
Например, следующие выражения эквивалентны:
- 5, space, vertical bar, space, left parenthesis, 13, minus, 23, right parenthesis, left parenthesis, 5, space, vertical bar, space, minus, 10 верно, поскольку 5, times, left parenthesis, minus, 2, right parenthesis, equals, minus, 10, right parenthesis
- 13, equals, 23, plus, K, dot, 5. Для этого подойдёт K, equals, minus, 2: 13, equals, 23, plus, left parenthesis, minus, 2, right parenthesis, times, 5
Сравнение по модулю — это отношение эквивалентности
Убедитесь, что секторы из предыдущего примера обладают следующими свойствами.
- Все значения в одном секторе попарно связаны друг с другом.
- Каждое значение встречается не более чем в одном секторе (секторы взаимно непересекаются).
- Если собрать вместе все секторы, получится «пирог» из всех возможных целых чисел.
Пирог, куски которого обладают этими свойствами, называется отношением эквивалентности.
Отношение эквивалентности определяет, как именно следует разрезать наш пирог (то есть как мы разобъём множество всех значений) на куски (классы эквивалентности).
Отношение эквивалентности определяет, как именно следует разрезать наш пирог (то есть как мы разобъём множество всех значений) на куски (классы эквивалентности).
В общем случае, отношение эквивалентности задаётся следующими тремя свойствами.
- Пирог — это все интересующие нас значения
- Кусок (или сектор) пирога — класс эквивалентности
- Принцип разрезания пирога на куски — соотношение эквивалентности
В частности, для предыдущего примера:
- Пирог — множество всех целых чисел
- Кусок пирога с пометкой B — это класс эквивалентности, в котором все значения start text, m, o, d, space, end text, C, equals, B
- Принцип разрезания пирога на куски — отношение сравнения по модулю C, то есть \equiv, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
Именно поэтому сравнение по модулю C — это отношение эквивалентности. Оно разделяет множество целых чисел на C различных классов эквивалентности.
Почему нам так важно, что сравнение по модулю C — это отношение эквивалентности?
Выяснив, что сравнение по модулю C — это отношение эквивалентности, давайте разберём несколько присущих ему свойств.
Отношения эквивалентности — это отношения, обладающих следующими свойствами.
Отношения эквивалентности — это отношения, обладающих следующими свойствами.
- Они рефлексивны, то есть A эквивалентно A.
- Они симметричны, то есть если A эквивалентно B, то B эквивалентно A.
- Они транзитивны, то есть если A эквивалентно B, а B эквивалентно C, то A эквивалентно C.
Поскольку сравнение по модулю C — это отношение эквивалентности, следовательно:
- Если A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis, тогда B, \equiv, A, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
- Если A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis и B, \equiv, D, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis, тогда A, \equiv, D, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
Пример
Рассмотрим эти свойства на конкретном примере — сравнения по start text, m, o, d, space, end text, 5.
- 3, \equiv, 3, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (свойство рефлексивности).
- Если 3, \equiv, 8, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis, то 8, \equiv, 3, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (свойство симметричности).
- Если 3, \equiv, 8, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis и 8, \equiv, 18, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis, то 3, \equiv, 18, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (свойство транзитивности).
Хотите присоединиться к обсуждению?
Пока нет ни одной записи.