Прості числа. Складові числа. Числа. Прості числа Ні простим ні складовим числом є

Теорема.

Простих чисел нескінченно багато.

Доведення.

Припустимо, що це не так. Тобто, припустимо, що простих чисел за все n штук, і ці прості числа є p 1, p 2, ..., p n. Покажемо, що ми завжди можемо знайти просте число, відмінне від зазначених.

Розглянемо число, p дорівнює p 1 · p 2 · ... · p n +1. Зрозуміло, що це число відмінно від кожного з простих чисел p 1, p 2, ..., p n. Якщо число p - просте, то теорема доведена. Якщо ж це число складене, то в силу попередньої теореми існує простий дільник цього числа (позначимо його p n + 1). Покажемо, що цей дільник не збігається ні з одним з чисел p 1, p 2, ..., p n.

Якби це було не так, то за властивостями подільності твір p 1 · p 2 · ... · p n ділилося б на p n + 1. Але на p n + 1 ділиться і число p, яка дорівнює загальній кількості p 1 · p 2 · ... · p n +1. Звідси випливає, що на p n + 1 повинно ділитися другий доданок цієї суми, що дорівнює одиниці, а це неможливо.

Так доведено, що завжди може бути знайдено нове просте число, що не полягає серед будь-якої кількості наперед заданих простих чисел. Отже, простих чисел нескінченно багато.

Отже, в силу того, що простих чисел нескінченно багато, при складанні таблиць простих чисел завжди обмежують себе зверху будь-яким числом, звичайно, 100, 1 000, 10 000 і т.д.

решето Ератосфена

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

Найочевиднішим методом вирішення цього завдання є послідовна перевірка цілих позитивних чисел, починаючи з 2, і закінчуючи 100, на наявність позитивного подільника, який більше 1 і менше перевіряється числа (з властивостей подільності ми знаємо, що абсолютна величина дільника не перевищує абсолютної величини ділимо, відмінного від нуля). Якщо такий дільник не знайдений, то перевіряється число є простим, і воно заноситься в таблицю простих чисел. Якщо ж такий дільник знайдений, то перевіряється число є складовим, воно НЕ заноситься в таблицю простих чисел. Після цього відбувається перехід до наступного числа, яке аналогічно перевіряється на наявність дільника.

Наведемо кілька перших кроків.

Починаємо з числа 2. Число 2 не має позитивних дільників, крім 1 і 2. Отже, воно просте, тому, заносимо його в таблицю простих чисел. Тут слід сказати, що 2 є найменшим простим числом. Переходимо до числа 3. Його можливим позитивним дільником, відмінним від 1 і 3, є число 2. Але 3 на 2 не ділиться, тому, 3 - просте число, і його також потрібно занести в таблицю простих чисел. Переходимо до числа 4. Його позитивними дільниками, відмінними від 1 і 4, можуть бути числа 2 і 3, перевіримо їх. Число 4 ділиться на 2, тому, 4 - складене число, і його не потрібно заносити в таблицю простих чисел. Звернемо увагу на те, що 4 - найменше складене число. Переходимо до числа 5. Перевіряємо, чи є його дільником хоча б одне з чисел 2, 3, 4. Так як 5 не ділиться ні на 2, ні на 3, ні на 4, то воно просте, і його треба записати в таблицю простих чисел. Далі відбувається перехід до чисел 6, 7, і так далі до 100.

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

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

Покажемо решето Ератосфена в дії при складанні таблиці простих чисел до 50.

Спочатку записуємо по порядку числа 2, 3, 4, ..., 50.

Перше записане число 2 є простим. Тепер від числа 2 послідовно переміщаємося вправо на два числа і зачеркиваем ці числа, поки не доберемося до кінця що накопичується таблиці чисел. Так будуть викреслені всі числа, кратні двом.

Першим таким за 2 невикреслених числом є 3. Це число просте. Тепер від числа 3 послідовно переміщаємося вправо на три числа (враховуючи і вже закреслені числа) і викреслюємо їх. Так будуть викреслені всі числа, кратні трьом.

Першим таким за 3 невикреслених числом є 5. Це число просте. Тепер від числа 5 послідовно переміщаємося вправо на 5 чисел (враховуємо і закреслені раніше числа) і викреслюємо їх. Так будуть викреслені всі числа, кратні п'яти.

Далі викреслюємо числа, кратні 7, потім, кратні 11 і так далі. Процес закінчується, коли не залишиться чисел для викреслювання. Нижче показана закінчена таблиця простих чисел до 50, отримана за допомогою решета Ератосфена. Все незачеркнутие числа є простими, а все закреслені числа - складовими.

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

Теорема.

