Математичні основи, Детальна інформація

5 * 5 (mod 7) \xF0BA 25 mod 7 \xF0BA 4

5 * 6 (mod 7) \xF0BA 30 mod 7 \xF0BA 2

Оскільки 5 * 3 (mod 7) \xF0BA 1, то 5-1 (mod 7) \xF0BA 3.

Твердження. Обернене число a-1 за модулем n існує тоді і тільки тоді, коли НСД(a, n) = 1.

Якщо НСД(a, n) = k > 1, то для довільного елемента x \xF0CE 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) \xF0BA ax + ny (mod n) \xF0BA d = 1.

Приклад. Обчислити 2-1 (mod 7).

НСД(2, 7) = 1, отже обернене значення існує.

За розширеним алгоритмом Евкліда матимемо:

2 * (-3) + 7 * 1 = 1, звідки 2-1 (mod 7) \xF0BA –3 (mod 7) \xF0BA 4.

Перевірка: 2 * 4 (mod 7) \xF0BA 8 (mod 7) \xF0BA 1.

Означення. Діленням числа a на число b за модулем n називається множення a на b-1 за умови існування b-1.

Приклад. Результатом 4 : 5 (mod 7) буде 4 * 5-1 (mod 7) \xF0BA 4 * 3 (mod 7) \xF0BA 12 (mod 7) \xF0BA 5.

Перевірка: 5 * 5 (mod 7) \xF0BA 25 (mod 7) \xF0BA 4.

Теорема Ейлера. Якщо a та n взаємно прості, то a\xF06A(n) \xF0BA 1 (mod n).

Доведення. Скористаємося другою теоремою про лишки лінійної форми. Нехай r1, ..., rk, k = \xF06A(n) – лишки зведеної системи за модулем n, взяті у формі найменших додатних лишків. Тоді найменшими додатними лишками чисел a * ri будуть r1’ , ..., rk’, які у сукупності утворюють також зведену систему. Отже

ar1 \xF0BA r1’ (mod n)

ar2 \xF0BA r2’ (mod n)

.........................

ark \xF0BA rk’ (mod n)

Звідки ak * r1 * ... * rk \xF0BA r1’ * ... * rk’ (mod n). Але оскільки добутки r1 * ... * rk та r1’ * ... * rk’ рівні і взаємно прості з модулем, то розділивши рівність на цей добуток, отримаємо: ak \xF0BA 1 (mod n). За припущенням k = \xF06A(n), отже a\xF06A(n) \xF0BA 1 (mod n).

Приклад. Нехай a = 7, n = 9. Тоді 7 \xF06A\xF020(9) (mod 9) \xF0BA 79 * (1 - 1/3) (mod 9) \xF0BA 76 (mod 9) \xF0BA 493 (mod 9) \xF0BA 43 (mod 9) \xF0BA 64 (mod 9) \xF0BA 1.

Теорема Ферма. (Частковий випадок теореми Ейлера).

Якщо p просте, a \xF0CE Zp*, то ap-1 \xF0BA 1 (mod p).

Наслідок. Якщо помножити рівність ap-1 \xF0BA 1 (mod p) на a, то отримаємо

ap \xF0BA a (mod p)

Приклад. Нехай p = 11 – просте число.

Виберемо а = 3. Тоді повинна виконуватись рівність:

310 (mod 11) \xF0BA 1

Дійсно, 310 (mod 11) \xF0BA 95 (mod 11) \xF0BA (-2)5 (mod 11) \xF0BA -32 (mod 11) \xF0BA 1.