Математичні основи (реферат)

Реферат на тему:

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

Означення. Нехай a та b – цілі числа. Кажуть, що a дорівнює b за
модулем n, позначається через a ? b (mod n), якщо a — b ділиться на n.

Приклад. 23 ? 3 (mod 5), тому що 23 — 3 = 5 * 4;

-25 ? 3 (mod 7), тому що -25 — 3 = 7 * -4;

Властивості. Нехай a, a1, b, b1, c – цілі числа.

1. a ? b (mod n) тоді і тільки тоді коли a та b дають рівні залишки при
діленні на n.

2. Рефлексивність. a ? a (mod n).

3. Симетрія. Якщо a ? b (mod n), то b ? a (mod n).

4. Транзитивність. Якщо a ? b (mod n) і b ? c (mod n), то a ? c (mod n).

5. Якщо a ? a1 (mod n) та b ? b1 (mod n),

то a + b ? a1 + b1 (mod n) і a * b ? a1 * b1 (mod n).

Означення. Нехай n – ціле додатне число. Позначимо через Ct клас, у який
об’єднано усі цілі числа, які при діленні на n дають одну і ту ж остачу
t. Усі цілі числа розіб’ються на n класів C0, C1, …, Cn-1, які
називаються класами лишків за модулем n.

Приклад. Нехай n = 7. Тоді до класу C2 належать числа виду 7 * x + 2,
де x ? Z.

Твердження. Два числа є порівнюваними за модулем n, якщо вони належать
одному класу лишків за модулем n.

Означення. Якщо з кожної системи лишків за модулем n взяти по одному
представнику, то отриману систему чисел називають повною системою лишків
за модулем n. Якщо повну систему лишків будувати з найменших невід’ємних
лишків, то вона прийме вигляд: 0, 1, 2, …, n — 1. Її будемо позначати
через Zn. Арифметичні операції над елементами цієї множини відбуваються
за модулем n. Повна система лишків утворює групу з операцією додавання.

Приклад. Повною системою лишків за модулем 5 буде множина чисел Z5 = {0,
1, 2, 3, 4}.

Приклад. Z12 = {0, 1, 2, …, 11}. У класі Z12: 11 + 6 = 5, тому що 11 +
6 = 17 ? 5 (mod 12). 10 * 3 = 6, тому що 10 * 3 = 30 ? 6 (mod 12).

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

Доведення. Отримана система складається з n чисел, оскільки замість x у
формі ax + b підставляються n різних значень. Доведемо від супротивного,
що усі ці n отриманих чисел різні. Нехай x1 та x2 не порівнювані за
модулем n, але ax1 + b ? ax2 + b (mod n). Тоді ax1 ? ax2 (mod n). Але
оскільки НСД(a, n) = 1, то x1 ? x2 (mod n). Отримали суперечність.

Приклад. Нехай n = 6, a = 5, b = 1, при цьому НСД(a, n) = 1. Підставимо
до форми 5 * x + 1 значення x із повної системи лишків Z6 = {0, 1, 2,
…, 5}.

x 5 * x + 1 (mod 6)

0 1

1 0

2 5

3 4

4 3

5 2

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

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

, то ??(n) = n * (1 — 1/p1) * (1 — 1/p2) * … * (1 — 1/pk).

4. ? (n) = |Zn*|.

= 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.

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

7 * 3 (mod 10) ? 21 (mod 10) ? 1

7 * 7 (mod 10) ? 49 (mod 10) ? 9

7 * 9 (mod 10) ? 63 (mod 10) ? 3

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

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

5 * 0 (mod 7) ? 0 mod 7 ? 0

5 * 1 (mod 7) ? 5 mod 7 ? 5

5 * 2 (mod 7) ? 10 mod 7 ? 3

5 * 3 (mod 7) ? 15 mod 7 ? 1

5 * 4 (mod 7) ? 20 mod 7 ? 6

5 * 5 (mod 7) ? 25 mod 7 ? 4

5 * 6 (mod 7) ? 30 mod 7 ? 2

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

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

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

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

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

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

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

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

Означення. Діленням числа 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)

має єдиний розв’язок за модулем n = n1 * n2 * … * nk.

Алгоритм Гауса розв’язку системи лінійних порівнянь з китайської теореми
про залишки.

Значення x обчислюється наступним чином:

mod ni.

Приклад. Розв’язати систему порівнянь:

n = 11 * 13 = 143. Обчислимо Ni та їх обернені хначення Mi:

N1 = 143 / 11 = 13, N2 = 143 / 13 = 11

M1 = 13-1 (mod 11) = 6, M2 = 11-1 (mod 13) = 6

Таким чином

x = 5 * 13 * 6 + 8 * 11 * 6 ( mod 143) ? 390 + 528 (mod 143) ? 60

Відповідь: x = 60 (mod 143).

Приклад. Обчислити значення виразу 46 * 67 mod 561, якщо відомо розклад
модуля на прості множники: 561 = 3 * 11 * 17.

Обчислимо лишки множників за модулями 3, 11 та 17.

{46 mod 3, 46 mod 11, 46 mod 17} = {1, 2, 12},

{67 mod 3, 67 mod 11, 67 mod 17} = {1, 1, 16}.

46 * 67 = {1, 2, 12} * {1, 1, 16} = {1 * 1 mod 3, 2 * 1 mod 11, 12 * 16
mod 17} = {1, 2, 5}

Тепер для обчислення значення 46 * 67 mod 561 слід розв’язати систему
лінійних порівнянь

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *