Математичні основи

Доведення. Підставивши замість змінної x у лінійну форму a * x (n) чисел, отримаємо (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.