Что такое mod в математике

Учебно-методическое пособие по курсу для студентов

В Модуле 1 изложены основы алгебры логики, принципы работы логических и арифметических устройств ЭВМ, рассмотрены системы счисления и принципы перевода чисел из одной системы счисления в другую.

В Модуле 2 изложены материалы по теме «Алгоритмические языки и программирование», приведены теоретические сведения, примеры программ и варианты индивидуальных заданий.

В начале каждого модуля указаны маршрутные карты, которые определяют последовательность самостоятельного изучения теоретического материала, сроки выполнения практических и индивидуальных заданий, сроки сдачи промежуточных и итоговых тестирований.

Для самостоятельной проверки знаний необходимо пользоваться интерактивным тренингом.

Электронный адрес сайта кафедры для прохождения тренинга:

http :// inf . tltsu . ru / res / strogov /

Составители: Ахмедханлы Д.М., Панюкова Е.В.

Оператор mod — остаток от деления. Что такое mod?

Оператор mod обозначается символом % и является оператором деления по модулю. Он возвращает остаток от деления 1-го операнда на 2-й и широко используется в разных языках программирования для решения ряда задач.

Оператор mod в Java

В Java operator mod может работать как с целыми числами (byte/int/short/long), так и с плавающей точкой (byte/int/short/long). Давайте приведём пример работы оператора mod при делении:

class Modulus  public static void main (String args [])  int x = 42; double у = 42.3; System.out.print("x mod 10 = " + x % 10); System.out.println("y mod 10 = " + у % 10); > >

После выполнения этой программы вы получите результат следующего вида:

х mod 10 = 2 у mod 10 = 2.3

Как видим, оператор mod — это прекрасный способ найти остаток от деления. Зачем это может понадобиться на практике? Например, при нахождении кратности числа и определении, является ли некоторое число, введённое с клавиатуры, чётным. Также с помощью оператора mod можно узнать, делится ли одно число на другое без остатка или определить последнюю цифру числа. В общем, оператор mod очень полезен при решении различных задач по программированию.

Оператор mod в SQL

Не менее интересно использование mod в базах данных. Аналогично, mod находит остаток от деления. При этом вместо mod можно задействовать операцию %, делающую то же самое. Синтаксис в SQL следующий:

SELECT MOD(что_делить, на_что_делить) FROM имя_таблицы WHERE условие

Но можно написать и иначе, используя % :

SELECT что_делить % на_что_делить FROM имя_таблицы WHERE условие

Давайте приведём пример использования mod в базах данных. Вот, например, таблица numbers:

Найдём остаток от деления столбца number на три:

SELECT *, MOD(number, 3) as mod FROM numbers

В результате запрос SQL выберет следующие строки:

Но, как мы уже говорили выше, этот же запрос можно без проблем переписать:

SELECT id, number % 3 as mod FROM numbers

Идём дальше. Теперь возьмём таблицу посложнее:

Здесь найдём остаток от деления столбца number1 на number2:

SELECT *, MOD(number1, number2) as mod FROM numbers

Получим следующие строки:

Опять же, этот же самый запрос можно оформить иначе:

SELECT *, number1 % number2 as mod FROM numbers

А где вы используете mod? Пишите в комментариях!

Учебник. Сравнения по модулю и признаки делимости

Два натуральных числа a и b, разность которых кратна натуральному числу m, называются сравнимыми по модулю m: a ≡ b (mod m).

Так, 3 ≡ 1 (mod 2), 7 ≡ 1 (mod 3). Два числа сравнимы по модулю 2, если они оба четны, либо если они оба нечетны. По модулю 1 все целые числа сравнимы между собой.

В том случае, если число n делится на m, то оно сравнимо с нулем по модулю m: n ≡ 0 (mod m).

Свойства сравнений по модулю вытекают из свойств арифметических операций.

Пусть a ≡ b (mod m), c ≡ d (mod m). Тогда:
- a + c ≡ b + d (mod m),
- a – c ≡ b – d (mod m),
- ac ≡ bd (mod m).
Отметим, что обе части сравнения не всегда можно сократить на какой-либо множитель. Так, 6 ≡ 3 (mod 3), но 2 не сравнимо с 1 по этому же модулю.

Простейшим применением сравнений по модулю является определение делимости чисел. Дадим для начала несколько правил.

Признак делимости на 2. Число, делящееся на 2, называется чётным, не делящееся на 2 – нечётным. Число делится на 2 тогда и только тогда, когда его последняя цифра делится на 2.

