что значит сравнимо по модулю

Сравнение чисел по модулю

Определение 1. Если два числа 1 ) a и b при делении на p дают один и тот же остаток r, то такие числа называются равноостаточными или сравнимыми по модулю p.

Утверждение 1. Пусть p какое нибудь положительное число. Тогда всякое число a всегда и притом единственным способом может быть представлено в виде

1 ) В данной статье под словом число будем понимать целое число.

Действительно. Если s получит значение от −∞ до +∞, то числа sp представляют собой совокупность всех чисел, кратных p. Рассмотрим числа между sp и (s+1)p=sp+p. Так как p целое положительное число, то между sp и sp+p находятся числа

Но эти числа можно получить задав r равным 0, 1, 2. p−1. Следовательно sp+r=a получит всевозможные целые значения.

Покажем, что это представление единственно. Предположим, что p можно представить двумя способами a=sp+r и a=s₁p+r₁. Тогда

(2)

Число r называется вычетом числа a по модулю p (другими словами, число r называется остатком от деления числа a на p).

Утверждение 2. Если два числа a и b сравнимы по модулю p, то a−b делится на p.

Действительно. Если два числа a и b сравнимы по модулю p, то они при делении на p имеют один и тот же остаток p. Тогда

где s и s₁ некоторые целые числа.

Разность этих чисел

(3)

делится на p, т.к. правая часть уравнения (3) делится на p.

Утверждение 3. Если разность двух чисел делится на p, то эти числа сравнимы по модулю p.

Доказательство. Обозначим через r и r₁ остатки от деления a и b на p. Тогда

По утверждению a−b делится на p. Следовательно r−r₁ тоже делится на p. Но т.к. r и r₁ числа 0,1. p−1, то абсолютное значение |r−r₁| Свойство 1. Для любого a и p всегда

Действительно. Из условия свойства 2 следует a−b и b−c делятся на p. Тогда их сумма a−b+(b−c)=a−c также делится на p.

a≡b mod (p) и m≡n mod (p),

a+m≡b+n mod (p) и a−m≡b−n mod (p).

Действительно. Так как a−b и m−n делятся на p, то

также делятся на p.

Это свойство можно распространить на какое угодно число сравнений, имеющих один и тот же модуль.

a≡b mod (p) и m≡n mod (p),

Действительно.Так как a−b делится на p, то (a−b)m также делится на p, следовательно

Далее m−n делится на p, следовательно b(m−n)=bm−bn также делится на p, значит

Таким образом два числа am и bn сравнимы по модулю с одним и тем же числом bm, следовательно они сравнимы между собой (свойство 2).

где k некоторое неотрицательное целое число.

Действительно. Имеем a≡b mod (p). Из свойства 4 следует

a·a≡b·b mod (p).

a·a·a≡b·b·b mod (p).

a k ≡b k mod (p).

Все свойства 1-5 представить в следующем утверждении:

При делении все обстоит иначе. Из сравнения

не всегда следует сравнение

Утверждение 5. Пусть

Доказательство. Пусть λ наибольший общий делитель чисел m и p. Тогда

Так как m(a−b) делится на k, то

имеет нулевой остаток. Тогда

имеет нулевой остаток, т.е. m₁(a−b) делится на k₁. Но числа m₁ и k₁ числа взаимно простые. Следовательно a−b делится на k₁=k/λ и, тогда, a≡b mod (p/λ).

Утверждение 6. Если

и m является один из делителей числа p, то

Действительно. a−b делится на p. p делится на m. Следовательно a−b делится на m.

Утверждение 7. Если

a≡b mod (p), a≡b mod (q), a≡b mod (s)

где h наименьшее общее кратное чисел p,q,s.

Действительно. Разность a≡b должна быть числом, кратным p,q,s. и, следовательно должна быть кратным h.

В частном случае, если модули p,q,s взаимно простые числа, то

Заметим, что можно допустить сравнения по отрицательным модулям, т.е. сравнение a≡b mod (p) означает и в этом случае, что разность a−b делится на p. Все свойства сравнений остаются в силе и для отрицательных модулей.

Источник

Что значит сравнимо по модулю

