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

План:

1 Визначення
2 Властивості
3 Операції з порівняннями
4 Пов'язані визначення
- 4.1 Класи вирахувань
- 4.2 Системи вирахувань
5 Рішення порівнянь
6 Історія

Введення

Порівняння ^[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 має такі властивості:

рефлексивності : для будь-якого цілого a справедливо $a \ equiv a \ pmod n.$
симетричності : якщо $a \ equiv b \ pmod n,$ то $b \ equiv a \ pmod n.$
транзитивності : якщо $a \ equiv b \ pmod n$ і $b \ equiv c \ pmod n,$ то $a \ equiv c \ pmod 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 ₁ = a / d , b ₁ = b / d і m ₁ = m / d є цілими числами, причому a ₁ і m ₁ взаємно прості. Тому число a ₁ можна звернути по модулю m ₁ , Тобто знайти таке число 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. Він же запропонував утвердилася в математиці символіку для порівнянь.

Джерела

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