Математичні основи - реферат українською
Означення. Нехай 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.
Друга теорема про лишки лінійної форми. Якщо у лінійній формі 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
Приклад. 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.
Друга теорема про лишки лінійної форми. Якщо у лінійній формі 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
Скачати реферат Математичні основи
Схожі українські реферати
|
1. Реферат: Математика в сільському господарстві План реферату 1. Вступ Значення математики в житті людей й сільському господарстві. 2. Математика у сільському господарстві. a) Рішення виробничих практичних задач, використовуючи тему “Відсотки”. b) Рішення виробничих задач на тему “П... 2. Реферат: Математика як навчальний предмет Математика вивчає просторові форми і кількіснівідношення, наприклад, який-небудь педмет. Нас може цікавити, яка його густина, міцність, теплопровідність. Ф. Енгельс так4 описав змуст математики: “Чиста математика має своїм обєктом просторові форми і ... 3. Реферат: Математики України Математика - галузь невтомного пошуку і важкої до самозабуття праці. Іноді на доведення однієї теореми потрібні роки. Праця вченого-математика подібна до праці поета: як і в поезії, у математиці діють досить складні механізми пошуку і філігранне офор... 4. Реферат: Математики ХVІ – поч. ХХ ст. Реферат на тему: Математики ХVІ – поч. ХХ ст. Епоха Відродження характеризується бурхливим розвитком живопису, музики, скульптури, архітектури й поезії, що почали звільнятися від догм католицької церкви. У XVI-XVII ст. на основі феодального... 5. Реферат: Математики, в яких рано виявився талант: Ф.Гаусс, Б.Паскаль, Е.Галуа, Л.Шнірельман Паскаль (Pascal) Блез (19.6.1623, Клермон-Ферран, — 19.8.1662, Париж), французький релігійний філософ, письменник, математик і фізик. Народився в родині високоосвіченого юриста, що займався математикою і виховували своїх дітей під впливом педагогічн... 6. Реферат: Математична обробка результатів вимірювань Прямими називаються вимірювання, в результаті яких встановлюють безпосередньо шукане значення величини. Результати спостережень Xl, Х2,.... Хп, одержані за прямими вимірюваннями фізичної величини Q, називаються рівнорозсіяними, якщо вони є незалежни... 7. Реферат: Математичне забезпечення САПР Тема : Математичне забезпечення САПР. Загальні поняття та вимоги до МЗ. Способи отримання математичних моделей. Постановка задач оптимізації. Класифікація і характеристика методів оптимізації. 1. МЗ включає в себе мат. методи, мат. моделі та а... 8. Реферат: Математичне моделювання в політології в контексті гуманітарної освіти Одна з найважливіших проблем будь-якої науки — проблема методу, розв’язання якої дозволяє отримати нове знання і застосувати його в практичній діяльності. Разом з тим, це є однією з найскладніших проблем, яка передує вивченню певного об’єкту і, крім... 9. Реферат: Математичне моделювання та диференціальні рівняння 1.1. Поняття математичного моделювання. Поняття математичного моделювання трактується різними авторами по своєму. Ми будемо його пов’язувати з нашою спеціалізацією – прикладна математика. Під математичним моделюванням ми будемо розуміти мето... 10. Реферат: Математичні моделі й методи обгрунтування управлінських рішень, сфери їх використання в управлінській діяльності Вступ. Кожен день нам доводиться вирішувати безліч питань: чи варто придбати ту чи іншу річ, як розподілити сімейний бюджет, що з’їсти на обід або чи варто вдягати теплий одяг? І кожен з нас незалежно від віку і статі намагається знайти якомога ра...
11. Реферат: Математичні основи
Означення. Нехай 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; ... 12. Реферат: Математичні послідовності План 1. Числова послідовність. 2. Означення границі числової послідовності. 3. Основні теореми про границі. 4. Обчислення деяких границь. 5. Монотонні послідовності. 6. Число е. 7. Верхня та нижня границя. 8. Функціональна послідовність крите... 13. Реферат: Математичні розваги. Мета: Виховувати у дітей зацікавленість до математичних завдань, зацікавити їх дотепними іграми, логічними задачами з елементами гумору, викликати радість пізнання. В зал заходять діти – цифри від 1 до 9, а за ними – решта дітей групи. Кожна цифра... 14. Реферат: Материки світу Назви частин світу і материків мають різне походження. Древні греки називали всі землі на захід від Босфору Європою, а на схід від нього - Азією. Римляни розділяли свої східні (азіатські) провінції на Азію і Малу Азію (Анатолію). Назва "Африка", я... 15. Реферат: Материнка звичайна, мачок жовтий, медунка лікарська Материнка звичайна, мачок жовтий, медунка лікарська МАТЕРИНКА ЗВИЧАЙНА (блошниця, зiновка, духовий цвіт, душинка, душиця, крушельниця, лебiдка, ліновка, маринка, материнка пахуча, матердушка) Origanum vulgare Багаторiчна трав'яниста ро... 16. Реферат: Матеріал на замовлення, особливість сучасної журналістики Матеріал на замовлення, особливість сучасної журналістики Коли я запитала Ріхарда Керлера, виконавчого директора видавництва IPM MAGAZIN GmbH, чи є в його країні таке поняття, як стаття "на замовлення", він не зрозумів мене. Це відчувалося з його ... 17. Реферат: Матеріали для захисту сільськогосподарської техніки під час її зберігання Специфічною особливістю сільськогосподарського виробництва є те, що переважну частину машин і знарядь використовують сезонно. Значно інтенсивніше експлуатують трактори, але й вони протягом року часто простоюють як під час польових робіт, так і взим... 18. Реферат: МАТЕРІАЛІСТИЧНА КАРТИНА СВІТУ ОЧИМА АСТРОНОМІЇ Метагалактика і космологія. Галактики, подібно до зір, бувають подвійними, кратними, утворюють групи і скупчення. Більшість галактик зосереджено в скупченнях. Скупчення галактик, як і скупчення зір, бувають розсіяними і кульовими, містять десятки, ін... 19. Реферат: Матеріалістична картина світу очима астрономії Метагалактика і космологія. Галактики, подібно до зір, бувають подвійними, кратними, утворюють групи і скупчення. Більшість галактик зосереджено в скупченнях. Скупчення галактик, як і скупчення зір, бувають розсіяними і кульовими, містять десятки, ін... 20. Реферат: Матеріалістична картина світу очима астрономії Метагалактика і космологія. Галактики, подібно до зір, бувають подвійними, кратними, утворюють групи і скупчення. Більшість галактик зосереджено в скупченнях. Скупчення галактик, як і скупчення зір, бувають розсіяними і кульовими, містять десятки, ін... 21. Реферат: Матеріальна відповідальність Поняття ознаки, функції, задачі і правове значення інституту матеріальної відповідальності Працівник, який завдав матеріальної шкоди підприємству, організації, установі, несе матеріальну відповідальність незалежно від того, чи був він притягнутий д... |
|