прости числа

Прости числа са естествените числа >1, които не могат да се представят като произведение с числа по-малки от тях. На графиката е представено разпределението на прости числа в посочения интервал.

С прости числа е свързана основната теорема на аритметиката: всяко естествено число n > 1 се представя еднозначно като произведение от прости числа с точност до реда на множителите.

Характерни свойство на простите числа:

С изключение на числата 2 и 5 последната цифра може да бъде само 1, 3, 7, 9. Правено е изследване с прости числа от даден интервал, което по статистически път извежда твърдението, че 1-цата е по-често срещаната последна цифра. Тези и следващите твърдения се отнасят за 10-ична бройна система, а 2 и 5 са делители на основата. Числата 2 и 5 са прости числа, но всички цели числа (с две и повече цифри) с последна цифра 2 или 5 са съставни числа.

За всяко просто число p > 2, съществува естествено число n такова, че p = 4n ± 1. Пример: 31 = 4*8 - 1.

Съществуват безброй много двойки съседни прости, такива че (p,p+2) са едновременно прости числа. Пример: 17 и 19.

Ако две числа са прости, те са взаимно прости числа, обратното твърдение не е вярно. Пример: 3 и 5 са прости и взаимно прости, но 4 и 9 са взаимно прости (нямат общ делител), но и двете са съставни.

За всяко естествено число n>1 съществува просто число p, за което n < p < 2n - постулат на Бертран. Пример: в затворения интервал [4..2*] има две прости числа 5 и 7.

Ако p е просто число и p дели произведението на двойката естествени числа a,b, то p дели a или дели b - лема на Евклид. Пример: p = 3 дели произведението 48 = 6х8.

Всяко четно число n>2 може да се представи като сума на две прости числа - хипотеза на Голдбах. Пример: 16 = 3+13 = 5 + 11

Естественото число p+1 е просто тогава и само тогава, когато сумата (p-1)! + 1 се дели на p+1 - теорема на Уилсън. Пример р = 6; (р-1)! + 1 = 121 = 7*103

Всяко нечетно просто p е делител на сумата: (2^(p-1) - 1) - малка теорема на Ферма. Пример: 7 е делител 2^(7-1)-1 = 64 - 1 = 9*7

Всяко нечетно число, по-голямо от 7, може да се представи като сума на три нечетни прости числа.

Съществуват хипотези, които все още чакат своето доказателство. Част от тях са:

Предположение на de Polignac: всяко четно число може да представено като разлика от две прости числа по безкрайно много начини. Ако то е вярно вземайки разликата 2, се предполага, че има безброй много прости числа близнаци. Примери:

8 = 19 - 11

10 = 23 - 13

12 = 23 - 11

14 = 19 - 5

Предположение на Levy: всяко нечетно число по-голямо от 5 може да бъде представено като сума p + 2*q, където p и q са прости. Примери:

13 = 2*3 + 7 = 2*5 + 3

15 = 2*2 + 11 = 2*5 + 5

17 = 2*7 + 3 = 2*5 + 7

19 = 2*7 + 5 = 2*3 + 13

За всяко просто p и естествено a, то сумата a^p - a се дели на p. Примери:

a = 4, p = 3 : 4^3 - 4 = 64 - 4 : 60 се дели без остатък на 3;

a = 6, p = 2 : 6^2 - 6 = 36 - 6 : 30 се дели без остатък на 2;

a = 9, p = 3 : 9^3 - 9 = 729 - 9 : 720 се дели без остатък на 9;

Често срещани задачи, свързани с прости числа:

проверка за просто число и дискутирания проблем за честота на срещане на последната цифра в простите числа; признаци за делимост - признак на делимост е правилото което позволява бързо да се определи дали дадено число се дели на друго, без да се извършва фактически операцията. Обикновено се основава на математически действия с част от цифрите на делимото.

намиране на всички прости числа в даден интервал - сито на Ератостен и свързаната задача намиране на брой прости числа в интервал;

делимост на естествени числа;

NP-задачи: разлагане на прости делители, факторизация (integer factorization problem);

прости числа близнаци;

най-близкото просто;

най-голям общ делител - алгоритъм на Евклид, теорема на Безу;

брой и вид прости делители;

сума на прости делители;

разбиване на суми;

разбиване на суми като събираемите са само прости числа;

сума от три прости числа;

Пример за елементи на числова редица с елементи прости числа чиито цифри са също прости числа са: 53, 73, 223, 227.

Част от представените прости числа имат сходен алгоритъм на търсене:

великодушни прости числа - при разбиване на числото на две групи от последователни негови цифри сумата им да е също просто число: 8009 като 8+9 = 17; 80+9 = 89; 800+9=809;

вълнообразни прости числа - с променлива (по стойност) последователност от цифри, в които всеки две съседни цифри a,b са различни по стойност и имат различна по знак стойност на разликата a-b: ...151, 163, 173...

просто Мерсеново число - просто число представено с формулата: a(n) = 2^p - 1, където p е също просто число: 3 , 7 , 31...

нестрого прости числа - по-малки от средната стойност на предходното и следващото просто число: 3, 7, 13...

пермутационно прости числа - при промяна наредбата на цифрите им отново са прости числа: 13 и 31;

прости омразни числа - изпълняват едновременно две условия: да са прости и в двоичния си запис да имат нечетен брой 1-ци: 11 е просто число, в двоична бройна система е 1011 с 3 броя 1-ци.

прости числа emirp - прости числа, които при огледално подреждане на същите цифри също са прости числа: 17 и всички палиндромни прости числа.

прости числа Lucasian - изпълняват изискането: n == 3 (mod 4) за 2*n+1 също просто число: 3, 11, 23, 83, 131, 179...

прости числа Pierpont - могат да се представят с формулата a(n)= 2^t*3^u + 1, където t и u са цели числа и не непременно различни: 2, 3, 5, 7, 13, 17, 19, 37......

прости числа Sexy - са съседни прости числа с разлика 6: n, n+6, названието е игра на думи: 5, 7, 11, 13, 17, 23, 31...

прости числа Sophie Germain - естествени числа, за които n и 2*n+1 са едновременно прости числа: 2, 3, 5, 11, 23, 29, 41....

прости числа Wagstaff - естествени числа, за които n и (2^n + 1)/3 са едновременно прости числа: 3, 5, 7, 11, 13, 17, 19, 23....

прости числа братовчеди - съседни прости числа с разлика 4: p, p+4, такива са: 3, 7, 13, 19, 37, 43, 67, 79, 97....

прости числа палиндроми - отговарят едновременно на две условия: да са прости и да са палиндромни числа: 2, 3, 5, 7, 11, 101, 131, 151, 191...

сигурно прости числа - естествени числа, за които p и (p-1)/2 са едновременно прости числа: 5 - (5-1)/2 = 3.

прости числа Primeval - просто число, представящо най-големия брой прости числа, които могат да се получат с част или всички цифри на дадено просто числа без значение реда на цифрите: 37 - 3, 7, 73.

числа на Kynea - прости числа, могат да бъдат представени с формулите a(n) = (2^n + 1)^2 - 2, a(n) = 4^n + 2^(n+1) - 1. Описанието на числата, представени в двоична бройна система, би било: 1, следвани от n-1 броя 0-ли, следвани от n+1 броя 1-ци. Пример: 79 = 4^3 + 2^(3+1) - 1 = 64 + 16 - 1 = 1 00 1111.

Разгледайте други основни типове примерни задачи, за чието решение се използват числови редици. Прочетете допълнителен материал за: спирала на Ulam, прости числа - сито на Ератостен.