Властивості простих чисел

Існують різні властивості простих чисел. Частина з них доведена, інша – ні, якісь існують в статусі припущень. Серед основних доведених властивостей можна виділити наступні.

Безліч простих чисел нескінченно (т. Е. Серед простих чисел немає найбільшого).
Доказ цієї властивості можна подивитися тут.

Серед простих дільників складеного числа є хоча б один квадрат, якого менше або дорівнює даним складеному числу.
Нехай p – найменший простий дільник числа n. Доведемо, що p2 ≤ n.

Якщо p – дільник складеного числа n, тоді повинен існувати інший дільник q числа n такий, що n = pq. Оскільки p найменший простий дільник, то дільників менше його бути не може, тому q ≥ p. З цього випливає, що p * p ≤ p * q, т. Е. P2 ≤ pq або p2 ≤ n.

Це властивість використовують при перевірці числа на простоту. Якщо завжди існує простий дільник складеного числа, квадрат якого менше цього числа або дорівнює йому, то немає чого шукати інші подільники, щоб зробити висновок про те, що перевіряється число складене. Тому можна обмежитися перевіркою подільності числа n на прості дільники p, для яких p2 ≤ n.

Зазвичай при цьому з n витягують корінь і округлюють до цілого. Після цього перебирають всі подільники до отриманого числа. Якщо жоден з них не є дільником для n, то значить інших простих дільників немає і досліджуване число просте.

Наприклад, перевіримо число 37 на простоту. Корінь з 37, округлений до цілого в меншу сторону, дорівнює 6. Отже, треба перевірити подільність на 2, 3, 4, 5, 6. Ні на одне з цих чисел 37 не ділиться, значить це просте число.

Всі натуральні числа можна представити у вигляді суми двадцяти простих доданків.
“Мала теорема Ферма”: якщо p – просте число, таке що число n на нього не ділиться, то число np – 1 – 1 завжди ділиться на p. Наприклад, 34 не ділиться на 3, але 343-1 – 1 = 342 – 1 = 1156 – 1 = 1155 ділиться.
Недоведені властивості простих чисел:

Будь-яке парне число можна виразити у вигляді суми двох простих чисел. Наприклад, 16 = 11 + 5, 64 = 23 + 41, 66 = 29 + 37.
Будь-яке велике непарне число можна представити у вигляді суми трьох простих непарних чисел.
Будь великі парні числа можна представити у вигляді суми чотирьох простих непарних чисел.
Будь-яке парне число можна представити у вигляді різниці двох простих чисел.


1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Властивості простих чисел