Просто число: Разлика между версии
Изтрито е съдържание Добавено е съдържание
Редакция без резюме |
Termininja (беседа | приноси) мРедакция без резюме |
||
Ред 1:
В [[математика]]та '''просто число''' се нарича всяко [[естествено число]], по-голямо от [[1 (число)|1]], което има точно два естествени [[делител]]я — 1 и самото себе си. Естествените числа, по-големи от едно, които не са прости, се наричат [[съставно число|съставни]]. Числата [[0 (число)|нула]] и едно не са нито прости, нито съставни. Простите числа са един от основните обекти, които се изучават от [[теория на числата|теорията на числата]].
[[2 (число) | 2]], [[3 (число) | 3]], [[5 (число) | 5]], [[7 (число) | 7]], [[11 (число) | 11]], [[13 (число) | 13]], [[17 (число) | 17]], [[19 (число) | 19]], [[23 (число) | 23]], [[29 (число) | 29]], [[31 (число) | 31]], [[37 (число) | 37]], [[41 (число) | 41]], [[43 (число) | 43]], [[47 (число) | 47]], [[53 (число) | 53]], [[59 (число) | 59]], [[61 (число) | 61]], [[67 (число) | 67]], [[71 (число) | 71]], [[73 (число) | 73]], [[79 (число) | 79]], [[83 (число) | 83]], [[89 (число) | 89]], [[97 (число) | 97]], [[101 (число) | 101]], [[103 (число) | 103]], [[107 (число) | 107]], [[109 (число) | 109]], [[113 (число) | 113]],
Ред 10:
== Представяне на естествените числа като произведение на прости ==
[[основна теорема на аритметиката|Основната теорема на аритметиката]] гласи, че всяко цяло число, по-голямо от 1, може да се представи по единствен начин (с точност до реда на множителите) като произведение на прости числа. Например
: <math>23244 = 2^2 \times 3 \times 13 \times 149 \,</math>
Ред 30:
[[решето на Ератостен|Решетото на Ератостен]] е прост начин, а [[решето на Аткин|решетото на Аткин]] е бърз начин да се намери списъкът на всички прости числа,по-малки от някое отнапред зададено число.
На практика обаче по-често се налага да се провери дали дадено число е просто, отколкото да се намери списък с прости числа. Често дори е достатъчно да се знае отговорът на горния въпрос с достатъчно голяма [[вероятност]]. Възможно е бързо да се провери дали дадено голямо число (например до хиляда цифри) е просто, използвайки вероятностни [[тест за простота|тестове]].
Един начин за установяване дали едно число е просто е, като се провери дали се дели на някое от простите числа, по-малки от квадратния му корен. Ако не се дели на нито едно от тях, то е просто. Това е най-елементарният известен тест, но той не е практичен за големи числа, тъй като броят на възможните делители нараства експоненциално, когато броят на цифрите на числото се увеличава.
Ред 38:
== Някои свойства на простите числа ==
* Ако ''p'' е просто и ''p'' дели произведението ''ab'' , където ''a'' и ''b'' са цели, то ''p'' дели ''a'' или ''p'' дели ''b''. Това твърдение е доказано от Евклид и е известно като ''лема на Евклид''. Използва се за някои от доказателствата на единствеността на разлагане на прости множители.
:Забележка: В сила е нещо повече. Нека за едно естествено число ''p>1'' и за всеки две цели числа ''a'' и ''b'' е вярно, че ако ''p'' дели произведението ''ab'' , то ''p'' дели ''a'' или ''p'' дели ''b''. В някои изложения на елементарната аритметика това свойство се използва за дефиниция на понятието просто число, а фактът, че простите числа имат точно два делителя, се доказва впоследствие.
* Ако ''p'' е просто и ''a'' е произволно цяло число, то ''a''<sup>''p''</sup> − ''a'' се дели на ''p'' ([[малка теорема на Ферма]]).
* Едно цяло ''p'' > 1 е просто тогава и само тогава, когато [[факториел]]ът (''p'' - 1)! + 1 се дели на ''p'' ([[теорема на Уилсън]]). Обратно, едно цяло ''n'' > 4 е съставно тогава и само тогава, когато (''n'' - 1)! се дели на ''n''.
* Ако ''n'' е положително цяло число, по-голямо от 1, то винаги има просто число ''p'', за което ''n'' < ''p'' < 2''n'' ([[постулат на Бертран]]).
* Сумата от реципрочните на всички прости е разходящ [[ред]]. ([[Доказателство, че сумата от реципрочните на всички прости е разходяща| доказателство]]). По-точно, ако със ''S''(''x'') означим сумата от реципрочните на всички прости числа ''p'', за които ''p'' ≤ ''x'', то ''S''(''x'') = Θ(ln ln ''x'') за ''x'' → ∞.
* За всяко просто число ''p'' > 2, съществува естествено число ''n'' такова, че ''p'' = 4''n'' ± 1.
* За всяко просто число ''p'' > 3, съществува естествено число ''n'' такова, че ''p'' = 6''n'' ± 1.
Ред 57:
* [[Хипотеза на Голдбах]]: Всяко четно число, по-голямо от 2, може да се представи като сума на две прости числа.
Малко по-слабото твърдение
* [[Хипотеза за простите близнаци]]: Има безбройно много прости числа близнаци, тоест двойки от прости числа с разлика 2, като например 5 и 7 или 11 и 13.
<!--* [[Polignac's conjecture]]: For every integer n, there are infinitely many pairs of consecutive primes which differ by 2''n''. (When ''n''=1 this is the [[twin prime conjecture]].)-->
Ред 68:
== Най-голямото известно просто число ==
Най-голямото известно просто число към ноември 2008 г.
съдържа повече от 13 млн. знака. Това е 46-тото известно просто [[число на Мерсен]] M<sub>32582657</sub>. Списание "Таймс" поставя откриването му на 29-то място в Класацията си на най-големите открития на 2008 г. <ref>[http://www.time.com/time/specials/packages/article/0,28804,1852747_1854195_1854157,00.html Класацията на сп. Таймс]</ref>
След появата на компютрите почти всички намерени най-големи прости числа са били мерсенови числа. Това е така, защото съществува изключително бърз алгоритъм за проверка на числа от този тип. Най-голямото известно просто число, което ''не е'' мерсеново число, е 27653 × 2<sup>9167433</sup> + 1 (2 759 677 цифри). То е шестото най-голямо просто число. <!-- It was found by the [[Seventeen or Bust]] project and it brings them one step closer to solving the [[Sierpinski problem]].
Some of the largest primes not known to have any particular form (that is, no simple formula such as that of Mersenne primes) have been found by taking a piece of semi-random binary data, converting it to a number <var>n</var>, multiplying it by 256<sup><var>k</var></sup> for some positive integer <var>k</var>, and searching for possible primes within the interval [256<sup>''k''</sup>''n'' + 1, 256<sup>''k''</sup>(''n'' + 1) в€’ 1].
In fact, as a [[publicity stunt]] against the [[Digital Millennium Copyright Act]] and other [[WIPO Copyright Treaty]] implementations, some people have applied this to various forms of [[DeCSS]] code, creating the set of [[illegal prime]] numbers. Such numbers, when converted to binary and executed as a [[computer program]], perform acts encumbered by applicable law in one or more jurisdictions. -->
| |||