ВНИМАНИЕ! В связи с новой волной пандемии и шумом вокруг вакцинации агрессивные антивакцинаторы банятся без предупреждения, а их особенно мракобесные комментарии — скрываются.

Основные условия публикации

— Посты должны иметь отношение к науке, актуальным открытиям или жизни научного сообщества и содержать ссылки на авторитетный источник.

— Посты должны по возможности избегать кликбейта и броских фраз, вводящих в заблуждение.

— Научные статьи должны сопровождаться описанием исследования, доступным на популярном уровне. Слишком профессиональный материал может быть отклонён.

— Видеоматериалы должны иметь описание.

— Названия должны отражать суть исследования.

— Если пост содержит материал, оригинал которого написан или снят на иностранном языке, русская версия должна содержать все основные положения.

Не принимаются к публикации

— Точные или урезанные копии журнальных и газетных статей. Посты о последних достижениях науки должны содержать ваш разъясняющий комментарий или представлять обзоры нескольких статей.

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

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

— Оскорбления, выраженные лично пользователю или категории пользователей.

— Попытки использовать сообщество для рекламы.

— Многократные попытки публикации материалов, не удовлетворяющих правилам.

— Нарушение правил сайта в целом.

Окончательное решение по соответствию поста или комментария правилам принимается модерацией сообщества. Просьбы о разбане и жалобы на модерацию принимает администратор сообщества. Жалобы на администратора принимает @SupportComunity и общество пикабу.

Источник

Сравнение по модулю натурального числа

В теории чисел сравнение [уточнить] по модулю натурального числа n — задаваемое означенным числом отношение эквивалентности на множестве целых чисел, связанное с делимостью на него. Факторпространство по этому отношению называется «кольцом вычетов». Совокупность соответствующих тождеств и алгоритмов образует модульную [уточнить] (или модулярную) арифметику.

Содержание

Определения

Два целых числа a и b сравнимы по модулю натурального числа n (или равноостаточны при делении на n ), если при делении на n они дают одинаковые остатки.

Утверждение « a и b сравнимы по модулю n » записывается в виде:

Свойства равенства по модулю

Отношение сравнения по модулю обладает свойствами

Любые два целых числа a и b сравнимы по модулю 1.

Для того, чтобы числа a и b были сравнимы по модулю n, необходимо и достаточно, чтобы их разность делилась на n.

Если числа и попарно сравнимы по модулю n, то их суммы и , а также произведения и тоже сравнимы по модулю n.

Если числа a и b сравнимы по модулю n, то их степени a k и b k тоже сравнимы по модулю n при любом натуральном k.

Если числа a и b сравнимы по модулю n, и n делится на m, то a и b сравнимы по модулю m.

Для того, чтобы числа a и b были сравнимы по модулю n, представленному в виде его канонического разложения на простые сомножители p_i

необходимо и достаточно, чтобы

Отношение сравнения является отношением эквивалентности и обладает многими свойствами обычных равенств. Например, их можно складывать и перемножать: если

Сравнения, однако, нельзя, вообще говоря, делить друг на друга или на другие числа. Пример: , однако, сократив на 2, мы получаем ошибочное сравнение: . Правила сокращения для сравнений следующие.

Нельзя также выполнять операции со сравнениями, если их модули не совпадают.

Связанные определения

Классы вычетов

Поскольку сравнение по модулю n является отношением эквивалентности на множестве целых чисел , то классы вычетов по модулю n представляют собой классы эквивалентности; их количество равно n. Множество всех классов вычетов по модулю n обозначается или .

Операции сложения и умножения на индуцируют соответствующие операции на множестве :

[a]_n + [b]_n = [a + b]_n

Относительно этих операций множество является конечным кольцом, а если n простое — конечным полем.

Системы вычетов

Система вычетов позволяет осуществлять арифметические операции над конечным набором чисел, не выходя за его пределы. Полная система вычетов по модулю n ― любой набор из n несравнимых между собой по модулю n целых чисел. Обычно в качестве полной системы вычетов по модулю n берутся наименьшие неотрицательные вычеты

или абсолютно наименьшие вычеты, состоящие из чисел

в случае нечётного n и чисел

Решение сравнений

Сравнения первой степени

