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

25

34

43

52

В правому стовпчику таблиці всі числа різні.

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

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

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

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

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

3. Якщо n = , то (n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk).

4. (n) = |Zn*|.

5. = n.

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

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

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

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

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

|Zn*| = (n)

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

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