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

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

Z

\x017E

`

b



T

V

Z

\x20AC

‚

„