Признак делимости на 5. Число делится на 5 тогда и только тогда, когда его последняя цифра – 5 или 0.

Признак делимости на 25. Число делится на 25 тогда и только тогда, когда две его последние цифры либо нули, либо образуют число, делящееся на 25.

Признаки делимости на 10, 100, 1000. Число делится на 10 тогда и только тогда, когда его последняя цифра – 0. Число делится на 100 тогда и только тогда, когда две его последние цифры – нули. Число делится на 1000 тогда и только тогда, когда три его последние цифры – нули.

Признак делимости на 4. Число делится на 4 тогда и только тогда, когда две его последние цифры – нули, либо когда двузначное число, образованное двумя его последними цифрами, делится на 4.

Признак делимости на 3. Число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3.

Признак делимости на 9. Число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9.

Признак делимости на 11. Число делится на 11 тогда и только тогда, когда сумма его цифр, стоящих на нечётных местах, либо равна сумме цифр, стоящих на чётных местах, либо отличается от неё на число, кратное 11.

Доказать свойство делимости на 9: число делится на 9 тогда и только тогда, когда сумма всех его цифр делится на 9.

Произвольное число x = x n . x 2 x 1 ¯ = x 1 + x 2 ċ 10 1 + x 3 ċ 10 2 + . + x n ċ 10 n - 1 , где x 1 , . x n – цифры числа x в десятичной записи. Так как 10 ≡ 1 (mod 9), то 10 2 ≡ 1 (mod 9) и вообще 10 k ≡ 1 (mod 9) для любого натурального k. Отсюда x 1 + x 2 ċ 10 + . + x n ċ 10 n - 1 ≡ x 1 + x 2 + . + x n ( mod 9 ) . Теорема доказана.

Доказать, что число делится без остатка на 19 тогда и только тогда, когда число его десятков, сложенное с удвоенным числом единиц, кратно 19.

Для любого натурального x верно равенство x = x₁ + 10x₂, где x₁ – число единиц, x₂ – число десятков этого числа. Пусть y = x₂ + 2x₁ (то есть y – число десятков, сложенное с удвоенным числом единиц). Тогда 10y – x = 19x₁ ≡ 0 (mod 19), откуда следует, что x ≡ 0 (mod 19) тогда и только тогда, когда 10y ≡ 0 (mod 19), то есть y ≡ 0 (mod 19). Утверждение доказано.

В заключение этого параграфа приведем формулировку малой теоремы Ферма.

Пусть p – простое число, a – натуральное число. Тогда a p – a делится на p: a p ≡ a (mod p).

В частности, если p – простое число, a – натуральное число, взаимно простое с p, то a p – 1 ≡ 1 (mod p).

Запишите состоящее из одних девяток натуральное число, которое делится на 17 без остатка.

Воспользуемся малой теоремой Ферма: a p – 1 ≡ 1 (mod p). Положим a = 10, p = 17. Тогда 10 16 ≡ 1 (mod 17) или 10 16 – 1 ≡ 0 (mod 17). Число 10 16 – 1 состоит из 16 девяток. Это и есть одно из чисел, которые делятся на 17 без остатка.

Ответ. 9 999 999 999 999 999.

[математикам]что такое mod?

в методичке по криптографии постоянно встречаются формулы вида этой:

Что такое mod? Простой остаток от деления e^-1 на p-1?

Судя по всему нет, т.к. вот пример из той же методички:

