Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Математичні основи
Означення. Нехай a та b – цілі числа. Кажуть, що a дорівнює b за модулем n, позначається через a º b (mod n), якщо a - b ділиться на n.
Приклад. 23 º 3 (mod 5), тому що 23 - 3 = 5 * 4;
-25 º 3 (mod 7), тому що -25 - 3 = 7 * -4;
Властивості. Нехай a, a1, b, b1, c – цілі числа.
1. a º b (mod n) тоді і тільки тоді коли a та b дають рівні залишки при діленні на n.
2. Рефлексивність. a º a (mod n).
3. Симетрія. Якщо a º b (mod n), то b º a (mod n).
4. Транзитивність. Якщо a º b (mod n) і b º c (mod n), то a º c (mod n).
5. Якщо a º a1 (mod n) та b º b1 (mod n),
то a + b º a1 + b1 (mod n) і a * b º a1 * b1 (mod n).
Означення. Нехай n – ціле додатне число. Позначимо через Ct клас, у який об’єднано усі цілі числа, які при діленні на n дають одну і ту ж остачу t. Усі цілі числа розіб’ються на n класів C0, C1, ..., Cn-1, які називаються класами лишків за модулем n.
Приклад. Нехай n = 7. Тоді до класу C2 належать числа виду 7 * x + 2, де x Î Z.
Твердження. Два числа є порівнюваними за модулем n, якщо вони належать одному класу лишків за модулем n.
Означення. Якщо з кожної системи лишків за модулем n взяти по одному представнику, то отриману систему чисел називають повною системою лишків за модулем n. Якщо повну систему лишків будувати з найменших невід’ємних лишків, то вона прийме вигляд: 0, 1, 2, ..., n - 1. Її будемо позначати через Zn. Арифметичні операції над елементами цієї множини відбуваються за модулем n. Повна система лишків утворює групу з операцією додавання.
Приклад. Повною системою лишків за модулем 5 буде множина чисел Z5 = {0, 1, 2, 3, 4}.
Приклад. Z12 = {0, 1, 2, ..., 11}. У класі Z12: 11 + 6 = 5, тому що 11 + 6 = 17 º 5 (mod 12). 10 * 3 = 6, тому що 10 * 3 = 30 º 6 (mod 12).
Перша теорема про лишки лінійної форми. Якщо у лінійній формі ax + b число x пробігає усі значення з повної системи лишків за модулем n при НСД(a, n) = 1 та довільному b, тоді ax + b пробігає усі значення повної системи лишків за модулем n.
Доведення. Отримана система складається з n чисел, оскільки замість x у формі ax + b підставляються n різних значень. Доведемо від супротивного, що усі ці n отриманих чисел різні. Нехай x1 та x2 не порівнювані за модулем n, але ax1 + b º ax2 + b (mod n). Тоді ax1 º ax2 (mod n). Але оскільки НСД(a, n) = 1, то x1 º x2 (mod n). Отримали суперечність.
Приклад. Нехай n = 6, a = 5, b = 1, при цьому НСД(a, n) = 1. Підставимо до форми 5 * x + 1 значення x із повної системи лишків Z6 = {0, 1, 2, ..., 5}.
|
x |
5 * x + 1 (mod 6) |
|
0 |
1 |
|
1 |
0 |
|
2 |
5 |
|
3 |
4 |
|
4 |
3 |
|
5 |
2 |
В правому стовпчику таблиці всі числа різні.
Означення. Якщо з кожної системи лишків Ct (t = 0, 1, ..., n - 1) за модулем n, для якої НСД (t, n) = 1 взяти по одному представнику, то отриману систему чисел називають зведеною системою лишків за модулем n і позначають через Zn*. Зведена система лишків утворює групу з операцією множення.
Якщо p – просте, то Zp* = {1, 2, ..., p - 1}.
Означення. Порядком множини A будемо називати кількість її елементів і позначати через |A|.
Приклад. Зведеною системою лишків для n = 10 буде множина чисел Z10* = {1, 3, 7, 9}, |Z10*| = 4.
Означення. Функція Ейлера. Позначимо через j(n) кількість чисел із інтервалу [1..n], взаємно простих з n.
Властивості функції Ейлера
1. Якщо p – просте число, то j (p) = p - 1 та j (pa) = pa * (1 - 1/p) для довільного a.
2. Якщо m та n взаємно прості, то j (m * n) = j (m) * j (n).
3. Якщо n = , то j (n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk).
4. j (n) = |Zn*|.
5. = n.
Приклад. Обчислити j(728), j(10).
728 = 7 * 8 * 13 = 23 * 7 * 13, 10 = 2 * 5.
j(728) = 728 * (1 - 1/2) * (1 - 1/7) * (1 - 1/13) = 728 * (1/2) * (6/7) * (12/13) = 288.
j(10) = 10 * (1 - 1/2) * (1 - 1/5) = 10 * (1/2) * (4/5) = 4.
Твердження. Порядком групи Zn* будемо називати кількість елементів в ній та позначати |Zn*|. При цьому
|Zn*| = j(n)
Приклад. Z10* = {1, 3, 7, 9}, |Z10*| = j(10) = 4.
Друга теорема про лишки лінійної форми. Якщо у лінійній формі a * x число x пробігає усі значення зі зведеної системи лишків за модулем n при НСД(a, n) = 1, тоді a * x пробігає усі значення зведеної системи лишків за модулем n.
Доведення. Підставивши замість змінної x у лінійну форму a * x j(n) чисел, отримаємо j(n) різних чисел, оскільки вони належать за модулем m різним класам (це випливає з першої теореми про лишки лінійної форми для b = 0). Оскільки x – лишок зведеної системи, то НСД(x, n) = 1. За умовою теореми НСД(a, n) = 1. З останніх двох рівностей випливає, що НСД(a * x, n) = 1, тобто числа a * x взаємно прості з n.
Приклад. Розглянемо множину чисел {1, 3, 7, 9}, яка є зведеною системою лишків для n = 10. Нехай a = 7, НСД (7, 10) = 1. Тоді мають місце співвідношення:
7 * 1 (mod 10) º 7 (mod 10) º 7
7 * 3 (mod 10) º 21 (mod 10) º 1
7 * 7 (mod 10) º 49 (mod 10) º 9
7 * 9 (mod 10) º 63 (mod 10) º 3
Означення. Оберненням числа a за модулем n (позначається a-1) називається таке число x Î Zn, що ax º 1 (mod n).
Приклад. Обчислити 5-1 (mod 7). Знайдемо всі значення 5 * x (mod 7), x = 0, ..., 6.
5 * 0 (mod 7) º 0 mod 7 º 0
5 * 1 (mod 7) º 5 mod 7 º 5
5 * 2 (mod 7) º 10 mod 7 º 3
5 * 3 (mod 7) º 15 mod 7 º 1
5 * 4 (mod 7) º 20 mod 7 º 6
5 * 5 (mod 7) º 25 mod 7 º 4
5 * 6 (mod 7) º 30 mod 7 º 2
Оскільки 5 * 3 (mod 7) º 1, то 5-1 (mod 7) º 3.
Твердження. Обернене число a-1 за модулем n існує тоді і тільки тоді, коли НСД(a, n) = 1.
Якщо НСД(a, n) = k > 1, то для довільного елемента x Î Zn вираз ax (mod n) буде ділитися на k і ніколи не буде дорівнювати 1 (тому що 1 не ділиться на k при k > 1).
Алгоритм обчислення оберненого числа. Якщо необхідно обчислити a-1 (mod n), то знайдемо за розширеним алгоритмом Евкліда НСД(a, n) = d та такі значення x та y, що ax + ny = d. Якщо d > 1, то оберненого значення не існує. Інакше a-1 (mod n) = x, тому що ax (mod n) º ax + ny (mod n) º d = 1.
Приклад. Обчислити 2-1 (mod 7).
НСД(2, 7) = 1, отже обернене значення існує.
За розширеним алгоритмом Евкліда матимемо:
2 * (-3) + 7 * 1 = 1, звідки 2-1 (mod 7) º –3 (mod 7) º 4.
Перевірка: 2 * 4 (mod 7) º 8 (mod 7) º 1.
Означення. Діленням числа a на число b за модулем n називається множення a на b-1 за умови існування b-1.
Приклад. Результатом 4 : 5 (mod 7) буде 4 * 5-1 (mod 7) º 4 * 3 (mod 7) º 12 (mod 7) º 5.
Перевірка: 5 * 5 (mod 7) º 25 (mod 7) º 4.
Теорема Ейлера. Якщо a та n взаємно прості, то aj(n) º 1 (mod n).
Доведення. Скористаємося другою теоремою про лишки лінійної форми. Нехай r1, ..., rk, k = j(n) – лишки зведеної системи за модулем n, взяті у формі найменших додатних лишків. Тоді найменшими додатними лишками чисел a * ri будуть r1’ , ..., rk’, які у сукупності утворюють також зведену систему. Отже
ar1 º r1’ (mod n)
ar2 º r2’ (mod n)
.........................
ark º rk’ (mod n)
Звідки ak * r1 * ... * rk º r1’ * ... * rk’ (mod n). Але оскільки добутки r1 * ... * rk та r1’ * ... * rk’ рівні і взаємно прості з модулем, то розділивши рівність на цей добуток, отримаємо: ak º 1 (mod n). За припущенням k = j(n), отже aj(n) º 1 (mod n).
Приклад. Нехай a = 7, n = 9. Тоді 7 j (9) (mod 9) º 79 * (1 - 1/3) (mod 9) º 76 (mod 9) º 493 (mod 9) º 43 (mod 9) º 64 (mod 9) º 1.
Теорема Ферма. (Частковий випадок теореми Ейлера).
Якщо p просте, a Î Zp*, то ap-1 º 1 (mod p).
Наслідок. Якщо помножити рівність ap-1 º 1 (mod p) на a, то отримаємо
ap º a (mod p)
Приклад. Нехай p = 11 – просте число.
Виберемо а = 3. Тоді повинна виконуватись рівність:
310 (mod 11) º 1
Дійсно, 310 (mod 11) º 95 (mod 11) º (-2)5 (mod 11) º -32 (mod 11) º 1.
Теорема. Китайська теорема про залишки. Нехай n1, n2, …, nk – взаємно прості числа. Тоді система порівнянь
x º a1 (mod n1)
x º a2 (mod n2)
. . . . . .. . .. . . .
x º ak (mod nk)
має єдиний розв'язок за модулем n = n1 * n2 * … * nk.
Алгоритм Гауса розв'язку системи лінійних порівнянь з китайської теореми про залишки.
Значення x обчислюється наступним чином:
x = mod n, де Ni = n / ni, Mi = mod ni.
Приклад. Розв’язати систему порівнянь:
n = 11 * 13 = 143. Обчислимо Ni та їх обернені хначення Mi:
N1 = 143 / 11 = 13, N2 = 143 / 13 = 11
M1 = 13-1 (mod 11) = 6, M2 = 11-1 (mod 13) = 6
x = 5 * 13 * 6 + 8 * 11 * 6 ( mod 143) º 390 + 528 (mod 143) º 60
Відповідь: x = 60 (mod 143).
Приклад. Обчислити значення виразу 46 * 67 mod 561, якщо відомо розклад модуля на прості множники: 561 = 3 * 11 * 17.
Обчислимо лишки множників за модулями 3, 11 та 17.
{46 mod 3, 46 mod 11, 46 mod 17} = {1, 2, 12},
{67 mod 3, 67 mod 11, 67 mod 17} = {1, 1, 16}.
46 * 67 = {1, 2, 12} * {1, 1, 16} = {1 * 1 mod 3, 2 * 1 mod 11, 12 * 16 mod 17} = {1, 2, 5}
Тепер для обчислення значення 46 * 67 mod 561 слід розв’язати систему лінійних порівнянь