Клас відрахувань - це
визначення
Кажуть, що два цілих числа a і bсравніми по модулю натурального числа n. якщо при розподілі на n вони дають однакові залишки.
Еквівалентні формулювання: a і bсравніми по модулюn. якщо їх різниця a - b ділиться на n. або якщо a може бути представлено у вигляді a = b + kn. де k - деяке ціле число.
- Приклад: 32 і -10 порівнянні по модулю 7, так як 32 = 7 ∙ 4 + 4, -10 = 7 ∙ (-2) + 4.
Затвердження «a і b можна порівняти по модулю n» записується у вигляді:
Ставлення порівняння є відношенням еквівалентності і володіє багатьма властивостями звичайних рівності. Наприклад, їх можна складати і множити: якщо
Порівняння, однак, не можна, взагалі кажучи, ділити один на одного або на інші числа. Приклад:, однак, скоротивши на 2, ми отримуємо помилкове порівняння:. Правила скорочення для порівнянь наступні.
- Можна ділити обидві частини порівняння на число, взаємно просте з модулем: якщо і НСД, то.
- Можна одночасно розділити обидві частини порівняння і модуль на їх спільний дільник: якщо, то.
Не можна також виконувати операції з порівняннями, якщо їх модулі не збігаються.
- Якщо і, то, де m = [m1, m2].
- Якщо, то a, b можна порівняти з будь-якого модулю - делителю m.
класи відрахувань
Безліч всіх чисел, які можна порівняти з a за модулем n називається класом відрахувань a за модулем n. і зазвичай позначається [a] n чи. Таким чином, порівняння рівносильне рівності класів відрахувань [a] n = [b] n.
Оскільки порівняння по модулю n є відношенням еквівалентності на множині цілих чисел, то класи лишків за модулем n є класи еквівалентності; їх кількість дорівнює n. Безліч всіх класів лишків за модулем n позначається або.
Операції додавання і множення на індукують відповідні операції на дуже багато!
[A] n + [b] n = [a + b] 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.
Дивитися що таке "Клас відрахувань" в інших словниках:
розряд, клас оподаткування - Точка на шкалі оподатковуваного доходу, до якої відноситься оподатковуваного доходу (taxable income). Також наз. граничним розрядом оподаткування (marginal tax bracket). Виражається у вигляді відсотка, який повинен бути застосований до кожного ... ... Фінансово-інвестиційний тлумачний словник
ЧИСЕЛ Теорія - розділ чистої математики, що займається вивченням цілих чисел 0, ± 1, ± 2. і співвідношень між ними. Іноді теорію чисел називають вищої арифметикою. Окремі обчислення, вироблені над конкретними числами, наприклад, 9 + 16 = 25, ні ... ... Енциклопедія Кольєра
Факторкольцо - Факторкольцо в абстрактній алгебрі це кільце класів відрахувань деякого кільця по модулю його ідеалу. Позначається. Класи лишків за модулем ідеалу визначаються як суміжні класи кільця по адитивної підгрупі ... Вікіпедія
ІНДЕКС - числа а по модулю т показник ув порівнянні a = gg (mod m), де АІ твзаімно прості, а g деякий фіксований первісний корінь по модулю т. І. числа апо модулю тобозначается через g = indg а чи, коротше, у = ind а. Первісні корені ... ... Математична енциклопедія
Нільпотентний елемент - нільпотент, елемент акольца або напівгрупи з нулем А, що задовольняє рівності для нек якого натурального п. Мінімальне значення п, для до якого справедливо це рівність, наз. індексом нильпотентною елемента а. Напр. в кільці відрахувань по модулю ... Математична енциклопедія
Нільпотентний елемент - чи нільпотент - елемент кільця, що задовольняє рівності для деякого натурального. Мінімальне значення. для якого справедливо це рівність, називається індексом нильпотентною елемента. Розгляд нільпотентов часто виявляється ... ... Вікіпедія