Найменший позитивний і відмінний від одиниці дільник складеного числа a не перевищує, де - з a.

Доведення.

Позначимо буквою b найменший і відмінний від одиниці дільник складеного числа a (число b є простим, що випливає з теореми, доведеною в самому початку попереднього пункту). Тоді існує таке ціле число q, що a = b · q (тут q - позитивне ціле число, що випливає з правил множення цілих чисел), причому (при b> q порушиться умова, що b - найменший дільник числа a, так як q також є дільником числа a в силу рівності a = q · b). Помноживши обидві частини нерівності на позитивне і більше одиниці ціле число b (це нам дозволяють зробити), отримуємо, звідки і.

Що ж нам дає доведена теорема, щодо решета Ератосфена?

По-перше, викреслювання складених чисел, кратних простому числу b слід починати з числа, рівного (це випливає з нерівності). Наприклад, викреслювання чисел, кратних двом, слід починати з числа 4, кратних трьом - з числа 9, кратних п'яти - з числа 25, і так далі.

По-друге, складання таблиці простих чисел до числа n за допомогою решета Ератосфена можна вважати закінченим тоді, коли будуть викреслені всі складові числа, кратні простих чисел, що не перевершують. У нашому прикладі n = 50 (так як ми складаємо таблицю простих чисел до 50) і, тому решето Ератосфена має відсіяти все складові числа, кратні простим числам 2, 3, 5 і 7, які не перевищують арифметичного квадратного кореня з 50. Тобто, нам далі не потрібно займатися пошуком і викреслюванням чисел, кратних простих чисел 11, 13, 17, 19, 23 і так далі до 47, так як вони вже будуть викреслені, як кратні меншим простим числам 2, 3, 5 і 7 .

Дане число просте або складене?

Деякі завдання вимагають з'ясування, чи є дане число простим чи складовим. У загальному випадку ця задача далеко не проста, особливо для чисел, запис яких складається з значної кількості знаків. У більшості випадків доводиться шукати будь-якої специфічний спосіб її вирішення. Однак ми спробуємо дати напрямок ходу думок для нескладних випадків.

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

Приклад.

Доведіть, що число 898 989 898 989 898 989 складене.

Рішення.

Сума цифр цього числа дорівнює 9 · 8 + 9 · 9 = 9 · 17. Так як число, що дорівнює 9 · 17 ділиться на 9, то за ознакою подільності на 9 можна стверджувати, що вихідне число також ділиться на 9. Отже, воно складене.

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

Самий логічний підхід полягає в переборі всіх можливих дільників даного числа. Якщо жоден з можливих дільників НЕ буде істинним дільником даного числа, то це число буде простим, в іншому випадку - складовим. З теорем, доведених в попередньому пункті, слід, що подільники даного числа a потрібно шукати серед простих чисел, що не перевершують. Таким чином, дане число a можна послідовно ділити на прості числа (які зручно брати з таблиці простих чисел), намагаючись знайти дільник числа a. Якщо буде знайдений дільник, то число a - складене. Якщо ж серед простих чисел, що не перевершують, не опиниться подільника числа a, то число a - просте.

Приклад.

число 11 723 просте або складене?

Рішення.

З'ясуємо, до якого простого числа можуть бути подільники числа 11 723. Для цього оцінимо.

Досить очевидно, що , Так як 200 2 = 40 000, а 11 723<40 000 (при необходимости смотрите статью порівняння чисел). Таким чином, можливі прості дільники числа 11 723 менше числа 200. Це вже значно полегшує нашу задачу. Якби ми цього не знали, то нам би довелося перебирати всі прості числа не до 200, а аж до числа 11 723.

При бажанні можна оцінити більш точно. Так як 108 2 = 11 664, а 109 2 = 11 881, то 108 2<11 723<109 2 , следовательно, . Таким чином, будь-яка з простих чисел, менших 109, потенційно є простим дільником даного числа 11 723.

Тепер ми будемо послідовно ділити число 11 723 на прості числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 , 73, 79, 83, 89, 97, 101, 103, 107. Якщо число 11 723 розділиться без остачі на одне із записаних простих чисел, то воно буде складовим. Якщо ж воно не ділиться ні на одне із записаних простих чисел, то вихідне число просте.

Не будемо описувати весь цей монотонний і одноманітний процес ділення. Відразу скажемо, що 11 723

