Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Порівняння за модулем



План:


Введення

Порівняння [1] за модулем натурального числа n - в теорії чисел відношення еквівалентності на кільці цілих чисел, пов'язане з подільністю на n. Факторкольцо по цьому відношенню називається кільцем відрахувань. Сукупність відповідних тотожностей і алгоритмів утворює модульну [2] (або модулярні) арифметику.


1. Визначення

Два цілих числа a і b можна порівняти по модулю натурального числа n (або равноостаточни при діленні на n), якщо при діленні на n вони дають однакові залишки. Число n називається модулем порівняння.

Еквівалентні формулювання: a і b можна порівняти за модулем n, якщо їх різниця a - b ділиться на n без залишку, або якщо a може бути представлено у вигляді a = b + k n , Де k - Деяке ціле число. Наприклад: 32 і -10 порівнянні за модулем 7, так як

32 = 7 \ cdot 4 + 4

і

-10 = 7 \ cdot (-2) + 4.

Твердження "a і b можна порівняти за модулем n" записується у вигляді:

a \ equiv b \ pmod n.

2. Властивості

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

В силу того, що ставлення порівнянності по модулю володіє цими трьома властивостями, воно є ставленням еквівалентності на безлічі цілих чисел.

Будь-які два цілих числа порівнянні за модулю 1.

Якщо числа a і b можна порівняти за модулем n, і n ділиться на m, то a і b можна порівняти за модулем m.

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

n = \ prod_ {i = 1} ^ n p_i ^ {\ alpha_i},

необхідно і достатньо, щоб

a \ equiv b \ pmod {p_i ^ {\ alpha_i}}, \ quad i = 1, 2, \ dots, n.

Якщо a \ equiv b \ pmod {m_1} і a \ equiv b \ pmod {m_2} , То a \ equiv b \ pmod m , Де m = [m 1, m 2] .


3. Операції з порівняннями

Порівняння з одного й того ж модулю володіють багатьма властивостями звичайних рівностей. Наприклад, їх можна складати, вичитати і множити: якщо числа a_1, \, a_2, \, \ dots, \, a_n і b_1, \, b_2, \, \ dots, \, b_n попарно можна порівняти по модулю n, то їх суми a_1 + a_2 + \ dots + a_n і b_1 + b_2 + \ dots + b_n , А також твори a_1 \, a_2 \, \ dots \, a_n і b_1 \, b_2 \, \ dots \, b_n теж можна порівняти по модулю n. Якщо числа a і b порівняти по модулю n, то їх ступеня a k і b k теж можна порівняти по модулю n при будь-якому натуральному k.

Порівняння, однак, не можна, взагалі кажучи, ділити один на одного або на інші числа. Приклад: 14 \ equiv 20 \ pmod 6 , Однак, скоротивши на 2, ми отримуємо помилкове порівняння: 7 \ equiv 10 \ pmod 6 . Правила скорочення для порівнянь наступні.

  • Можна ділити обидві частини порівняння на число, взаємно просте з модулем: якщо ac \ equiv bc \ pmod n і gcd (c, n) = 1 , То a \ equiv b \ pmod n .
  • Можна одночасно розділити обидві частини порівняння і модуль на їх загальний дільник: якщо ac \ equiv bc \ pmod {nc} , То a \ equiv b \ pmod n .

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


4. Пов'язані визначення

4.1. Класи вирахувань

Безліч всіх чисел порівнянних з a за модулем n називається класом відрахувань a за модулем n, і звичайно позначається [A] n або \ Bar a_n . Таким чином, порівняння a \ equiv b \ pmod {n} рівносильно рівності класів відрахувань [A] n = [b] n .

Оскільки порівняння за модулем n є ставленням еквівалентності на безлічі цілих чисел \ Mathbb {Z} , То класи відрахувань по модулю n є класи еквівалентності; їх кількість дорівнює n. Безліч всіх класів відрахувань по модулю n позначається \ Mathbb {Z} _n або \ Mathbb {Z} / n \ mathbb {Z} .

Операції додавання і множення на \ Mathbb {Z} індукують відповідні операції на множині \ Mathbb {Z} _n :

[A] n + [b] n = [a + b] n
[A] _n \ cdot [b] _n = [a \ cdot b] _n

Щодо цих операцій безліч \ Mathbb {Z} _n є кінцевим кільцем, а для простого n - кінцевим полем.


4.2. Системи вирахувань

Система вирахувань дозволяє здійснювати арифметичні операції над кінцевим набором чисел, не виходячи за його межі. Повна система відрахувань по модулю n - будь-який набір з n попарно непорівнянних за модулем n цілих чисел. Звичайно як повної системи відрахувань по модулю n беруться найменші невід'ємні відрахування

