Порівняння по модулю натурального числа - це
визначення
Два цілих числа a і b можна порівняти по модулю натурального числа n (або равноостаточни при розподілі на n), якщо при розподілі на n вони дають однакові залишки.
Еквівалентні формулювання: a і b можна порівняти по модулю n. якщо їх різниця a - b ділиться на 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. то їх ступеня ak і bk теж можна порівняти по модулю 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.
рішення порівнянь
Порівняння першого ступеня
У теорії чисел. криптографії та інших областях науки часто виникає задача відшукання рішень порівняння першого ступеня виду:
Рішення такого порівняння починається з обчислення НСД (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 с.
Дивитися що таке "Порівняння по модулю натурального числа" в інших словниках:
Порівняння по модулю - Порівняння [1] по модулю натурального числа n в теорії чисел відношення еквівалентності на кільці цілих чисел, пов'язане з делимостью на n. Факторкольцо з цього відношенню називається кільцем відрахувань. Сукупність відповідних тотожностей і ... ... Вікіпедія
Індекс числа по модулю - Дискретне логарифмирование (DLOG) - задача звернення функції gx в деякій кінцевої мультиплікативної групі G. Найбільш часто завдання діскетной логарифмирования розглядають в групі оборотних елементів кільця відрахувань, в мультипликативной ... ... Вікіпедія
Порівняння - Порівняння багатозначний термін. Порівняння процес кількісного або якісного зіставлення різних властивостей (подібностей, відмінностей, переваг і недоліків) двох об'єктів. Порівняння з'ясування, який з двох об'єктів краще в ... ... Вікіпедія
Клас відрахувань - Порівняння по модулю натурального числа відношення еквівалентності на множині цілих чисел, пов'язане з делимостью. Воно дає можливість працювати з системою чисел, більш простий ніж цілі числа, в якій значення «зациклюються» (повторюються) ... ... Вікіпедія
Класи відрахувань - Порівняння по модулю натурального числа відношення еквівалентності на множині цілих чисел, пов'язане з делимостью. Воно дає можливість працювати з системою чисел, більш простий ніж цілі числа, в якій значення «зациклюються» (повторюються) ... ... Вікіпедія
Кільце відрахувань - Порівняння по модулю натурального числа відношення еквівалентності на множині цілих чисел, пов'язане з делимостью. Воно дає можливість працювати з системою чисел, більш простий ніж цілі числа, в якій значення «зациклюються» (повторюються) ... ... Вікіпедія
Модульна арифметика - Порівняння по модулю натурального числа відношення еквівалентності на множині цілих чисел, пов'язане з делимостью. Воно дає можливість працювати з системою чисел, більш простий ніж цілі числа, в якій значення «зациклюються» (повторюються) ... ... Вікіпедія
Модулярная арифметика - Порівняння по модулю натурального числа відношення еквівалентності на множині цілих чисел, пов'язане з делимостью. Воно дає можливість працювати з системою чисел, більш простий ніж цілі числа, в якій значення «зациклюються» (повторюються) ... ... Вікіпедія
Метод Берлекемпа - метод вирішення порівнянь другого ступеня за довільним простому модулю. Див. Також Порівняння по модулю натурального числа Квадратичний відрахування ... Вікіпедія
- Порівняння по модулю. Джессі Рассел. Ця книга буде виготовлена в відповідності з Вашим замовленням за технологією Print-on-Demand. High Quality Content by WIKIPEDIA articles! Порівняння по модулю натурального числа n - в теорії ... Детальніше Купити за тисячі сто двадцять п'ять руб