Відповідь Іллі коректний, але не дуже докладний. У 18 столітті, до речі, одиницю ще вважали простим числом. Наприклад, такі великі математики як Ейлер і Гольдбах. Гольдбах автор однієї з семи завдань тисячоліття - гіпотези Гольдбаха. У початковій формулюванні затверджується, що будь-яке парне число можна подати у вигляді суми двох простих чисел. Причому спочатку 1 враховувалася як просте число, і ми бачимо таке: 2 = 1 + 1. Це найменший приклад, що задовольняє вихідного формулювання гіпотези. Пізніше її підправили, і формулювання набула сучасного вигляду: "всяке парне число, починаючи з 4, представимо у вигляді суми двох простих чисел".

Згадаймо визначення. Простим є натуральне число р, що має тільки 2 різних натуральних дільники: саме р і 1. Слідство з визначення: у простого числа р тільки один простий дільник - саме р.

Тепер припустимо, що 1 просте число. За визначенням у простого числа тільки один простий дільник - воно саме. Тоді вийде, що будь-яке просте число, більше 1, ділиться на відмінне від нього просте число (на 1). Але два різних простих числа не можуть ділитися один на одного, тому що інакше це не прості, а складові числа, і це суперечить визначенню. При такому підході виходить, що існує тільки 1 просте число - сама одиниця. Але це абсурд. Отже, 1 не проста число.

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

При такому розгляді не важко виявити аналоги простих чисел в інших алгебраїчних структурах. Припустимо, що у нас є мультиплікативна група, утворена з ступенів 2, починаючи з 1: 2, 4, 8, 16, ... і т.д. 2 виступає тут утворюючим елементом. Простим числом в цій групі назвемо число, більше найменшого елемента, і ділиться тільки на себе і на найменший елемент. У нашій групі такими властивостями володіє тільки 4. Все. Більше простих чисел в нашій групі не існує.

Якби 2 теж була простим числом в нашій групі, то см. Перший абзац, - знову вийшло б, що простим числом є тільки 2.

Одиниця просте число? Ні, одиниця не є простим числом.

0 просте число? Ні, нуль не є простим числом.

2 просте число? Так, 2 просте число. 2 є єдиним парних простим числом.

3 просте число? Так, 3 просте число.

5 просте число? Так, 5 просте число.

7 просте число? Так, 7 просте число.

9 просте число? Ні, 9 не є простим числом. Адже 9 ділиться на себе, на одиницю і на три.

11 просте число? Так, 11 просте число.

13 просте число? Так, 13 просте число.

15 просте число? Ні, 15 не є простим числом. Адже 15 ділиться на себе, на одиницю, на три, на п'ять.

17 просте число? Так, 17 просте число.

19 просте число? Так, 19 просте число.

20 просте число? Ні, 20 не є простим числом. Адже 20 ділиться на себе, на одиницю, на два, на чотири, на п'ять, на десять.

777 просте число? Ні, 777 не є простим числом. Адже 777 ділиться на себе, на одиницю, на 3, на 7, на 37.

997 просте число? Так, 997 просте число.

Простим числом є натуральне число, яке ділиться тільки на себе і на одиницю.

На даний момент невідомі поліноміальні алгоритми факторизації чисел, хоча і не доведено, що таких алгоритмів не існує. На передбачуваної великий обчислювальної складності задачі факторизації базується криптосистема RSA і деякі інші. Факторизация з поліноміальною складністю теоретично можлива на квантовому комп'ютері за допомогою алгоритму Шора.

Алгоритми пошуку та розпізнавання простих чисел

Прості способи знаходження початкового списку простих чисел аж до деякого значення дають решето Ератосфена, решето Сундарама і решето Аткіна.

Однак, на практиці замість отримання списку простих чисел найчастіше потрібна перевірити, чи є дане число простим. Алгоритми, що вирішують цю задачу, називаються тестами простоти. Існує безліч поліноміальних тестів простоти, але більшість їх є імовірнісними (наприклад, тест Міллера - Рабина) і використовуються для потреб криптографії. У 2002 році було доведено, що задача перевірки на простоту в загальному вигляді полиномиально можна вирішити, але запропонований детермінований тест Агравал - Каяла - Сакса має досить велику обчислювальну складність, що ускладнює його практичне застосування.

Для деяких класів чисел існують спеціалізовані ефективні тести простоти (див. Нижче).

Нескінченність безлічі простих чисел

Простих чисел нескінченно багато. Найстаріше відоме доказ цього факту було дано Евклідом в «Засадах» (книга IX, твердження 20). Його доказ може бути коротко відтворено так:

Математики пропонували інші докази. Одне з них (наведене Ейлером) показує, що сума величин, зворотних до перших nпростим числам, необмежено зростає з ростом n.

Числа Мерсенна вигідно відрізняються від інших наявністю ефективного тесту простоти: тесту Люка - Лемера. Завдяки йому прості числа Мерсенна давно утримують рекорд як найбільші відомі прості.

