![]()
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||
Арифметика2.1 Алгоритм Евкліда. Для будь-якого цілого а і натурального b однозначно визначені цілі числа g і г такі, що а = bq+r i 0 < г < b. Число q називається часткою, а r — остачею вiд ділення а на b. Наприклад, рівність -20 = (-1) • 67 + 47 означає, що -20 при діленні на 67 дає частку -1 і остачу 47. Для остачі будемо вживати таке позначення: r = a mod b. Число r будемо також називати (зведеним) лишком числа a за модулем b. Якщо г = 0, то кажуть, що а ділиться на b (націло або без остачі) і пишуть b | а. Кажуть також, що b ділить а, і називають b дільником числа а, а а — кратним числа b. Запис b Aлгоритм Евкліда (3 ст. до н.е.) для знаходження НСД двох натуральних чисел a і b грунтується на співвідношеннях: 1) НСД(а,b) = НСД(b,а mod b) для a 2) НСД(а, 0) = а Спершу продемонструємо ідею цього алгоритму на прикладі. Приклад 2.1. Щоб знайти НСД (211,79), застосовуємо послідовно (1) аж доки не опинимось у ситуації, коли можна використати (2). Таким чином робота алгоритму зводиться до кількаразового ділення з остачею. 211 = 79 79 = 53 53 = 26 26 = 1 Маємо НСД (211,79) = НСД (79,53) = НСД (53, 26) = НСД (26,1) = НСД (1,0) = 1. Опишемо тепер, що відбувається в загальному випадку. Алгоритм Eвкліда обчислення НСД (а, b), а · Покласти г0 = а, г1 = b, і = 1. · Виконати i-ий крок, що полягає у діленні з остачею: rі-1 = rі · Якщо rі+1 > 0, то збільшити і на 1 і перейти до виконання наступнoго кроку згідно з попереднім пунктом. Якщо rі+1 = 0, то завершити роботу із результатом НСД (а, b) = гi. Коректність. Алгоритм завершує роботу як тільки rі+1 = 0. Рано и пізно це трапиться, оскільки 0 < rі+1< гi, для кожного і. Припустимо так сталося на m-ому кроці, тобто rm+1 = 0. Результатом роботи алгоритму є значення rm. Рівність rm = НСД (а, b) випливає з таких міркувань. Співвідношення НСД (а, b) = НСД (rі-1, rі) для 1 Ефективність. Під ефективністю алгоритму Евкліда розуміємо те що кількість кроків m, які виконуються на вході а, b, не є надто великою. Із співвідношення 0 < rі+1< гi,- випливає, що m На щастя, оцінку на m можна суттєво поліпшити. Покажемо, що m Алгоритм Евкліда дає такий наслідок. Твердження 2.2. Для кожної пари взаємно простих чисел а і ь можна знайти такі цілі u і v, що иа + vь = 1. Доведення. За умовою НСД (а, b) = 1. Тому на передостанньому кроці алгоритму Евкліда матимемо rm-2 = rm-1 qm-1+1. Звідси 1 = 1
індукції за і від m-1 до 1, доведемо, що 1 = иi+1ri+viri, для деяких цілих иi та vi,. Справді, якщо 1 = иi+1ri+vi+1ri+1, то після підстановки замість ri+1 його значення, визначеного з (3), маємо При і = 1 отримуємо потрібне твердження. Зазначимо, що алгоритм Евкліда дає ефективний спосіб знаходження коефіцієнтів u і v; для заданої пари а, b. Приклад 2.3. Нехай а = 211, b = 79. Протокол роботи алгоритму Евкліда виписаний у прикладі 2.1. Рухаючись знизу вверх, отримуємомо 1 = 1 Отже, u = 3 і v = - 8. Продемонстрований спосіб визначення коефіцієнтів u і v є наочним, але не оптимальним, бо вимагає збереження в пам'яті проміжних обчислень алгоритму Евкліда. Кращий спосіб, так званий розширений алгоритм Евкліда, пропонується у вправі 2.7. 2.2. Розклад на прості співмножники.Очевидно, що кожне натуральне число а має принаймні два дільники, а саме 1 і а. Ці дільники називаються тривіальними. Якщо число а не має ніяких інших дільників, то воно називається простим, в іншому ж разі — складеним. Твердження 2.4. Якщо просте число р ділить добуток ab двох натуральних чисел, то воно мусить ділити хоча б одне із чисел а і b. Доведення. Якщо а не ділиться на р, то а і р взаємно прості. Тоді за твердженням 2.2 для деяких цілих чисел u і v виконується рівністі иа + vp = 1. Домноживши її на b, отримаємо Зрозуміло, що кожне складене число можна записати як добуток простих. Такий добуток називається розкладом числа на прості співмножники. Вважаємо, що розклад простого числа складається з єдиного елемента — самого числа. Має місце Теорема про однозначність розкладу на прості співмножники! Кожне більше від 1 ціле число однозначно розкладається на прості співмножники (якщо не враховувати їхнього порядку). Доведення. Припустимо, що Розклад, в якому прості співмножники йдуть у неспадному порядку, називається канонічним.
ЛЕКЦІЯ 6 2.3. Конгруенції. В пункті 2.1 ми домовились позначати остачу від и ділення цілого а на натуральне b через a mod b. Позначення mod ми будемо вживати і в іншому значенні. А саме, ми будемо писати х = у (mod п), якщо цілі х і у при діленні на натуральне п, дають однакову остачу. Такі х і у називатимемо конгруентними або рівними за модулем п. Відношення між х і у називається конгруенцією або порівнянням. Твердження 2.5. Наступні три умови еквівалентні. 1. х = у (mod п). 2. х = у + kn для деякого цілого k. 3. п|(х-у). Твердження 2.6. Конгруенції мають такі властивості. 1) Це відношення еквівалентності: 1. х = х (mod п) (рефлексивність); 2. якщо х = у (mod п), то у = х (mod n) (симетричність); 3. якщо х = у (modn) і у = z(modn), то х = z(modn) (транзитивність). 2) Конгруенції можна почленно додавати: якщо х1 = y1 (modn) i х2 = y2(modn), то 3) Конгруенції можна почленно перемножувати: якщо х1 = y1 (modn) і х2 = y2(modn),, то х1 4) Обидві частини конгруенції можна скорочувати на їхній спільний дільник, якщо він взаємно простий з модулем: якщо d |x, d| у і НСД (d, п) = 1, то з х = у (mod n) випливає x/d = y/d(modm). 5) Обидві частини конгруенції і модуль можна скорочувати на їхній спільний дільник: якщо d | х, d | у i d | п, то з х = у (modn) випливає x/d = y/d (mod n/d). 6) Якщо m | n, то з х = у (mod n) випливав х = у (mod m). 7) Для р і q простих, х = у (mod pq) тоді і лише тоді, коли одночасно x = y(modp) i x=y(modq). Приклад 2.7.Уникаючи обчислювальної роботи, покажемо, що 73524 ділиться на 11. Очевидно, 10 = -1 (mod 11). Множачи цю конгруенцію саму на себе, отримаємо: 100 = 1 (mod 11), 1000 = - 1 (mod 11), 10000 = 1 (mod 11). Після домноження на числа 2, 5, 3, 7 відповідно, матимемо: 20 = -2 (mod 11), 500 = 5 (mod 11), 3000 = -3 (mod 11), 70000 = 7 (mod 11). Почленне сумування дасть 73520 =.7 (mod 11). Додавши до обох частин 4, отримаємо 73524 =11 = 0 (mod 11). 2.4. Кільце лишків. Для натурального п через Zn позначаємо множину {0,1,..., п - 1}, наділену операціями додавання та множення за модулем п. Сумою х і у із Zn Твердження 2.8. Z* складається з елементів х, взаємно простих з n, і лише з них. Доведення. Якщо НСД(x, n) = 1, то за твердженням 2.2 маємо ux+ vn = 1 для деяких цілих u і v. Звідси ux = 1 (mod n) і х' = u mod n в оберненим за множенням до х в Zn. Навпаки, якщо хх' = 1 в Zn, то добуток х та х' як цілих чисел дає , 1 при діленні на п: З доведення твердження бачимо, що розширений алгоритм Евкліда дає ефективний спосіб знаходження оберненого елемента для будь якого заданого х Елемент, обернений до х Приклад 2. 9. Нехай ми хочемо знайти елемент, обернений до 79 в Z*211. У прикладі 2.3 була отримана рівність 1 = 3 Наслідок. 2.10. Для простого модуля р, кільце Zp є полем. Через ф(п) позначаємо порядок групи Zn*. Іншими словами, значення ф(п) дорівнює кількості натуральних чисел, що не перевищують п взаємно прості з п. ф називається функцією Ойлера. Теорема Ойлера (1763). Для взаємно простих цілого х і натурального п справедлива конгруенція хф(n) = 1 (modn). Доведення.Припустимо 1 < х < п і розглянемо х як елементи мультиплікативної групи Zn*. За теоремою Лагранжа порядок елемента х є дільником порядку групи, ф(п) в нашому випадку. Тому хф(n) = 11 в Zn*, звідси й випливає теорема. Випадок довільного х зводимо до попереднього, використавши конгруенцію Zn* = (х mod п) ф(n) (mod n). Як легко бачити, ф(р) = р — 1 для простого р. Звідси отримуємся такий наслідок теореми Ойлера. Мала теорема Ферма(1640). Якщо ціле х не ділиться на прості р, то хр-1 = 1 (modp) Китайська теорема про остачі (І ст. до н.е.). Для будь-якої пари взаємно простих натуральних чисел п1 і п2 та для будь-якої пари цілих чисел х1 і х2, можна знайти таке ціле х, де х = х1 (modn1) і х = х2 (mod п2). Доведення. За твердженням 2.2 для деяких цілих u1 і и2 маємо рівність u1n1+u2n2 = 1, з якої випливають співвідношення u1n1= 1 (modn2) і u2n2 = l(modn1). Використовуючи останні, легко пересвідчитись, що х = х2 u1n1 + х1 u2n2 задовільняє потрібні умови. Як видно з доведення, х для заданих n1, n2, х1 і х2 знаходиться ефективно за допомогою розширеного алгоритму Евкліда. Приклад 2.11. Нехай ми хочемо знайти ціле х, яке при діленні на 211 давало б остачу 100, а при діленні на 79 остачу 10. У прикладі 2.3 була отримана рівність Твердження 2.12. Нехай п = n1 f(x) = (х mod n1,x mod n2), (1) є Ізоморфізмом кілець. Доведення. Перевірка того, що f є гомоморфізмом, зводиться до перевірки того, що відображення fі(x) = (х mod n), є гомоморфізмом із Zn в Znі для і = 1,2. Останнє справді має місце, оскільки пі, ділить п. Сюр'єктивність є безпосереднім наслідком Китайської теореми остачі. Ін'єктивність випливає із тривіальності ядра — найменшим натуральним числом, яке ділиться націло на кожне із взаємно простих чисел n1, n2 є добутком n1n2=n Слід зауважити, що як f, так і обернене відображення f-1 обчислюються ефективним чином (див. приклад 2.11). Попереднє твердження разом із твердженням Б.2 дає Наслідок 2.13. Нехай п = n1n2, де n1 і n2 взаємно прості. Тоді звуження відображення (1) на Zn* є ізоморфізмом із цієї групи на прямий добуток груп Zn1* Наслідок 2.14. (мультиплікативність функції Ойлера) Для попарно взаємно простих Доведення. Випадок l = 2 безпосередньо випливає з наслідку 2.13. загальне твердження доводиться індукцією за l. Формула для функції Ойлера. Нехай п = Доведення. Спочатку розглянемо випадок l = 1, тобто п = Твердження 2.15. ф(п) > n(61nlnn) для п > 4. ; доведення, проведене в [135]. Див. також [13, вправа II.9(g)]. 2.5. Кільце Матриць,. Через Mк(Zn) позначаємо множину матриць розміру k х k з коефіцієнтами з Zn. З операціями додавання і множення матриць Mк(Zn) утворює кільце. Твердження 2.16. Нехай п = n1n2, де n1 і n2 взаємно прості Тоді відображення fk : Mк(Zn) Доведення. Очевидно, що fk переводить одиницю кільця Mк(Zn) в одиницю кільця Mк(Zn1) Щоб встановити сюр'єктивність, зауважимо, що fk діє покомпонентно і на кожній із k2 компонент це відображення є сюр'єктивним за Китайською теоремою про остачі. Ін'єктивність випливає із тривіальності ядра. За твердженням Б.2 отримуємо Наслідок 2.17. Звуження відображення fk на Mк(Zn)* є ізоморфізмом Із цієї групи на прямий добуток груп Mк(Zn1)* х Mк(Zn2)* Наслідок 2.18. Функція fk мультиплікативна: для попарно взаємно простих n1 n2,..., nl, справедлива рівність ф(n1, n2 ... nl) = ф(n1) ф(n2) ... ф(nl). Доведення.Випадок l = 2 безпосередньо випливає з наслідку 2.17 Загальне твердження доводиться індукцією за l. Теорема 2.19. Нехай п = Читайте також:
|
||||||||
|