В теории чисел, криптографии и других областях науки часто возникает задача отыскания решений сравнения первой степени вида:

Решение такого сравнения начинается с вычисления НОД(a, m)=d. При этом возможны 2 случая:

Практическое вычисление значения c можно осуществить разными способами: с помощью теоремы Эйлера, алгоритма Евклида, теории цепных дробей (см. алгоритм) и др. В частности, теорема Эйлера позволяет записать значение c в виде:

Пример

Поскольку 2 взаимно просто с модулем 11, можно сократить левую и правую части на 2. В итоге получаем одно решение по модулю 11: , эквивалентное двум решениям по модулю 22: .

Сравнения второй степени

Решение сравнений второй степени сводится к выяснению, является ли данное число квадратичным вычетом (с помощью квадратичного закона взаимности) и последующему вычислению квадратного корня по данному модулю.

История

Китайская теорема об остатках, известная уже много столетий, утверждает (на современном математическом языке), что кольцо вычетов по модулю произведения нескольких взаимно простых чисел является прямым произведением соответственных множителям колец вычетов.

В значительной степени теория делимости и вычетов была создана Эйлером. Сравнения по модулю впервые использовались Гауссом в его книге «Арифметические исследования», 1801 год. Он же предложил утвердившуюся в математике символику для сравнений.

Источник

Статья по алгебре на тему «Сравнение по модулю. Арифметрика остатков»»

Ищем педагогов в команду «Инфоурок»

Сравнение по модулю. Арифметика остатков

ОБОУ ЦДО «Новые технологии»

Боги открыли людям не все. В поиск пустившись,

люди сами открыли немало.

Число а делится на в, если при делении а на в получается целое число с.

Поделить с остатком целое число а на натуральное число в, это значит найти такие целые числа k и r, для которых выполняется равенство a=kb+r, при этом r не отрицательно и меньше b. k— неполное частное, r— остаток.

Например, нужно найти остаток от деления 100 на 7.

100 = 14х7+2, где 14 — неполное частное, 2 — остаток.

Для любого целого числа а и любого натурального числа в существует единственная пара чисел k и r, при которых выполняется равенство a=kb+r, при этом r не отрицательно и меньше b.

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

Докажем следующее утверждение: а сравнимо с в по модулю m тогда и только тогда, когда разность этих чисел а-в делится на m.

Первая часть доказательства.

Если мы знаем, что у чисел одинаковые остатки, то

a-b=km+r-lm-r=(k-l)m. Доказали — а-в это сколько-то раз по m.

Вторая часть доказательства.

Пусть мы знаем, что а-в делится на m. Предположим, что у а и в разные остатки.

Наше утверждение доказано.

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

1. Если а сравнимо с в по модулю m и с сравнимо с d по модулю m, то сумма а+с сравнима с суммой в+d по модулю m.

(а+с)- (в+d)= (а-в)+(с-d). Раз (а-в) делится на m и (с-d) делится на m, то и их сумма делится на т, а значит разность а+с и в+d делится на т и они имеют одинаковые остатки.

2. Если а сравнимо с в по модулю m и с сравнимо с d по модулю m, то разность а-с сравнима с разностью в-d по модулю m.

(а-с)- (в-d)= (а-в)-(с-d). Раз (а-в) делится на m и (с-d) делится на m, то и их разность делится на т, а значит а-с и в-d имеют одинаковые остатки.

3. Если а сравнимо с в по модулю m и с сравнимо с d по модулю m, то произведение а*с сравнимо с произведением в*d по модулю m.

ас-bd=(прибавим и вычтем вс)=ас-bс+bc-bd=c(a-b)+b(c-d).Это выражение делится на т, значит и произведение делится на т.

4. Если у чисел одинаковые остатки, то и у их равных степеней тоже одинаковые остатки. Доказательство следует из свойства 3.

Сравнение по модулю. Арифметика остатков. Борис Трушин https://www.youtube.com/watch?v=lHgMi8b27A4&t=4s

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

Источник

Алгебра и начала математического анализа. 10 класс

Конспект урока

Алгебра и начала математического анализа, 10 класс

Перечень вопросов, рассматриваемых в теме

Определение. Если а и b — два целых числа и их разность а — b делится на натуральное число m, то говорят, что a и b сравнимы по модулю m.

