Числа сравнимые по модулю

Числа сравнимые по модулю

Определение 1. Пусть a, bZ, mN. Говорят, что число а сравнимо с b по модулю m, если а и b при делении на m дают одинаковые остатки. Запись этого факта выглядит так: ab(mod m).

Определение 2. Два целых числа a и b называются сравнимыми по модулю m, если их разность делится нацело на m. (ab) ⋮ m

Определение 3. Два целых числа a и b называются сравнимыми по модулю m, если a = b + mt, где tZ.

Очевидно, что бинарное отношение сравнимости m (неважно, по какому модулю) есть отношение эквивалентности на множестве целых чисел.

Ясно, что число а сравнимо с b по модулю m тогда и только тогда, когда аb делится на m нацело. Очевидно, это, в свою очередь, бывает тогда и только тогда, когда найдется такое целое число t , что a = b + mt.

Понять процесс собирания целых чисел в классы сравнимых между собой по модулю m (классы эквивалентности m) поможет следующая картинка:

На рисунке 6 изображен процесс наматывания цепочки целых чисел на колечко с m делениями, при этом на одно деление автоматически попадают сравнимые между собой числа. Кстати, эта картинка неплохо объясняет и термин "кольцо".

Перечислим, далее, свойства сравнений, похожие на свойства отношения равенства.

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

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

Доказательство.

Свойство 3. К любой части сравнения можно прибавить любое число, кратное модулю.

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

Свойство 5. Обе части сравнения можно возвести в одну и ту же степень.

Как следствие из вышеперечисленных свойств, получаем

Свойство 7. Обе части сравнения можно разделить на их общий делитель, взаимно простой с модулем.

Свойство 8. Обе части сравнения и его модуль можно умножить на одно и то же целое число или разделить на их общий делитель.

Свойство 9. Если сравнение ab имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.

Свойство 10. Если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m.

Доказательство очевидно следует из транзитивности отношения делимости: если ab(mod m), то a-b делится на m, значит a-b делится на d, где d|m.

Свойство 11. Если одна часть сравнения и модуль делятся на некоторое число, то и другая часть сравнения должна делиться на то же число.

Пример. Доказать, что при любом натуральном n число 37 п +2 +16 п +1 + 23 п делится на 7.

Решение. Очевидно, что 37 ≡ 2(mod 7), 16 ≡ 2(mod 7), 23 ≡ 2(mod 7)

Возведем первое сравнение в степень n+2, второе – в степень n+1, третье – в степень n и сложим:

т.е. 37 п +2 + 16 п +1 + 23 п делится на 7. Как видите, ровным счетом ничего сложного в решении подобных школьных задач "повышенной трудности" нет.

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

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

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

a=sp+r, (1)

где s — число, и r одно из чисел 0,1, . p−1.

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

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

Читайте также:  Что такое program unwanted 1183

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

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

(2)

Так как r1 принимает один из чисел 0,1, . p−1, то абсолютное значение r1r меньше p. Но из (2) следует, что r1r кратно p. Следовательно r1=r и s1=s.

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

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

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

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

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

(3)

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

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

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

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

a≡a mod (p).

Свойство 2. Если два числа a и c сравнимы с числом b по модулю p , то a и c сравнимы между собой по тому же модулю, т.е. если

