Основное содержание
Информатика
Course: Информатика > Модуль 2
Урок 5: Модульная арифметика- Что такое модульная арифметика?
- Оператор модуля
- Испытание по модульной арифметике
- Равенство по модулю
- Отношение равенства
- Отношения эквивалентности
- Теорема о делимости целых чисел с остатком
- Сложение и вычитание по модулю
- Сложение по модулю
- Испытание по теме «Модульная арифметика» (сложение и вычитание)
- Умножение по модулю
- Умножение по модулю
- Возведение в степень по модулю
- Быстрое возведение в степень по модулю
- Быстрое возведение в степень по модулю
- Обратное число по модулю
- Алгоритм Евклида
Равенство по модулю
Сравнение по модулю
Вы можете встретить следующее выражение:
Это значит, что A равно B по модулю C.
Обсудим сравнение по модулю, проделав мысленный эксперимент с оператором деления по модулю.
Представим, что мы делим по модулю 5 все целые числа:
Подпишем 5 секторов цифрами 0, 1, 2, 3 и 4. Затем, каждое целое число мы записываем в сектор, соответствующий результату деления этого числа по модулю 5.
Представьте, что сектор — это корзина, в которую помещаются числа. Например, число 26 положим в корзину с подписью 1, поскольку 26, start text, space, m, o, d, space, end text, 5, equals, 1.
На рисунке выше приведены примеры чисел, которые окажутся в каждом из секторов.
Представьте, что сектор — это корзина, в которую помещаются числа. Например, число 26 положим в корзину с подписью 1, поскольку 26, start text, space, m, o, d, space, end text, 5, equals, 1.
На рисунке выше приведены примеры чисел, которые окажутся в каждом из секторов.
Было бы полезно придумать способ как обозначить числа, оказавшиеся в одном секторе. (Обратите внимание, что число 26 в примере выше оказалось в одном секторе с числами 1, 6, 11, 16, 21).
Как правило, чтобы показать, что два значения находятся в одном секторе, говорят, что они принадлежат одному классу эквивалентности.
В случае с модулем C математическое обозначение выглядит так: A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
В случае с модулем C математическое обозначение выглядит так: A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
Читается это выражение так: A равно (или тождественно) B по модулю C.
Изучим его подробнее:
- \equiv — это символ тождества, то есть A и B принадлежат одному классу эквивалентности.
- left parenthesis, start text, m, o, d, space, end text, C, right parenthesis говорит о том, какая операция должна быть проделана с A и B.
- Встретив оба этих обозначения, мы называем “\equiv“ тождеством или равенством по модулю C.
например, 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, значит, оно находится в одном классе эквивалентности с 1,
11, start text, space, m, o, d, space, end text, 5, equals, 1, значит, оно также находится в одном классе эквивалентности с 1.
11, start text, space, m, o, d, space, end text, 5, equals, 1, значит, оно также находится в одном классе эквивалентности с 1.
Обратите внимание, что это не то же самое что 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.
Подробнее о сравнении по модулю
Мы можем изучить свойства сравнения по модулю, проведя тот же мысленный эксперимент над натуральным числом C.
Сначала отметим C секторы числами 0, comma, 1, comma, 2, comma, dots, comma, C, minus, 2, comma, C, minus, 1.
Затем мы поместим каждое целое число в сектор, соответствующий этому целому числу start text, m, o, d, space, end text, C.
Ниже на иллюстрации приведены примеры чисел, которые окажутся в каждом секторе.
Сначала отметим C секторы числами 0, comma, 1, comma, 2, comma, dots, comma, C, minus, 2, comma, C, minus, 1.
Затем мы поместим каждое целое число в сектор, соответствующий этому целому числу start text, m, o, d, space, end text, C.
Ниже на иллюстрации приведены примеры чисел, которые окажутся в каждом секторе.
Если взглянуть на корзину с надписью 0, мы найдём в ней:
Если мы заглянем в корзину с надписью 1, то мы там обнаружим:
Если мы заглянем в корзину с надписью 2, то мы там обнаружим:
Если мы заглянем в корзину с C, minus, 1, то мы там обнаружим:
Из этого эксперимента мы можем сделать следующий вывод.
Числа в каждой из корзин равняются подписи плюс-минус некое кратное числу C.
Это значит, что разность между любыми двумя числами в одном секторе — это целое число, кратное C.
Это наблюдение поможет нам понять дальнейшие эквивалентные выражения и классы эквивалентности.
Числа в каждой из корзин равняются подписи плюс-минус некое кратное числу C.
Это значит, что разность между любыми двумя числами в одном секторе — это целое число, кратное C.
Это наблюдение поможет нам понять дальнейшие эквивалентные выражения и классы эквивалентности.
Хотите присоединиться к обсуждению?
Пока нет ни одной записи.