м узагальненням ділення позитивних чисел. Тут ми також називаємо число r у формулі (1.2.6) залишком при розподілі числа а на число m або залишком по модулю m.
Приклади.
) а=11, m=7, 11=7 1 + 4,
) а=- 11, m=7, - 11=7 (- 2) + 3.
Розподіл (1.2.6) може бути також записано як порівняння
а r (mod m). (1.2.8)
Таким чином, кожне число порівнянно зі своїм залишком по модулю m. У наведених вище прикладах ми маємо
4 (mod 7), - 113 (mod 7).
Жодних два залишку в (1.2.7) не порівняні по (mod m), так як різниця між будь-якими двома з них менше, ніж m. Тому два числа, які не порівняні по (mod m), повинні мати різні залишки. Отже, ми робимо висновок: порівняння а b (mod m) виконується тоді і тільки тоді, коли числа а і b мають однакові залишки при діленні на число m.
Існує інший спосіб представлення цього порівняння. Припустимо на мить, що а і b - цілі позитивні числа. Коли число а записано при підставі m, а=(аn ..., а1, а0) m,
то остання цифра а0 є залишком числа а при діленні його на число m. Якщо ми використовуємо цей факт, щоб інакше висловити нашу інтерпретацію порівняння, то можна сказати:
порівняння а b (mod m) виконується для цілих (позитивних) чисел а і b тоді і тільки тоді, коли числа а і b мають однакові останні цифри в записі при підставі m.
Наприклад,
87 (mod 10),
так як ці два числа мають одну і ту ж останню цифру в десятковій системі чисел.
1.3 Алгебра порівнянь
З алгебри ми пам'ятаємо, що рівняння можна складати, віднімати, множити. Точно такі ж правила справедливі для порівнянь. Припустимо, що ми маємо порівняння
a b (mod m), з d (mod m). (1.3.1)
За визначенням, це означає, що
=b + mk, c=d + ml, (1.3.2)
де k і l - цілі числа. Складемо рівняння (1.3.2).
В результаті отримуємо
а + с=b + d + m (k + l),
що можемо записати як
теорія число порівняння арифметика
а + с b + d (mod m); (1.3.3)
іншими словами, два порівняння можна складати. Таким же чином можна показати, що одне порівняння можна віднімати з іншого, тобто. Е. Що
- c b - d (mod m). (1.3.4)
Приклад.
- 5 (mod 8) і 7 - 9 (mod 8). (1.3.5)
Складаючи їх, отримуємо
- 14 (mod 8),
а віднімаючи,
4 (mod 8).
Обидва ці порівняння справедливі.
Можна також перемножити два порівняння. З (1.3.1) і (1.3.2) випливає, що ac=bd + m (kd + bl + mkl),
таким чином,
ас bd (mod m). (1.3.6)
Приклад. Коли два порівняння з (1.3.5) перемножити, виходить
=45 (mod 8).
Порівняння ab (mod m) може бути помножена на будь-яке ціле число с, при цьому отримуємо
ас bc (mod m). (1.3.7)
Це можна розглядати як окремий випадок множення порівнянь (1.3.6) при с=d. Його можна також розглядати як прямий наслідок з визначення порівняння.
Приклад. Коли перше порівняння з (1.3.5) множиться на 3, одержуємо, що 33=- 15 (mod 8).
Виникає природне запитання: у якому випадку можна в порівнянні (1.3.7) скоротити загальний множник з і отримати при цьому вірне сравненіеb (mod m)?
Саме тут порівняння відрізняються від рівнянь. Наприклад, вірно, що 22 - 2 (mod 8),
але скорочення на множник 2 дало б порівняння
- 1 (mod 8),
яке невірно.
В одному важливому випадку скорочення допустимо:
якщо ас bc (mod m), то ab (mod m) за умови, що числа m і з взаємно прості.
Доказ. Перше порівняння означає, що
ас - bc=(а - b) с=mk.
Якщо D (m, с)=1, то звідси випливає, що а - b ділиться на m.
Приклад. У порівнянні
48 (mod 11)
ми можемо скоротити на множник 4, так як D (11, 4)=1. Це дає
212 (mod 11).
3
2. АРИФМЕТИЧНІ ДОДАТКИ ТЕОРІЇ порівнянні
. 1 Арифметичні дії
До арифметичним дій відносяться:
Додавання є початковим поняттям, для якого неможливо дати строге формальне визначення. Тим не менш, щоб надати цій дії деякий розумне уявлення, ми скажемо, що додавання - це операція знаходження суми двох або декількох чисел, де під сумою розуміється загальна кількість одиниць, що містяться в розглянутих числах разом. Ці числа називаються доданками. Наприклад, 11 + 6=17. Тут 11 і 6 - доданки, 17 - сума. Якщо доданки поміняти місцями, то сума не зміниться: 11 + 6=17 і 6 + 11=17.
Віднімання є дією, зворотним до додавання, так як...
