Основное содержание
Информатика
Course: Информатика > Модуль 2
Урок 5: Модульная арифметика- Что такое модульная арифметика?
- Оператор модуля
- Испытание по модульной арифметике
- Равенство по модулю
- Отношение равенства
- Отношения эквивалентности
- Теорема о делимости целых чисел с остатком
- Сложение и вычитание по модулю
- Сложение по модулю
- Испытание по теме «Модульная арифметика» (сложение и вычитание)
- Умножение по модулю
- Умножение по модулю
- Возведение в степень по модулю
- Быстрое возведение в степень по модулю
- Быстрое возведение в степень по модулю
- Обратное число по модулю
- Алгоритм Евклида
Равенство по модулю
Сравнение по модулю
Вы можете встретить следующее выражение:
Это значит, что равно по модулю .
Обсудим сравнение по модулю, проделав мысленный эксперимент с оператором деления по модулю.
Представим, что мы делим по модулю 5 все целые числа:
Подпишем 5 секторов цифрами 0, 1, 2, 3 и 4. Затем, каждое целое число мы записываем в сектор, соответствующий результату деления этого числа по модулю 5.
Представьте, что сектор — это корзина, в которую помещаются числа. Например, число 26 положим в корзину с подписью 1, поскольку .
На рисунке выше приведены примеры чисел, которые окажутся в каждом из секторов.
Представьте, что сектор — это корзина, в которую помещаются числа. Например, число 26 положим в корзину с подписью 1, поскольку
На рисунке выше приведены примеры чисел, которые окажутся в каждом из секторов.
Было бы полезно придумать способ как обозначить числа, оказавшиеся в одном секторе. (Обратите внимание, что число 26 в примере выше оказалось в одном секторе с числами 1, 6, 11, 16, 21).
Как правило, чтобы показать, что два значения находятся в одном секторе, говорят, что они принадлежат одному классу эквивалентности.
В случае с модулем C математическое обозначение выглядит так:
В случае с модулем C математическое обозначение выглядит так:
Читается это выражение так: равно (или тождественно) по модулю .
Изучим его подробнее:
— это символ тождества, то есть и принадлежат одному классу эквивалентности. говорит о том, какая операция должна быть проделана с и .- Встретив оба этих обозначения, мы называем “
“ тождеством или равенством по модулю .
например,
Обратите внимание, что это не то же самое что : .
Подробнее о сравнении по модулю
Мы можем изучить свойства сравнения по модулю, проведя тот же мысленный эксперимент над натуральным числом .
Сначала отметим секторы числами .
Затем мы поместим каждое целое число в сектор, соответствующий этому целому числу .
Ниже на иллюстрации приведены примеры чисел, которые окажутся в каждом секторе.
Сначала отметим
Затем мы поместим каждое целое число в сектор, соответствующий этому целому числу
Ниже на иллюстрации приведены примеры чисел, которые окажутся в каждом секторе.
Если взглянуть на корзину с надписью 0, мы найдём в ней:
Если мы заглянем в корзину с надписью 1, то мы там обнаружим:
Если мы заглянем в корзину с надписью 2, то мы там обнаружим:
Если мы заглянем в корзину с , то мы там обнаружим:
Из этого эксперимента мы можем сделать следующий вывод.
Числа в каждой из корзин равняются подписи плюс-минус некое кратное числу .
Это значит, что разность между любыми двумя числами в одном секторе — это целое число, кратное .
Это наблюдение поможет нам понять дальнейшие эквивалентные выражения и классы эквивалентности.
Числа в каждой из корзин равняются подписи плюс-минус некое кратное числу
Это значит, что разность между любыми двумя числами в одном секторе — это целое число, кратное
Это наблюдение поможет нам понять дальнейшие эквивалентные выражения и классы эквивалентности.
Хотите присоединиться к обсуждению?
Пока нет ни одной записи.