0,1 ,..., n - 1

або абсолютно найменші відрахування, що складаються з чисел

0, \ pm1, \ pm2 ,..., \ pm \ tfrac {n-1} 2 ,

у разі непарного n , І чисел

0, \ pm1, \ pm2 ,..., \ pm (\ tfrac {n} 2-1), \ tfrac {n} 2

у разі парного n .

Максимальний набір попарно непорівнянних за модулем n чисел, взаємно простих з n, називається наведеної системою вирахувань по модулю n. Будь-яка наведена система відрахувань по модулю n містить φ (n) елементів, де \ Varphi (\ cdot) - функція Ейлера.


5. Рішення порівнянь

5.1. Порівняння першого ступеня

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

ax \ equiv b \ pmod {m}.

Рішення такого порівняння починається з обчислення НОД (a, m) = d. При цьому можливі 2 випадки:

  • Якщо b не кратно d , То у порівняння немає рішень.
  • Якщо b кратно d , То у порівняння існує єдине рішення по модулю m / d , Або, що те ж саме, d рішень по модулю m . У цьому випадку в результаті скорочення вихідного порівняння на d виходить порівняння:
a_1 x \ equiv b_1 \ pmod {m_1}

де a 1 = a / d , b 1 = b / d і m 1 = m / d є цілими числами, причому a 1 і m 1 взаємно прості. Тому число a 1 можна звернути по модулю m 1 , Тобто знайти таке число c, що c \ cdot a_1 \ equiv 1 \ pmod {m_1} (Іншими словами, c \ equiv a_1 ^ {-1} \ pmod {m_1} ). Тепер рішення знаходиться множенням отриманого порівняння на c:

x \ equiv c a_1 x \ equiv c b_1 \ equiv a_1 ^ {-1} b_1 \ pmod {m_1}.

Практичне обчислення значення c можна здійснити різними способами: за допомогою теореми Ейлера, алгоритму Евкліда, теорії ланцюгових дробів (див. алгоритм) та ін Зокрема, теорема Ейлера дозволяє записати значення c у вигляді:

c \ equiv a_1 ^ {-1} \ equiv a_1 ^ {\ varphi (m_1) -1} \ pmod {m_1}.

5.1.1. Приклад

Для порівняння 4x \ equiv 26 \ pmod {22} маємо d = 2 , Тому по модулю 22 порівняння має два рішення. Замінимо 26 на 4, порівнянне з ним по модулю 22, і потім скоротимо всі 3 числа на 2:

2x \ equiv 2 \ pmod {11}

Оскільки 2 взаємно просто з модулем 11, то його можна звернути по модулю 11 і знайти 2 ^ {-1} \ equiv 6 \ pmod {11} . Примножуючи порівняння на 6, отримуємо рішення по модулю 11: x \ equiv 1 \ pmod {11} , Еквівалентну сукупності двох рішень по модулю 22: x \ equiv 1 \ pmod {22} і x \ equiv 12 \ pmod {22} .


5.2. Порівняння другого ступеня

Рішення порівнянь другого ступеня зводиться до з'ясування, чи є дане число квадратичним вирахуванням (за допомогою квадратичного закону взаємності) і подальшого обчислення квадратного кореня з даного модулю.

5.3. Системи порівнянь

Найпростіша система порівнянь щодо попарно взаємно простих модулів m_1, m_2, \ ldots, m_n

\ Left \ {\ begin {array} {rcl} x & \ equiv & a_1 \ pmod {m_1} \ \ x & \ equiv & a_2 \ pmod {m_2} \ \ & \ ldots & \ \ x & \ equiv & a_n \ pmod {m_n} \ end {array} \ right.

завжди можна залагодити, і її рішення єдино по модулю m_1 \ cdot m_2 \ cdot \ ldots \ cdot m_n (Див. китайська теорема про залишки).


6. Історія

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

Значною мірою теорія подільності і вирахувань була створена Ейлером. Порівняння за модулем вперше використовувалися Гауссом в його книзі "Арифметичні дослідження", 1801. Він же запропонував утвердилася в математиці символіку для порівнянь.


Джерела

  1. Девенпорт Г. Вища арифметика. Введення в теорію чисел. - М.: Наука, 1965. - 176 с.
  2. Вельшенбах М. Криптографія на Сі і C + + в дії - М.: Тріумф, 2004. - 461 с.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Порівняння
Порівняння браузерів
Порівняння (програмування)
Порівняння IDE
Порівняння (риторика)
Ознака порівняння
Ступені порівняння
Порівняння месенджерів
© Усі права захищені
написати до нас