1. Основи теорії чисел Теорія порівнянь
2. Історія теорії чисел
В
витоках теорії чисел як наукової дисципліни
виділяються дослідження Евкліда (3 століття до н. е.),
Діофанта (3 століття н. Е.), Ферма (1601-1665), Ейлера
(1707-1783), що збереглися в письмовому вигляді.
Історичні джерела підтверджують, що
творцем теорії чисел є Ейлер. При цьому
слід зазначити, що кілька теорем з теорії
чисел (як правило без доказів) були
сформульовані до Ейлера.
кожне
натуральне число, більше одиниці,
ділиться принаймні на два числа: на 1 і на саме
себе. Якщо число не має дільників, крім самого
себе і одиниці, то воно називається простим, а якщо у
числа є ще подільники, то складовим. одиниця ж
не рахується ні простим числом, ні складовим.
Наприклад, числа 7, 29- прості; числа 9, 15 -
складові (9 ділиться на 3, 15 ділиться на 3 і на 5).
Не про всякий числі можна відразу сказати, просте воно чи складене.
Якщо число менше ста, то, швидше за все ми відразу зможемо відповісти
на це питання. Однак з великими числами справа складніша.
Буває, що перевірка на простоту проводитися набагато довше, а
для роботи з великими цілими числами потрібні навіть
спеціальні комп'ютерні програми.
Пошук великих простих чисел має важливе значення для
математики і не тільки. Наприклад, в криптографії великі
прості числа використовуються в алгоритмах шифрування з відкритим
ключем. Для забезпечення надійності шифрування там
використовуються прості числа довжиною до 1024 біт.
Перемножити два числа порівняно неважко, особливо якщо у
Ми маємо калькулятор, а числа не надто великі. існує і
зворотне завдання - завдання факторизації - знаходження двох або
більше чисел, що дають при перемножуванні заданий число. ця
задача набагато важче, ніж множення чисел, і будь-кому, хто
намагався її вирішити, про це відомо.
Наприклад, якщо від нас вимагається помножити 67 на 113, то результат,
7571, буде отримано, напевно, менше ніж за хвилину. Якщо ж від
нас потрібно знайти два числа, твір яких одно 7571,
то, швидше за все, це займе у нас набагато більше часу.
6. Основна теорема арифметики
7. Взаємно прості числа і функція Ейлера
Два числа називаються взаємно простими, якщо вони не мають жодного
загального дільника крім одиниці.
Наприклад, числа 11 і 12 взаємно прості (у них немає спільних дільників
крім одиниці), числа 30 і 35- немає (у них є спільний дільник 5).
Дослідженням закономірностей, пов'язаних з цілими числами, довго
займався швейцарський математик Леонард Ейлер. Одним з питань,
яким він цікавився, був наступний: скільки існує
натуральних чисел, що не перевершують n і взаємно простих з n?
Відповідь на це питання була отримана Ейлером в 1763 році і ця відповідь
пов'язаний з канонічним розкладанням числа n на прості множники.
8. Число натуральних чисел, що не перевершують n і взаємно простих з n, називається функцією Ейлера і позначається
Наприклад, знайдемо кількість натуральних чисел, що не перевершують
12 і взаємно простих з 12. З ряду натуральних чисел 1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11 взаємно простими (не мають спільних дільників) з 12
будуть тільки числа 1, 5, 7, 11. Їх кількість дорівнює чотирьом.
Скористаємося функцією Ейлера і теж отримаємо 4.
Для цього спочатку запишемо канонічний розклад числа
12: 12 = 22 * 3.
Формулу Ейлера зручно використовувати для
великих n, якщо відомо розкладання числа n
на прості множники.
Для криптографії формула Ейлера важлива тим,
що вона дозволяє легко отримати число для
простих і деяких інших чисел.
Ейлер був одним з перших, хто використовував і
навіть удосконалив алгоритм Евкліда в
арифметичної формі.
11. Знаходження НОД за алгоритмом Евкліда
Алгоритм Евкліда - це алгоритм знаходження
найбільшого спільного дільника (НСД) пари цілих
чисел.
Найбільший спільний дільник (НСД) - це
число, яке ділить без залишку два числа і
ділиться саме без залишку на будь-який інший
дільник даних двох чисел. Простіше кажучи, це
найбільше число, на яке можна без
залишку розділити два числа, для яких шукається
НСД.
12. Опис алгоритму знаходження НСД розподілом
1. Більше число ділимо на меншу.
2. Якщо ділиться без залишку, то менша кількість і
є НОД (вихід з циклу).
3. Якщо є залишок, то більше число замінюємо
на залишок від ділення.
4. Переходимо до пункту 1.
Приклад 1: Знайти НСД для 30 і 18.
30/18 = 1 (залишок 12)
18/12 = 1 (залишок 6)
12/6 = 2 (залишок 0).
НСД (30, 18) = 6
13. Знаходження НОД за допомогою розкладання чисел на прості множники
Найбільший спільний дільник може бути знайдений
по розкладання чисел на прості множники.
Сформулюємо правило:
НСД двох цілих позитивних чисел a і b
дорівнює добутку всіх загальних простих
множників, що знаходяться в розкладах чисел a
і b на прості множники.
14. Знайдіть найбільший спільний дільник чисел 72 і 96
Рішення.
Розкладемо на прості множники числа 72 і 96:
72 = 2 · 2 · 2 · 3 · 3
96 = 2 · 2 · 2 · 2 · 2 · 3
Спільними простими множниками є 2, 2, 2 і 3.
Таким чином, НСД (72, 96) = 2 · 2 · 2 · 3 = 24.
відповідь:
НСД (72, 96) = 24.
15. Знаходження НОД трьох і більшої кількості чисел
Знаходження найбільшого загального дільника трьох
і більшої кількості чисел може бути зведене до
послідовному знаходженню НСД двох чисел.
Найбільший спільний дільник кількох чисел
a1, a2, ..., ak дорівнює числу dk, яке знаходиться при
послідовному обчисленні НСД (a1, a2) = d2,
НСД (d2, a3) = d3, НОД (d3, a4) = d4, ..., НОД (dk-1,
ak) = dk.
16. Знайти НСД (78, 294, 570 і 36)
Знайти НСД (78. 294. 570 і 36)
1) По алгоритму Евкліда визначимо найбільший
загальний дільник d2 двох перших чисел 78 і 294.
При розподілі отримуємо рівності 294 = 78 · 3 + 60;
78 = 60 · 1 + 18; 60 = 18 · 3 + 6 і 18 = 6 · 3.
Таким чином, d2 = НСД (78, 294) = 6.
2) Обчислимо d3 = НСД (d2, a3) = НСД (6, 570).
Т.к.570 = 6 · 95, значить, d3 = НСД (6, 570) = 6.
3) Обчислимо d4 = НСД (d3, a4) = НСД (6, 36) = 6.
Таким чином, найбільший спільний дільник чотирьох
даних чисел дорівнює d4 = 6.
НСД (78, 294, 570, 36) = 6.
17. Знаходження найменшого спільного кратного (НОК) даних чисел
найменшим
загальним
кратним
даних
натуральних
чисел
називають
найменше
натуральне число, кратне кожному з даних чисел.
Приклад.
НОК (24, 42) = 168. Це найменша кількість,
яке ділиться і на 24, і на 42.
18. Знаходження найменшого спільного кратного
Для знаходження НОК декількох даних
натуральних чисел треба:
1) розкласти кожне з даних чисел на прості
множники;
2) виписати розкладання більшої з чисел і
помножити його на відсутні множники з
розкладів інших чисел.
Найменша кратне двох взаємно простих чисел
дорівнює добутку цих чисел.
19. Знайти НОК (35; 40)
Розкладемо числа 35 і 40 на прості множники
35 = 5 ∙ 7, 40 = 2 ∙ 2 ∙ 2 ∙ 5 або 40 = 23 ∙ 5
Беремо розкладання більшої кількості 40 і доповнюємо
його відсутніми
множителями.
НОК (35; 40) = 23 ∙ 5 ∙ 7 = 40 ∙ 7 = 280.
Відповідь: НОК (35; 40) = 280.
20. Знайти НОК (75; 120; 150)
Розкладемо числа 75, 120 і 150 на прості
множники.
75 = 3 ∙ 52, 120 = 23 ∙ 3 ∙ 5, 150 = 2 ∙ 3 ∙ 52
Візьмемо розкладання більшої кількості 150 і
доповнимо його двома «двійками», так як в
розкладанні числа 120 є три «двійки», а в
розкладанні числа 150 - тільки одна.
НОК (75; 120; 50) = 2 ∙ 3 ∙ 52 ∙ 2 ∙ 2 = 150 ∙ 4 = 600.
Відповідь: НОК (75; 120; 150) = 600.
21. Теорія порівнянь
Кожному цілому числу відповідає певний
залишок від ділення його на m;
якщо двом цілим а й b відповідає один і той же
залишок m, то вони називаються равноостаточнимі по
модулю m або порівнянними за модулем m.
Порівнянність чисел а і b по модулю m записується
так:
що читається: а порівняно з b за модулем m.
порівняння
виявляють
корисні
для
математиків і криптографов властивості, багато в чому
схожі на властивості рівностей.
Ці властивості дозволяють істотно спрощувати
арифметичні обчислення.
Так, наприклад, властивості порівнянь корисні при
розрахунках в алгоритмах шифрування з відкритим
ключем.
23. Властивості порівнянь
1.Якщо a - b ділиться на m, то
наприклад,
так як 15 -1 = 14, а 14 кратно 7.
2. Якщо
то
наприклад,
то
24. Властивості порівнянь
3. Якщо
4. Якщо,
просте з m.
наприклад
тоді
то з взаємно
25. Мала теорема Ферма
В основі алгоритму шифрування по системі RSA
лежить
теорема,
сформульована
в
початку
сімнадцятого століття без докази французьким
математиком П'єром Ферма (Pierre Fermat). її часто
називають "Малої теореми Ферма".
Якщо p - просте число, а m - будь-яке число, яке
не ділиться на p, то
тобто число mp-1 при діленні на p дає залишок 1.
