Порівняння по модулю

Перший доказ цієї теореми належить Лейбніца. причому він відкрив зазначену теорему незалежно від Ферма не пізніше 1683 року і повідомив про це з приведенням точного докази Бернуллі. Крім цього Лейбніцем був запропонований прообраз формулювання теореми Вільсона.

Пізніше вивчення питань, присвячених теорії чисел і теорії порівнянь, було продовжено Ейлером. який ввів квадратичний закон взаємності і узагальнив теорему Ферма. встановивши, що

Поняття і символьне позначення порівнянь було введено Гауссом. як важливий інструмент для обґрунтування його арифметичної теорії, робота над якою була розпочата їм в 1797 році. На початку цього періоду Гауса ще не були відомі праці його попередників, тому результати його роботи, викладені в перших трьох розділах його книги «Арифметичні дослідження» (1801 рік), були в основному вже відомі, проте методи, які він використовував для доказів, виявилися абсолютно новими, мають вищу важливість для розвитку теорії чисел. Використовуючи ці методи Гаусс перетворив все накопичені до нього відомості, пов'язані з операціями порівняння по модулю, в струнку теорію, яка вперше була викладена в цій же книзі. Крім цього, він досліджував порівняння першого та другого ступеня, теорію квадратичних лишків і пов'язаний з нею квадратичний закон взаємності [5].

Якщо два цілих числа a і b при діленні на m дають однакові залишки, то вони називаються порівнянними (або равноостаточнимі) по модулю числа m [6].

Порівнянність чисел a і b записується у вигляді формули (порівняння):

Число m називається модулем порівняння.

Визначення порівнянності чисел a і b по модулю m рівносильно будь-якого з наступних тверджень:

Тоді в припущенні, що

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

Порівняння по одному і тому ж модулю мають багато властивостей звичайних рівності. Наприклад, їх можна додавати, віднімати і множити: якщо числа a 1. a 2. .... a n, a _, \ ldots, a_> і b 1. b 2. .... b n, b _, \ ldots, b_> попарно можна порівняти по модулю m. то їх суми a 1 + a 2 + ... + a n + a _ + \ ldots + a_> і b 1 + b 2 + ... + b n + b _ + \ ldots + b_>. а також твори a 1 ⋅ a 2 ⋅. ⋅ a n \ cdot a_ \ cdot. \ Cdot a_> і b 1 ⋅ b 2 ⋅. ⋅ b n \ cdot b_ \ cdot. \ Cdot b_> теж можна порівняти по модулю m:

(A 1 + a 2 + ... + a n) ≡ (b 1 + b 2 + ... + b n) (mod m); + A _ + \ ldots + a _) \ equiv (b_ + b _ + \ ldots + b _)>;> (a 1 ⋅ a 2 ⋅ ... ⋅ an) ≡ (b 1 ⋅ b 2 ⋅ ... ⋅ bn) (mod m) . \ Cdot a_ \ cdot \ ldots \ cdot a _) \ equiv (b_ \ cdot b_ \ cdot \ ldots \ cdot b _)>.>

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

До обох частин порівняння можна додати одне і те ж число c:

Також можна перенести число з однієї частини порівняння в іншу зі зміною знака:

K кожній із частин порівняння можна додати ціле число, кратне модуля, тобто, якщо числа a і b можна порівняти по модулю деякого числа m. то і a + t 1> порівняно з b + t 2> по модулю m. де t 1> і t 2> - довільні цілі числа, кратні m:

Також обидві частини порівняння і модуль можна помножити на одне і те ж число, тобто, якщо числа a і b можна порівняти по модулю деякого цілого числа m. то і числа a q і b q можна порівняти по модулю числа m q. де q - ціле:

Порівняння, однак, не можна, взагалі кажучи, ділити один на одного або на інші числа. Приклад: 14 ≡ 20 (mod 6) >>. однак, скоротивши на 2, ми отримуємо помилкове порівняння: 7 ≡ 10 (mod 6) >>. Правила скорочення для порівнянь наступні.

Якщо, число d не взаємних просто з модулем, як було в прикладі, зазначеному вище, то скорочувати на d можна.

• Можна одночасно розділити обидві частини порівняння і модуль на їх спільний дільник: