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

Означення. Діленням числа 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 взаємно прості, то a(n) 1 (mod n).

Доведення. Скористаємося другою теоремою про лишки лінійної форми. Нехай r1, ..., rk, k = (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 = (n), отже a(n) 1 (mod n).

Приклад. Нехай a = 7, n = 9. Тоді 7 (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)