За перебування простих чисел з більш ніж 100 000 000 і 1 000 000 000 десяткових цифр EFF призначила грошові призи відповідно в 150 000 і 250 000 доларів США. Раніше EFF вже присуджувала призи за перебування простих чисел з 1 000 000 і 10 000 000 десяткових цифр.

Прості числа спеціального виду

Існує ряд чисел, простота яких може бути встановлена ​​ефективно з використанням спеціалізованих алгоритмів.

Для пошуку простих чисел позначених типів в даний час використовуються проекти розподілених обчислень GIMPS, PrimeGrid, [Email protected], Seventeen or Bust, Riesel Sieve, [Email protected].

деякі властивості

• Якщо p - просте, і p ділить ab, то p ділить a або b. Доказ цього факту було дано Евклідом і відомо як лема Евкліда. Воно використовується в доведенні основної теореми арифметики.
• кільце відрахувань $\backslash \; Mathbb\; (Z)\; \_n$є полем тоді і тільки тоді, коли $n$- просте.
• Характеристика кожного поля - це нуль або просте число.
• якщо $p$- просте, а $a$- натуральне, то $a\; ^\; p-a$ділиться на $p$(Мала теорема Ферма).
• якщо $G$- кінцева група, порядок якої $|\; G\; |$ділиться на $p$, то $G$містить елемент порядку $p$(Теорема Коші).
• якщо $G$- кінцева група, і $p\; ^\; n$- максимальний ступінь $p$, Яка ділить $|\; G\; |$, то $G$має підгрупу порядку $p\; ^\; n$, Звану сіловской підгрупою, більш того, кількість сіловскіх підгруп одно $pk\; +\; 1$для деякого цілого $k$(Теореми Силова).
• натуральне $p>\; 1$є простим тоді і тільки тоді, коли $(P-1)!\; +\; 1$ділиться на $p$(Теорема Вільсона).
• якщо $n>\; 1$- натуральне, то існує просте $p$, Таке, що (Постулат Бертрана).
• Ряд чисел, зворотних до простих, розходиться. Більш того, при $x\; \backslash \; to\; \backslash \; infty$
• Будь-яка арифметична прогресія виду $a,\; a\; +\; q,\; a\; +\; 2\; q,\; a\; +\; 3\; q,\; ...$, де $a,\; q>\; 1$- цілі взаємно прості числа, містить нескінченно багато простих чисел (теорема Діріхле про прості числа в арифметичній прогресії).
• Будь-яке просте число, більше 3, представимо у вигляді $6k\; +\; 1$або $6k-1$, де $k$- деяке натуральне число. Звідси, якщо різниця між кількома послідовними простими числами (при k> 1) однакова, то вона обов'язково кратна 6 - наприклад: 251-257-263-269; 199-211-223; 20183-20201-20219.
• якщо $p>\; 3$- просте, то $p\; ^\; 2-1$кратно 24 (справедливо також для всіх непарних чисел, що не діляться на 3).
• Теорема Гріна-Тао. Існують як завгодно довгі кінцеві арифметичній прогресії, що складаються з простих чисел.
• $n\; ^\; k-1$, де n>2, k> 1. Інакше кажучи, число, наступне за простим, не може бути квадратом або більш високим ступенем з підставою, великим 2. З цього випливає також, що якщо просте число має вигляд $2\; ^\; k-1$, то k- просте (див. Числа Мерсенна).
• Ніяке просте число не може мати вигляд $n\; ^\; (2k\; +\; 1)\; +1$, де n>1, k> 0. Інакше кажучи, число, попереднє простому, не може бути кубом або вищої непарної ступенем з підставою, великим 1.

Формули для знаходження простих чисел

У різний час робилися спроби вказати вираз, значеннями якого при різних значеннях вхідних в нього змінних були б прості числа. Л. Ейлер вказав многочлен $\backslash \; Textstyle\; n\; ^\; 2-n\; +\; 41,$приймає прості значення при n = 0, 1, 2, ..., 40. Однак при n = 41значення многочлена є складовим числом. Можна довести, що не існує многочлена від однієї змінної n, який приймає прості значення при всіх цілих n. П. Ферма припустив, що всі числа виду 2 2 k + 1прості; проте Ейлер спростував цю гіпотезу, довівши, що число 2 2 5 + 1 = 4 294 967 297 - складене.

Проте, існують многочлени, безліч позитивних значень яких при невід'ємних значеннях змінних збігається з безліччю простих чисел. Одним із прикладів є многочлен

• $\backslash \; Begin\; (align)$