Теорема обратимости: обратный элемент для числа существует тогда и только тогда, когда это число взаимно простое с модулем.

Теорема 1. Если , то сравнение (7) имеет единственное решение.

Колягин Ю.М., Ткачева М.В, Федорова Н.Е. и др., под ред. Жижченко А.Б. Алгебра и начала математического анализа (базовый и профильный уровни) 10 кл. – М.: Просвещение, 2014.

Шабунин М.И., Ткачева М.В., Федорова Н.Е. Дидактические материалы Алгебра и начала математического анализа (базовый и профильный уровни) 10 кл. – М.: Просвещение, 2017.

Теоретический материал для самостоятельного изучения

Два целых числа, разность которых кратна данному натуральному числу m, называются сравнимыми по модулю m. (Слово «модуль» происходит от латинского modulus, что по-русски означает «мера», «величина».) Утверждение «a сравнимо с b по модулю m» обычно записывают в виде a ≡ b (mod m), и называют сравнением. Вот примеры сравнений: 5 ≡ 1 (mod 2), 48 ≡ 0 (mod 6), 16 ≡ 9 (mod 5). Сравнение по модулю 1 выполняется для любых двух целых чисел, так как всякое число кратно 1. Два числа сравнимы по модулю 2, если они одной четности, т.е. либо оба четны, либо оба нечетны.

Определение сравнения было сформулировано в книге К. Ф. Гаусса «Арифметические исследования». Эту работу, написанную на латинском языке, начали печатать в 1797 г., но книга вышла в свет лишь в 1801 г. из-за того, что процесс книгопечатания в то время был чрезвычайно трудоемким и длительным. Первый раздел книги Гаусса так и называется: «О сравнении чисел вообще».

Сравнениями очень удобно пользоваться в тех случаях, когда достаточно знать в каких-либо исследованиях числа с точностью до кратных некоторого числа. Например, если нас интересует, на какую цифру оканчивается куб целого числа a, то нам достаточно знать a лишь с точностью до кратных числа 10, и можно пользоваться сравнениями по модулю 10.

Мы выражаем это записью

которая читается так: а сравнимо с b по модулю m.

Делитель m мы предполагаем натуральным; он называется модулем сравнения. Наше высказывание (1) означает, что

1) 23 ≡ 8 (mod 5), так как 23 — 8 = 15 = 5 ∙ 3;

2) 47 ≡ 11 (mod 9), так как 47–11 = 36 = 9 ∙ 4;

3) —11 ≡ 5 (mod 8), так как — 11 — 5 = —16 = 8 ∙ (-2);

4) 81 ≡ 0 (mod 27), так как 81 — 0 = 81 = 27 ∙ 3.

Последний пример показывает, что вообще, вместо того, чтобы говорить: число а делится на число m, мы можем записать a ≡ 0 (mod m), так как это означает, что а — 0 = а = mk, где k — некоторое целое число.

Например, вместо того, чтобы сказать, что а — четное число, мы можем записать a ≡ 0 (mod 2).

Таким же образом видно, что нечетное число является числом, удовлетворяющим сравнению а ≡ 1 (mod 2).

Обобщим свойства сравнений:

Нахождение обратного элемента

Элемент b называется обратным к a по модулю n, если a∙b≡1(mod n). Тогда пишут, что b ≡ a –1 (mod n). Справедлива

То есть, обратный элемент для числа существует тогда и только тогда, когда это число взаимно простое с модулем.

Найти обратный элемент можно с помощью расширенного алгоритма Евклида:

Пусть a > n; a, Расширенный алгоритм Евклида находит числа x, y: ax+ny = НОД(a, n).

Вычисляет цепочка равенств:

Используя эту цепочку, восстанавливаем:

Получаем сравнение ax+ny≡1(mod n). Поскольку ny≡0(mod n), то ax≡1(mod n), а значит полученное с помощью расширенного алгоритма Евклида число x как раз и есть искомый обратный элемент к числу a по модулю n.

Вычислить элемент, обратный а по mod n, если a=9; n=29;

Воспользуемся расширенным алгоритмом Евклида:

Ответ: обратный элемент = 13.