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

Означення. Якщо з кожної системи лишків 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.

Означення. Функція Ейлера. Позначимо через \xF06A(n) кількість чисел із інтервалу [1..n], взаємно простих з n.

Властивості функції Ейлера

1. Якщо p – просте число, то \xF06A (p) = p - 1 та \xF06A\xF020(pa) = pa * (1 - 1/p) для довільного a.

2. Якщо m та n взаємно прості, то \xF06A\xF020(m * n) = \xF06A\xF020(m) * \xF06A\xF020(n).

, то \xF06A\xF020(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk).

4. \xF06A (n) = |Zn*|.

= n.

Приклад. Обчислити \xF06A(728), \xF06A(10).

728 = 7 * 8 * 13 = 23 * 7 * 13, 10 = 2 * 5.

\xF06A(728) = 728 * (1 - 1/2) * (1 - 1/7) * (1 - 1/13) = 728 * (1/2) * (6/7) * (12/13) = 288.

\xF06A(10) = 10 * (1 - 1/2) * (1 - 1/5) = 10 * (1/2) * (4/5) = 4.

Твердження. Порядком групи Zn* будемо називати кількість елементів в ній та позначати |Zn*|. При цьому

|Zn*| = \xF06A(n)

Приклад. Z10* = {1, 3, 7, 9}, |Z10*| = \xF06A(10) = 4.

Друга теорема про лишки лінійної форми. Якщо у лінійній формі a * x число x пробігає усі значення зі зведеної системи лишків за модулем n при НСД(a, n) = 1, тоді a * x пробігає усі значення зведеної системи лишків за модулем n.

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

7 * 3 (mod 10) \xF0BA 21 (mod 10) \xF0BA 1

7 * 7 (mod 10) \xF0BA 49 (mod 10) \xF0BA 9

7 * 9 (mod 10) \xF0BA 63 (mod 10) \xF0BA 3

Означення. Оберненням числа a за модулем n (позначається a-1) називається таке число x \xF0CE\xF020Zn, що ax \xF0BA 1 (mod n).

Приклад. Обчислити 5-1 (mod 7). Знайдемо всі значення 5 * x (mod 7), x = 0, ..., 6.

5 * 0 (mod 7) \xF0BA 0 mod 7 \xF0BA 0

5 * 1 (mod 7) \xF0BA 5 mod 7 \xF0BA 5

5 * 2 (mod 7) \xF0BA 10 mod 7 \xF0BA 3