& (K + 2) (1 - ^ 2 - [(gk + 2g + k + 1) (h + j) + h - z] ^ 2 - ^ 2 - \\ & ^ 2 - ^ 2 - [(a ^ 2 - 1) y ^ 2 + 1 - x ^ 2] ^ 2 - \\ & ^ 2 - [((a + u ^ 2 (u ^ 2 - a)) ^ 2 - 1) (n + 4dy) ^ 2 + 1 - (x + cu) ^ 2] ^ 2 - ^ 2 - \\ & [(a ^ 2 - 1) l ^ 2 + 1 - m ^ 2] ^ 2 - ^ 2 - ^ 2 - \ \ & ^ 2 - ^ 2) \ end (align)що містить 26 змінних і має ступінь 25. найменша ступіньдля відомих многочленів такого типу - 5 при 42 змінних; найменше число змінних - 10 при ступеня близько 1,6 · 10 45. Цей результат є окремим випадком доведеною Юрієм Матіясевіч диофантово будь-якого рахункового безлічі.

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

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

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

додатки

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

Варіації і узагальнення

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

Див. також

Напишіть відгук про статтю "Просте число"

Примітки

Уривок, що характеризує Просте число

Наташа була спокійніше, але не веселіше. Вона не тільки уникала будь-яких зовнішніх умов радості: балів, катання, концертів, театру; але вона ні разу не сміялася так, щоб через сміху її не можна почути були сльози. Вона не могла співати. Як тільки починала вона сміятися чи пробувала одна сама з собою співати, сльози душили її: сльози каяття, сльози спогадів про те безповоротний, чистому часу; сльози досади, що так, задарма, погубила вона своє молоде життя, яка могла б бути така щаслива. Сміх і спів особливо здавалися їй блюзнірством над її горем. Про кокетуванні вона і не думала ні разу; їй не доводилося навіть утримуватися. Вона говорила і відчувала, що в цей час всі чоловіки були для неї зовсім те ж, що блазень Настасья Іванівна. Внутрішній страж твердо забороняв їй всяку радість. Та й не було в ній всіх колишніх інтересів життя з того дівочого, безтурботного, повного надій складу життя. Найчастіше і найболючіше згадувала вона осінні місяці, полювання, дядечка і святки, проведені з Nicolas в Відрадному. Що б вона дала, щоб повернути хоч один день з того часу! Але вже це назавжди було скінчено. Передчуття не обманює її тоді, що той стан свободи і відкритості для всіх радощів ніколи вже не повернеться більше. Але жити треба було.
Їй приємно було думати, що вона не краще, як вона перш думала, а гірше і набагато гірше всіх, всіх, хто тільки є на світі. Але цього мало було. Вона знала це і питала себе: «Що ж далі? А далі нічого не було. Не було ніякої радості в житті, а життя проходила. Наташа, мабуть, намагалася тільки нікому не бути тягарем і нікому не заважати, але для себе їй нічого не потрібно було. Вона віддалялася від всіх домашніх, і тільки з братом Петром їй було легко. З ним вона любила бувати більше, ніж з іншими; і іноді, коли була з ним віч-на-віч, сміялася. Вона майже не виїжджала з дому і з приїжджали до них рада була тільки одному П'єру. Не можна було ніжніше, обережніше і разом з тим серйозніше звертатися, ніж звертався з нею граф Безухов. Наташа Осссознательно відчувала цю ніжність звернення і тому знаходила велике задоволення в його суспільстві. Але вона навіть не була вдячна йому за його ніжність; ніщо добре з боку П'єра не здавалася їй зусиллям. П'єру, здавалося, так природно бути добрим з усіма, що не було ніякої заслуги в його доброті. Іноді Наташа помічала збентеження і незручність П'єра в її присутності, особливо, коли він хотів зробити для неї що-небудь приємне або коли він боявся, щоб що-небудь в розмові не навело Наташу на важкі спогади. Вона помічала це і приписувала це його загальної доброті і сором'язливості, яка, за її поняттями, така ж, як з нею, повинна була бути і з усіма. Після тих випадкових слів про те, що, якщо б він був вільний, він на колінах просив би її руки і любові, сказаних в хвилину такого сильного хвилювання для неї, П'єр ніколи не говорив нічого про свої почуття до Наташі; і для неї було очевидно, що ті слова, тоді так втішити її, були сказані, як говоряться всякі безглузді слова для втіхи плаче дитини. Чи не тому, що П'єр був одружений чоловік, але від того, що Наташа відчувала між собою і їм надзвичайно ту силу моральних перешкод - відсутність якої вона відчувала з Kyрагіним, - їй ніколи в голову не приходило, щоб з її відносин з П'єром могла вийти не тільки любов з її або, ще менше, з його боку, але навіть і той рід ніжною, визнає себе, поетичної дружби між чоловіком і жінкою, якій вона знала кілька прикладів.
В кінці Петрівського посту Горпина Іванівна Бєлова, Отрадненського сусідка Ростові, приїхала в Москву поклонитися московським угодників. Вона запропонувала Наталі говіти, і Наташа з радістю вхопилася за цю думку. Незважаючи на заборону доктора виходити рано вранці, Наташа наполягла на тому, щоб говіти, і говіти не так, як говіли звичайно в будинку Ростові, тобто відслухати на дому три служби, а щоб говіти так, як говіли Горпина Іванівна, тобто весь тиждень , не пропускаючи жодної вечірні, обідні або заутрені.
Графині сподобалося це старанність Наташі; вона в душі своїй, після безуспішного медичного лікування, сподівалася, що молитва допоможе їй більше ліків, і хоча з острахом і приховуючи від доктора, але погодилася на бажання Наташі і доручила її Бєлової. Горпина Іванівна о третій годині ночі приходила будити Наташу і здебільшого знаходила її вже не спить. Наташа боялася проспати час заутрені. Поспішно вмиваючись і з смиренням одягаючись в найпоганіше свою сукню і стареньку мантилью, здригаючись від свіжості, Наташа виходила на пустельні вулиці, прозоро освітлені ранкової зорею. За порадою Горпини Іванівни, Наташа говіли не в своїй парафії, а в церкві, в якій, за словами побожною Бєлової, був священик вельми суворий і високою життя. У церкві завжди було мало народу; Наташа з Бєлової ставали на звичне місце перед іконою Божої Матері, вправленої в зад лівого кліросу, і нове для Наташі почуття смирення перед великим, незбагненним, охоплювало її, коли вона в цей незвичний годину ранку, дивлячись на чорний лик Божої Матері, освітлений і свічками , горіли перед ним, і світлом ранку, падав з вікна, слухала звуки служби, за якими вона намагалася стежити, розуміючи їх. Коли вона розуміла їх, її особисте відчуття з своїми відтінками приєднувалося до її молитві; коли вона не розуміла, їй ще солодшим було думати, що бажання розуміти все є гордість, що розуміти всього не можна, що треба тільки вірити і віддаватися Богу, який в ці хвилини - вона відчувала - керував її душею. Вона хрестилася, вклонилась і, коли не розуміла, то тільки, жахаючись перед своєю мерзотою, просила бога простити її за все, за все, і помилувати. Молитви, яким вона найбільше віддавалася, були молитви розкаяння. Повертаючись додому в ранню годину ранку, коли зустрічалися тільки каменярі, які йшли на роботу, двірники, вимітали вулицю, і в будинках ще всі спали, Наташа відчувала нове для неї почуття можливості виправлення себе від своїх вад і можливості нової, чистої життя і щастя.
У продовження усього тижня, в яку вона вела цю життя, почуття це росло з кожним днем. І щастя долучитися або повідомити, як, радісно граючи цим словом, говорила їй Горпина Іванівна, уявлялося їй настільки великим, що їй здавалося, що вона не доживе до цього блаженного неділі.
Але щасливий день настав, і коли Наташа в це пам'ятне для неї неділю, в білому серпанкові плаття, повернулася від причастя, вона в перший раз після багатьох місяців відчула себе спокійною і не обтяжуючу життям, яка мала відбутися їй.
Приїжджав в цей день доктор оглянув Наташу і велів продовжувати ті останні порошки, які він прописав два тижні тому.
- Неодмінно продовжувати - вранці і ввечері, - сказав він, мабуть, сам сумлінно задоволений своїм успіхом. - Тільки, будь ласка, акуратніше. Будьте певні, графиня, - сказав жартівливо доктор, в м'якоть руки спритно підхоплюючи золотий, - скоро знову заспіває і зарезвітся. Дуже, дуже їй на користь останнім ліки. Вона дуже посвіжіла.
Графиня глянула на нігті і поплювавши, з веселим обличчям повертаючись до вітальні.