d = e^-1 (mod p-1) = 42239^-1 (mod(52631-1) = 32229

Как это считается?

p.s. Да, математика в институте была >5 лет назад, и она вовсе не мой конек.

Turbid ★★★★★
22.06.09 02:40:55 MSD

Re: [математикам]что такое mod?

а вроде всегда это был остаток от деления. число, не превосходящее делитель.

gunja ★
( 22.06.09 04:12:36 MSD )

Re: [математикам]что такое mod?

если по простому, то это как будто "зацикленное" отнимание. т.е. какое останется число k, если от числа n отнять число m максимум полных раз.
например. 11 mod 3 = 2. число 11 это 3+3+3+2. результат - 2. 61 mod 26 = 9. 61 это 26+26+9.

//читаю лекции по криптографии у людей с большими провалами в математике, даже поля Галуа и теорему Ейлера можно объяснить на пальцах, ящитаю

val-amart ★★★★★
( 22.06.09 05:07:04 MSD )

Re: [математикам]что такое mod?

про (mod p-1) уже сказали, но

> d = e^-1 (mod p-1) = 42239^-1 (mod(52631-1) = 32229

либо очепятка, либо ошибка:

a^=b(mod c) если a*b=1(mod c), но у тут

pupok ★★
( 22.06.09 05:22:44 MSD )

Re: [математикам]что такое mod?

кури теорию чисел

irq ★
( 22.06.09 06:03:22 MSD )

Re: [математикам]что такое mod?

Ужас. Закрывай методичку, открывай теорию чисел. А то что будет, когда дискретные логарифмы (ЕМНИП, ГОСТовское шифрование на них основано, но тут могу ошибаться, лет 10 криптографию не трогал) встретишь и т.д.

~~redgremlin~~ ★★★★★
( 22.06.09 07:07:07 MSD )
Ответ на: Re: [математикам]что такое mod? от val-amart 22.06.09 05:07:04 MSD

Re: [математикам]что такое mod?

ОМГ, так это ты подпускаешь людей без знания математики к криптографии?

spunky ★★
( 22.06.09 07:31:05 MSD )
Ответ на: Re: [математикам]что такое mod? от val-amart 22.06.09 05:07:04 MSD

Re: [математикам]что такое mod?

> //читаю лекции по криптографии у людей с большими провалами в математике, даже поля Галуа и теорему Ейлера можно объяснить на пальцах, ящитаю

Объясните на пальцах БПФ. Не что он делает, а КАК.

Ну мля, я хочу понять, как всё-таки эти формулы с интегралами в циклы расписать чтобы ему на вход массив с PCM, на выходе массив с частотами.

tx ★
( 22.06.09 08:54:55 MSD )

Re: [математикам]что такое mod?

Здесь либо порядок операций нужно смотреть, либо ограничение представления машинного числа в памяти компа. Положительное integer принимает значения от 0 до 32767. Ну, типа тогда 0-1=32767.

the_mozart
( 22.06.09 08:54:55 MSD )
Ответ на: Re: [математикам]что такое mod? от val-amart 22.06.09 05:07:04 MSD

Re: [математикам]что такое mod?

Ну что такое остаток я понимаю, но как его найти в данном примере? Ведь e^ явно меньше чем (p-1)?

p.s. эта формула из "трехподходного протокола Шамира"

Turbid ★★★★★
( 22.06.09 08:55:21 MSD ) автор топика

Re: [математикам]что такое mod?

>Как это считается?

Самое простое объяснение: в методичке опечатка, пропущена какая-то буква перед "-1".

DonkeyHot ★★★★★
( 22.06.09 09:46:58 MSD )

Re: [математикам]что такое mod?

Второе объяснение - вопрос в том, что такое e^-1 в смысле (mod n), и как его вычислить.

DonkeyHot ★★★★★
( 22.06.09 10:06:17 MSD )

Re: [математикам]что такое mod?

Это таки точно опечатка. У меня получается 34229, что слишком похоже на 32229, чтобы быть случайным.

DonkeyHot ★★★★★
( 22.06.09 10:09:53 MSD )
Ответ на: Re: [математикам]что такое mod? от DonkeyHot 22.06.09 10:09:53 MSD

Re: [математикам]что такое mod?

Т.е. получается: d = e^ (mod p-1) = 42239^ (mod(52631-1) = 34229

Еще раз, для малограмотных, объясните как взять остаток от деления 42239^ = 2.36748029073e-05 на 52630?

Turbid ★★★★★
( 22.06.09 10:22:07 MSD ) автор топика
Ответ на: Re: [математикам]что такое mod? от Turbid 22.06.09 10:22:07 MSD

Re: [математикам]что такое mod?

>как взять остаток от деления 42239^

На самом деле mod(n), означает не остаток от деления(это только метод вычисления) а выполнение операций в соотв. кольце (или какой другой структуре -- я основательно позабыл) - в котором не-целых чисел вообще нет, т.ч. e-05 там получить никак нельзя. Т.о. из определения ^-1: A^-1 (mod N) = B, такое, что A * B (mod n) = 1, следует немножко другое число. Как его вычислить и правда не знаю (:for i in range() помог:). Опыт показывает, что это 34229, т.к. *42239 mod (52630) == 1.

DonkeyHot ★★★★★
( 22.06.09 10:51:27 MSD )
Ответ на: Re: [математикам]что такое mod? от DonkeyHot 22.06.09 10:51:27 MSD

Re: [математикам]что такое mod?

Спасибо, тогда тоже пока напишу скрипт, пусть ищет.
Похожие публикации: