Реферат Математичні основи Означення. Нехай Х та Ц цілі числа. Кажуть, що Х дорівнює Ц за модулем n, позначається через Х Ц (moШ n), якщо


СкачатиСкачать (DOC|ZIP):
Математичні основи Означення. Нехай Х та Ц цілі числа. Кажу

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

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

Означення. Нехай 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).

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.


СкачатиСкачати: Математичні основи Означення. Нехай Х та Ц цілі числа. Кажу


Схожі реферати:
  • Зарубіжна й українська культура в другій половині 60-80-х років (реферат)
  • Порядок визначення суми податкових зобов язань і представлення податкових декларацій. Підстави і порядок застосування адм
  • Економічна теорія. Закон грошового обігу і проблеми інфляції (курсова)
  • РЕФЕРАТ на тему: Демографічний потенціал світу 1. Загальне поняття про демографічний потенціал Під демографічним потенці
  • Реферат Формування сексуальної культури молоді: феномен людської сексуальності.
  • РЕФЕРАТ на тему: Оцінка коливань та сталості динаміки. Поясність сутність індексу сезонності Для характеристики розвитку явищ у часі використовую
  • Теоретичні основи аналізу попиту та пропозиції(пошукова робота)
  • Методрозробка практичного заняття з латинської мови І. Тема практичного заняття. а) Граматична тема. Родові винятки. Відмінювання іменників в ІІІ відміни у відмінках вживаних у медич
  • Міжнародні фінансові організації. Кредити підприємству (реферат)
  • Кучма Л.Д. - президент України (реферат)




  • Скористайтеся пошуком:
    Loading

    Пошук :

    0.031471