На початку липня в Москві поширювалися все більше і більше тривожні чутки про хід війни: говорили про відозві государя до народу, про приїзд самого государя з армії в Москву. І так як до 11 го липня маніфест і відозву не було отримано, то про них і про становище Росії ходили перебільшені чутки. Говорили, що государ від'їжджає тому, що армія в небезпеці, говорили, що Смоленськ зданий, що у Наполеона мільйон війська і що тільки диво може врятувати Росію.
11 го липня, в суботу, був отриманий маніфест, але ще не надрукований; і П'єр, колишній у Ростові, обіцяв на другий день, у неділю, приїхати обідати і привезти маніфест і відозву, які він дістане у графа Растопчина.
Цієї неділі Ростова, як звичайно, поїхали до обідні в домову церкву Розумовських. Був жаркий липневий день. Вже о десятій годині, коли Ростова виходили з карети перед церквою, в жаркому повітрі, в криках рознощиків, в яскравих і світлих літніх сукнях натовпу, в запилених листі дерев бульвару, в звуках музики і білих панталонах минулого на розлучення батальйону, в громі бруківці і яскравому блиску жаркого сонця було те літнє ловлення, достаток і невдоволення справжнім, яке особливо різко відчувається в ясний жаркий день в місті. У церкві Розумовських була вся знать московська, все знайомі Ростові (в цей рік, як би очікуючи чогось то, дуже багато багатих сімей, звичайно роз'їжджаються по селах, залишилися в місті). Проходячи позаду ліврейних лакея, розсовує натовп біля матері, Наташа почула голос молодої людини, занадто голосним шепотом говорив про неї:
- Це Ростова, та сама ...
- Як схудла, а все таки хороша!
Вона чула, або їй здалося, що були згадані імена Курагина і Болконського. Втім, їй завжди це здавалося. Їй завжди здавалося, що все, дивлячись на неї, тільки й думають про те, що з нею сталося. Страждаючи і завмираючи в душі, як завжди в натовпі, Наташа йшла в своєму ліловому шовковому з чорним мереживом плаття так, як вміють ходити жінки, - тим спокійніше і величніше, ніж болючіше і соромніше у ній було на душі. Вона знала і не помилялася, що вона хороша, але це тепер не радувало її, як раніше. Навпаки, це мучило її найбільше в Останнім часомі особливо в цей яскравий, жаркий літній день в місті. «Ще неділю, ще тиждень, - говорила вона собі, згадуючи, як вона була тут тієї неділі, - і все те ж життя без життя, і все ті ж умови, в яких так легко було жити раніше. Хороша, молода, і я знаю, що тепер добра, перш я була погана, а тепер я добра, я знаю, - думала вона, - а так даром, ні для кого, проходять кращі роки ». Вона стала біля матері і перекинулася з близько стояли знайомими. Наташа за звичкою розглянула туалети дам, засудила tenue [манеру триматися] і непристойний спосіб хреститися рукою на малому просторі однієї близько стояла пані, знову з досадою подумала про те, що про неї судять, що і вона судить, і раптом, почувши звуки служби, жахнулася своєї гидоти, жахнулася того, що колишня чистота знову втрачена нею.
Благообразний, тихий дідок служив з тієї лагідної урочистістю, яка так величаво, заспокійливо діє на душі моляться. Царські двері зачинилися, повільно засунув завіса; таємничий тихий голос вимовив що то звідти. Незрозумілі для неї самої сльози стояли в грудях Наташі, і радісне і нудне почуття хвилювало її.
«Навчи мене, що мені робити, як мені виправитися назавжди, назавжди, як мені бути з моїм життям ... - думала вона.
Диякон вийшов на амвон, виправив, широко відставивши великий палець, довге волосся з під стихаря і, поклавши на грудях хрест, голосно і урочисто став читати слова молитви:
- «Миром господу помолимося».
«Світом, - все разом, незалежно від станів, без ворожнечі, а з'єднані братньою любов'ю - будемо молитися», - думала Наташа.
- За мир із неба і спасіння душ наших!
«За мир ангелів і душ всіх безтілесних істот, які живуть над нами», - молилася Наташа.
Коли молилися за воїнство, вона згадала брата і Денисова. Коли молилися за плаваючих і подорожуючих, вона згадала князя Андрія і молилася за нього, і молилася за те, щоб бог простив їй те зло, яке вона йому зробила. Коли молилися за люблячих нас, вона молилася про своїх домашніх, про батька, матері, Соні, в перший раз тепер розуміючи всю свою вину перед ними і відчуваючи всю силу своєї любові до них. Коли молилися про тих, хто ненавидить нас, вона придумала собі ворогів і ненавидять для того, щоб молитися за них. Вона зараховувала до ворогів кредиторів і всіх тих, які мали справу з її батьком, і всякий раз, при думці про ворогів і ненавидять, вона згадувала Анатоля, який зробив їй стільки зла, і хоча він не був ненавидить, вона радісно молилася за нього як за ворога. Тільки на молитві вона відчувала себе в силах ясно і спокійно згадувати і про князя Андрія, і про Анатолі, як про людей, до яких почуття її знищувалися в порівнянні з її почуттям страху і благоговіння до Бога. Коли молилися за царську прізвищеі за Синод, вона особливо низько вклонилась і хрестилася, кажучи собі, що, якщо вона не розуміє, вона не може сумніватися і все таки любить Синод і молиться за нього.
Закінчивши єктенію, диякон перехрестив навколо грудей орарь і вимовив:
- «Самі себе і життя наше Христу Богу віддамо».
«Самі себе богу зрадимо, - повторила в своїй душі Наташа. - Боже мій, передаю себе твоєї волі, - думала вона. - Нічого не хочу, не бажаю; навчи мене, що мені робити, куди використати свою волю! Так візьми ж мене, візьми мене! - з розчуленим нетерпінням в душі говорила Наташа, що не хрестячись, опустивши свої тонкі руки і ніби чекаючи, що ось ось невидима сила візьме її і позбавить від себе, від своїх жалю, бажань, докорів, надій і пороків.
Графиня кілька разів під час служби оглядалася на розчулене, з блискучими очима, обличчя своєї дочки і молилася Богу про те, щоб він допоміг їй.

Яке має тільки 2 різних натуральних дільника. Якщо сказати по-іншому, число pтоді буде простим, коли воно більше одиниці і може бути розділене лише на одиницю і на себе самого - p.

Натуральні числа, великі одиниці і числа, які не є простими, називають складовими числами. Т.ч., все натуральні числа діляться на 3 класу: одиниця (має 1 дільник), прості числа(Мають 2 дільника) і складені числа(Мають більше 2-х дільників).

початок п оследовательності простих чиселвиглядає так:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, …

Якщо уявити натуральні числа як твір простих, то це буде називатися розкладання на прості або факторизация числа.

Найбільше просте число, яке відоме.

Найбільше відоме просте число - це 2 57885161 - 1. Це число складається з 17 425 170 десяткових цифр і називається просте число Мерсенна(M 57885161).

Деякі властивості простих чисел.

Припустимо, p- просте, і pділить ab, тоді pділить aабо b.

кільце відрахувань Z nбуде називатися полем тільки в разі, якщо n- просте.

Характеристика всіх полів - це нуль або просте число.

коли p- просте, а a- натуральне, значить, a p -aможна поділити на p (мала теорема Ферма).

коли G- кінцева група, у якій порядок | G |ділять на p, Значить, у Gє елемент порядку p (теорема Коші).

коли G- кінцева група, і p n- найвища ступінь p, що ділить | G |, Значить, у Gє підгрупа порядку p n, Яка називається Сіловская підгрупа, крім того, число сіловскіх підгруп відповідає pk + 1для якогось цілого k(Теореми Силова).

натуральне p> 1буде простим лише в разі, якщо (P-1)! + 1можна подув на p (теорема Вільсона).

коли n> 1- натуральне, значить, є просте p: n< p < 2 n (постулат Бертрана).

Ряд чисел, які протилежні до простих, розходиться. Крім того, при.

Будь-яка арифметична прогресія типу a, a + q, a + 2 q, a + 3 q, ..., де a, q> 1- цілі взаємно прості числа, Містить нескінченне число простих чисел ( Теорема Діріхле про прості числа в арифметичній прогресії).

Будь-яке просте число, яке більше трійки, можна уявити як 6k + 1або 6k-1, де k- натуральне число. Виходячи з цього, коли різниця декількох послідовних простих чисел (при k> 1) Однакова, значить, вона точно ділиться на шість - наприклад: 251-257-263-269; 199-211-223; 20183-20201-20219 .

коли p> 3- просте число, значить, p 2 -1ділиться на 24 (Працює і на непарних чисел, які не діляться на три).

Теорема Гріна-Тао. є нескінченні арифметичні прогресії, Які складаються з простих чисел.

n k -1, де n> 2, k> 1. Іншими словами, число, яке слідує за простим, не може бути квадратом або більш високим ступенем з підставою, яке більше двох. Можна зробити висновок, що коли просте число представлено як 2 k -1, значить k- просте.

Жодне просте число не можна уявити як n 2k + 1 +1, де n> 1, k> 0. Іншими словами, число, яке передує простому, не може бути кубом або вищої непарної ступенем з підставою, яке більше одиниці.

Є многочлени, у яких безліч невід'ємних значень при позитивних значеннях змінних збігається з безліччю простих чисел. приклад:

Цей многочлен містить 26 змінних, має 25. Найнижчий ступінь для відомих многочленів представленого виду - п'ять при 42 змінних; найменше кількість змінних - десять при ступеня приблизно 1,6 · 10 45.

Дії з простими числами.

1. Твір простих чисел.

2. Різниця простих чисел.

3. Сума простих чисел.

4. Розподіл простих чисел.