logo
шкм

Відкриті питання

Досі існує багато відкритих запитань відносно простих чисел, найвідоміші з яких були перераховані Едмундом Ландау на П'ятому Міжнародному математичному конгресі:

  1. Проблема Гольдбаха (перша проблема Ландау): довести або спростувати, що кожне парне число, більше двох, може бути представлено у вигляді суми двох простих чисел, а кожне непарне число, більше 5, може бути представлено у вигляді суми трьох простих чисел.

  2. Друга проблема Ландау : чи нескінченна множина «простих близнюків» — простих чисел, різниця між якими дорівнює 2?

  3. Гіпотеза Лежандра (третя проблема Ландау) чи вірно, що між і завжди знайдеться просте число?

  4. Четверта проблема Ландау: чи нескінченна множина простих чисел виду ?

Відкритою проблемою є також існування нескінченної кількості простих чисел у багатьох цілочисельних послідовностях, включаючи числа Фібоначчі, числа Ферма і т. д.

Застосування

Великі прості числа (порядка ) використовують в криптографії з відкритим ключем. Прості числа також використовують в хеш-таблицях і для генерації псевдовипадкових чисел (зокрема, в генераторі псевдовипадкових чисел Вихор Мерсенна).

4.Найбільший спільний дільник(НСД),найменше спільне кратне(НСК)

Найбільший спільний дільник

Найбі́льший спі́льний дільни́к (НСД) двох або більше невід'ємних цілих чисел - це найбільше натуральне число, на яке ці числа ділиться без остачі.

Позначення

Найбільший спільник дільник двох чисел a і b позначається як НСД(a, b), деколи (a, b). В англомовній літературі прийнято вживати позначення gcd(a, b).

Приклад

Число 54 може бути виражене як добуток двох інших цілих чисел кількома способами:

Отже дільники числа 54 є:

Аналонічно дільники числа 24 є:

Числа, які є у обох цих списках, є спільними дільниками чисел 54 та 24:

Найбільшим серед них є число 6. Воно найбільшим спільним дільником чисел 54 та 24. Можна записати:

Скорочення дробів

Найбільший спільний дільник використовується для скорочення дробів. Наприклад, НСД(42, 56) = 14, тому,

Властивості

Обчислення НСД методом розкладу на прості множники

Нехай розклад чисел на прості множники:

Тоді

НСД

Приклад

Визначимо НСД . Розклад на прості множники:

,

або, подаючи для наглядності нульові степені,

,

Отже,

НСД

Ефективним алгоритмом обчислення НСД є алгоритм Евкліда

НСД в кільці многочленів

В кільці многочленів над довільним полем найбільшим спільним дільником многочленів і , принаймі один з яких є відмінний від нуля, називаємо нормований многочлен найвищого степеня, який ділить обидва многочлени і Обчислити НСД можна розкладаючи многочлен на нескоротні множники. Можна застосувати також алгоритм Евкліда.

Приклад

Обчислимо НСД двох многочленів над полем дійсних чисел:

Розкладаючи многочлени на нескоротні множники

,

отримуємо

НСД .

Найменше спільне кратне

Найменше спільне кратне (НСК) двох цілих чисел a, b називаємо найменше натуральне число, яке є кратним обох цих чисел. Позначаємо НСК(a, b), в англомовній літературі LCM(a, b). Отже НСК(a, b) є найменшим натуральним числом, яке ділиться без залишку на обидва числа a, b. Означення можна – очевидним способом – узагальнити на довільну кількість аргументів.

Властивості

Обчислення НСК методом розкладу на прості множники

Нехай розклад чисел на прості множники:

Тоді

НСК

Приклад

Визначимо НСК . Розклад на прості множники:

,

або, подаючи для наглядності нульові степені,

,

Отже,

НСК

НСК можна теж обчислити за допомогою рівності НСК(a, b) =|ab|/НСД(a, b), використавши для обчислення НСД ефективний алгоритм Евкліда

5.Ділення з остачею

Ділення з остачею (ділення по модулю, ділення націло) — арифметична операція, результатом якої є два числа: неповна частка та остача.

Визначення

Поділити з остачею ціле число на натуральне число означає представити його у вигляді:

— називають неповною часткою,

 — остачею від ділення.

Якщо то:

Наприклад, при діленні з остачею на отримаємо неповну частку та остачу

Також можливе ділення з остачею дійсних чисел на додатні дійсні числа.

При діленні на від'ємне число, навідь для цілих чисел, результат не є однозначно інтерпретуємим. В теорії чисел прийнято, що в мовах програмування, здебільшого, це не виконується.