Учебник. Сравнения по модулю и признаки делимости
Два натуральных числа 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 = x1 + 10x2, где x1 – число единиц, x2 – число десятков этого числа. Пусть y = x2 + 2x1 (то есть y – число десятков, сложенное с удвоенным числом единиц). Тогда 10y – x = 19x1 ≡ 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 MSDRe: [математикам]что такое 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 MSDRe: [математикам]что такое 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 MSDRe: [математикам]что такое 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 MSDRe: [математикам]что такое 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 MSDRe: [математикам]что такое mod?
Спасибо, тогда тоже пока напишу скрипт, пусть ищет.
Оператор 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? Пишите в комментариях!
Что такое mod в математике
Оператор div и оператор mod
В этой статье речь пойдет о целочисленном делении и делении с остатком.
Итак, что такое целочисленное деление вообще? В математике целочисленным делением называют такое деление, при котором одно целое число делится на другое целое число ,а результатом является целая часть их частного.
То есть например 20 / 5 = 4, 55 / 6 = 9, 100 / 3 = 33 и т.д.
Согласитесь, что в некоторых случаях это очень удобно и практично. Теперь поговорим о реализации этого метода в Паскале. Тут все достаточно просто, открывать Америку не придется. В паскале за целочисленное деление отвечает оператор div. Теперь как это записывается в Pascal’e
x — число , которое будем делить на y (делимое)
y — число , на которое будем делить число x (делитель)
z — результат целочисленного деления (целочисленное частное)Таким образом, вот такая запись (55 / 6) нацело = 9 в результате использования оператора div будет выглядеть так
z будет равно 9. Запомните! При использовании оператора div дробная часть будет отброшена!
А сейчас поговорим о делении с остатком. Оно не особо отличается и главным здесь является то, что в результате отбрасывается как раз целая часть. То есть (40 / 6) с остатком = 4, (10 / 3) с остатком =1, (22 /5) с остатком = 2 и т.д. В паскале для этого есть оператор mod. Записывается он точно так же.
x — число , которое будем делить на y (делимое)
y — число , на которое будем делить число x (делитель)
z — остатокНапример (40 / 6) с остатком = 4 с оператором mod будет такой
И как результат получим z=1 .
Кстати оператор mod часто используют, для определения кратности чисел (кратность — это делимость на какое-нибудь число нацело. То есть например говорят, что числа 3, 6, 9, 12, 21 кратны трем. Или числа 5,10,15,20 кратны 5). В статье нахождение четных элементов массива я упоминал о числах кратных двум (четных). Итак как эту кратность определить в паскале. Обратите внимание, что если число кратное, то у него есть остаток (точнее оно имеет в остатке ноль). Этим и стоит воспользоваться.
Сейчас я привел пример условия, которое проверяет кратность, где v — это число, проверяемое на кратность по числу m. Например чтобы проверить,
является ли 40 кратным 4, используем оператор mod с условием и получим