a≡b mod (p), b≡c mod (p).
a≡c mod (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, то

(a−b)+ (m−n)=(a+m)−(b+n) ,
(a−b)−(m−n)=(a−m)−(b−n)

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

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

a≡b mod (p) и m≡n mod (p),
am≡bn mod (p).

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

am≡bm mod (p).

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

bm≡bn mod (p).

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

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

где 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 представить в следующем утверждении:

Утверждение 4. Пусть f(x1, x2, x3, . ) целая рациональная функция с целыми коэффициентами и пусть

a1b1, a2b2, a3b3, . mod (p).
f(a1, a2, a3, . )≡f(b1, b2, b3, . ) mod (p).

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

am≡bm mod (p)

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

a≡b mod (p).

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

am≡bm mod (p),
a≡b mod (p/λ),

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

m=m1λ и k=k1λ.

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

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

.

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

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

a≡b mod (p)

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

a≡b mod (m).

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

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

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

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

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

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

a≡b mod (h),

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

Читайте также:  Генератор ников для варкрафт

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

Эквивалентные формулировки: a и b сравнимы по модулю n , если их разность ab делится на n , или если a может быть представлено в виде a = b + kn , где k — некоторое целое число. Например: 32 и −10 сравнимы по модулю 7, так как

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

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

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

  • рефлексивности: для любого целого a справедливо
  • симметричности: если то
  • транзитивности: если и то

Любые два целых числа 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, представленному в виде его канонического разложения на простые сомножители pi

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

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

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

  • Можно делить обе части сравнения на число, взаимно простое с модулем: если и НОД, то .
  • Можно одновременно разделить обе части сравнения и модуль на их общий делитель: если , то .

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

  • Если и , то , где m = [m1,m2] .

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

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

Множество всех чисел, сравнимых с a по модулю n называется классом вычетов a по модулю n , и обычно обозначается [a]n или . Таким образом, сравнение равносильно равенству классов вычетов [a]n = [b]n .

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

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

[a]n + [b]n = [a + b]n

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

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

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

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

,

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

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

Набор несравнимых чисел, взаимно простых с n , называется приведённой системой вычетов, см. Мультипликативная группа кольца вычетов.

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

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

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

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

  • Если b не кратно d , то у сравнения нет решений.
  • Если b кратно d , то у сравнения существует единственное решение по модулю m / d , или, что то же самое, d решений по модулю m . В этом случае в результате сокращения исходного сравнения на d получается сравнение:

где a1 = a / d , b1 = b / d и m1 = m / d являются целыми числами, причем a1 и m1 взаимно просты. Поэтому число a1 можно обратить по модулю m1 , то есть найти такое число c, что (другими словами, ). Теперь решение находится умножением полученного сравнения на c:

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

Читайте также:  Если холодильник не отключается в чем причина

Пример

Для сравнения имеем d = 2 , поэтому по модулю 22 сравнение имеет два решения. Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все 3 числа на 2:

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

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

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

История

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

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

Ссылки

  • Вейль А., Основы теории чисел, М.:Мир, 1972.
  • Виленкин Н. Я., Сравнения и классы вычетов, Квант, № 10, 1978.
  • И. М. ВиноградовОсновы теории чисел. — М.-Л.: Гос. изд. технико-теоретической литературы, 1952. — 180 с.

Wikimedia Foundation . 2010 .

Смотреть что такое "Сравнение по модулю натурального числа" в других словарях:

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

Сравнение — Сравнение многозначный термин. Сравнение процесс количественного или качественного сопоставления разных свойств (сходств, отличий, преимуществ и недостатков) двух объектов. Сравнение выяснение, какой из двух объектов лучше в… … Википедия

Кармайкловы числа — В теории чисел кармайкловы числа это положительные составные числа n, которые удовлетворяют условию для всех целых b, взаимно простых с n (смотри Сравнение по модулю натурального числа). Названы в честь Роберта Кармайкла. Содержание 1 Общее … Википедия

Индекс числа по модулю — Дискретное логарифмирование (DLOG) – задача обращения функции gx в некоторой конечной мультипликативной группе G. Наиболее часто задачу дискетного логарифмирования рассматривают в группе обратимых элементов кольца вычетов, в мультипликативной… … Википедия

Класс вычетов — Сравнение по модулю натурального числа отношение эквивалентности на множестве целых чисел, связанное с делимостью. Оно даёт возможность работать с системой чисел, более простой чем целые числа, в которой значения «зацикливаются» (повторяются)… … Википедия

Классы вычетов — Сравнение по модулю натурального числа отношение эквивалентности на множестве целых чисел, связанное с делимостью. Оно даёт возможность работать с системой чисел, более простой чем целые числа, в которой значения «зацикливаются» (повторяются)… … Википедия

Кольцо вычетов — Сравнение по модулю натурального числа отношение эквивалентности на множестве целых чисел, связанное с делимостью. Оно даёт возможность работать с системой чисел, более простой чем целые числа, в которой значения «зацикливаются» (повторяются)… … Википедия

Модульная арифметика — Сравнение по модулю натурального числа отношение эквивалентности на множестве целых чисел, связанное с делимостью. Оно даёт возможность работать с системой чисел, более простой чем целые числа, в которой значения «зацикливаются» (повторяются)… … Википедия

Модулярная арифметика — Сравнение по модулю натурального числа отношение эквивалентности на множестве целых чисел, связанное с делимостью. Оно даёт возможность работать с системой чисел, более простой чем целые числа, в которой значения «зацикливаются» (повторяются)… … Википедия

Метод Берлекемпа — метод решения сравнений второй степени по произвольному простому модулю. См. также Сравнение по модулю натурального числа Квадратичный вычет … Википедия

Ссылка на основную публикацию
Хрипит динамик на телефоне при прослушивании
Одной из самых распространенных поломок мобильных аппаратов является выход из строя динамика. Любой пользователь мобильных телефонов знает, что сейчас производители...
Установить программу для сканирования документов бесплатно
Загрузите бесплатно пробную полнофункциональную версию программы для сканирования Scanitto Pro. Данная версия работает без каких-либо ограничений в течение 30 дней....
Установить протокол mtp media transfer protocol
Описание Компания Microsoft содержит под своим крылом множество драйверов, среди этой коллекции находится и Media Transfer Protocol, тот самый драйвер,...
Хэнкок из какой вселенной комиксов
Хэнкок Общая информацияЖанр Научная фантастика Драма Комедия Страна производстваСШАКиностудия Columbia Pictures РежиссёрПитер БергАвтор сценария Винс Джиллиган Винсент Нго Когда вышел2008...
Adblock detector