Как да проверите дали едно число е просто. прости числа

просто числое естествено (цело положително) число, което се дели без остатък само на две естествени числа: само по себе си. С други думи, едно просто число има точно два естествени делителя: и самото число.

По дефиниция множеството от всички делители на просто число е двуелементно, т.е. е комплект.

Множеството от всички прости числа се обозначава със символа . Така, по силата на дефиницията на множеството от прости числа, можем да запишем: .

Последователността от прости числа изглежда така:

Основна теорема на аритметиката

Основна теорема на аритметикататвърди, че всяко естествено число, по-голямо от едно, може да бъде представено като произведение на прости числа и по уникален начин, до реда на факторите. По този начин простите числа са елементарните „градивни елементи“ на множеството естествени числа.

Разлагане на естествено число title="(!LANG:Предадено от QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют !} каноничен:

където е просто число и . Например, каноничното разширение на естествено число изглежда така: .

Представянето на естествено число като произведение на прости числа се нарича още разлагане на числа.

Свойства на простите числа

Сито на Ератостен

Един от най-известните алгоритми за търсене и разпознаване на прости числа е сито на Ератостен. Така че този алгоритъм е кръстен на гръцкия математик Ератостен от Кирена, който се смята за автор на алгоритъма.

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

Етап 1.Напишете в ред всички естествени числа от две до , т.е. .
Стъпка 2Задайте стойност на променлива, тоест стойност, равна на най-малкото просто число.
Стъпка 3Изтрийте в списъка всички числа от до кратни на , тоест числа: .
Стъпка 4Намерете първото незачеркнато число в списъка, по-голямо от , и присвоете стойността на това число на променливата.
Стъпка 5Повторете стъпки 3 и 4, докато се достигне числото.

Процесът на прилагане на алгоритъма ще изглежда така:

Всички останали незачеркнати числа в списъка в края на процеса на прилагане на алгоритъма ще бъдат набор от прости числа от до.

Хипотезата на Голдбах

Корица на книгата "Чичо Петрос и предположението Голдбах"

Въпреки факта, че простите числа се изучават от математиците от дълго време, днес много свързани проблеми остават нерешени. Един от най-известните нерешени проблеми е Предположението на Голдбах, който е формулиран по следния начин:

Вярно ли е, че всяко четно число, по-голямо от две, може да бъде представено като сбор от две прости числа (бинарна хипотеза на Голдбах)?
Вярно ли е, че всяко нечетно число, по-голямо от 5, може да бъде представено като сбор от три прости числа (тройната хипотеза на Голдбах)?

Трябва да се каже, че тройната хипотеза на Голдбах е частен случай на бинарната хипотеза на Голдбах или, както казват математиците, тройната хипотеза на Голдбах е по-слаба от бинарната хипотеза на Голдбах.

Предположението на Голдбах стана широко известно извън математическата общност през 2000 г. благодарение на рекламен маркетингов трик от издателските компании на Bloomsbury USA (САЩ) и Faber and Faber (Великобритания). Тези издателства, след като пуснаха книгата „Чичо Петрос и предположението на Голдбах“ („Чичо Петрос и предположението на Голдбах“), обещаха да изплатят награда от 1 милион щатски долара в рамките на 2 години от датата на публикуване на книгата на този, който доказва предположението на Голдбах. Понякога споменатата награда от издателите се бърка с наградите за решаване на проблемите с наградата на хилядолетието. Не се заблуждавайте, хипотезата на Голдбах не е посочена като предизвикателство на хилядолетието от Института на Клей, въпреки че е тясно свързана с хипотезата на Риманедно от предизвикателствата на хилядолетието.

Книгата „Прости числа. Дълъг път към безкрайността

Корица на книгата „Светът на математиката. Прости числа. Дълъг път към безкрайността

Освен това препоръчвам да прочетете завладяваща научно-популярна книга, анотацията към която гласи: „Търсенето на прости числа е един от най-парадоксалните проблеми в математиката. Учените се опитват да го решат от няколко хилядолетия, но придобивайки нови версии и хипотези, тази мистерия все още остава неразгадана. Появата на простите числа не е подчинена на никаква система: те възникват спонтанно в поредица от естествени числа, пренебрегвайки всички опити на математиците да идентифицират модели в тяхната последователност. Тази книга ще позволи на читателя да проследи еволюцията на научните идеи от древни времена до наши дни и да въведе най-любопитните теории за търсенето на прости числа.

Освен това ще цитирам началото на втора глава от тази книга: „Простите числа са една от важните теми, които ни връщат към самото начало на математиката, а след това, по пътя на нарастваща сложност, ни водят към изрязването ръба на съвременната наука. По този начин би било много полезно да се проследи увлекателната и сложна история на теорията на простите числа: как точно се е развила тя, как точно са събрани фактите и истините, които днес се считат за общоприети. В тази глава ще видим как поколения математици внимателно са изучавали естествените числа в търсене на правило, което предсказва появата на прости числа, правило, което в хода на търсенето става все по-неуловимо. Ще разгледаме и историческия контекст по-отблизо: в какви условия са работили математиците и до каква степен тяхната работа включва мистични и полурелигиозни практики, които изобщо не са подобни на научните методи, използвани в наше време. Въпреки това, бавно и трудно, почвата беше подготвена за новите възгледи, вдъхновили Ферма и Ойлер през 17-ти и 18-ти век.”

Простото число е естествено число, което се дели само на себе си и на единица.

Останалите числа се наричат съставни.

Прости естествени числа

Но не всички естествени числа са прости.

Прости естествени числа са само тези, които се делят само на себе си и на единица.

Примери за прости числа:

2; 3; 5; 7; 11; 13;...

Прости цели числа

От това следва, че само естествените числа са прости числа.

Това означава, че простите числа са задължително естествени.

Но всички естествени числа също са цели числа.

Следователно всички прости числа са цели числа.

Примери за прости числа:

2; 3; 5; 7; 11; 13; 17; 19; 23;...

Дори прости числа

Има само едно четно просто число и това са две.

Всички останали прости числа са нечетни.

Защо четно число, по-голямо от две, не може да бъде просто число?

Но тъй като всяко четно число, по-голямо от две, ще се дели само по себе си, не на едно, а на две, тоест такова число винаги ще има три делителя, а може и повече.

Превод

Свойствата на простите числа са изследвани за първи път от математиците на древна Гърция. Математиците от питагорейската школа (500 - 300 г. пр. н. е.) се интересуват преди всичко от мистичните и нумерологичните свойства на простите числа. Те бяха първите, които излязоха с идеи за перфектни и приятелски числа.

Съвършеното число има свои собствени делители, равни на себе си. Например, правилните делители на числото 6 са: 1, 2 и 3. 1 + 2 + 3 = 6. Делите на числото 28 са 1, 2, 4, 7 и 14. Освен това 1 + 2 + 4 + 7 + 14 = 28.

Числата се наричат приятелски, ако сборът от правилните делители на едно число е равен на друго и обратно – например 220 и 284. Можем да кажем, че едно съвършено число е приятелско на себе си.

До момента на появата на творбата на Евклид „Началата“ през 300 г. пр.н.е. Няколко важни факта за простите числа вече са доказани. В IX книга на Елементите Евклид доказва, че има безкраен брой прости числа. Между другото, това е един от първите примери за използване на доказателство чрез противоречие. Той също така доказва Основната теорема на аритметиката – всяко цяло число може да бъде представено по уникален начин като произведение на прости числа.

Той също така показа, че ако числото 2 n -1 е просто, тогава числото 2 n-1 * (2 n -1) ще бъде перфектно. Друг математик, Ойлер, през 1747 г. успява да покаже, че всички дори перфектни числа могат да бъдат записани в тази форма. И до днес не е известно дали съществуват нечетни перфектни числа.

През 200 г. пр.н.е. Гръцкият Ератостен измисли алгоритъм за намиране на прости числа, наречен Ситото на Ератостен.

И тогава имаше голям пробив в историята на изучаването на простите числа, свързани със Средновековието.

Следните открития са направени още в началото на 17 век от математика Ферма. Той доказа хипотезата на Алберт Жирар, че всяко просто число от формата 4n+1 може да бъде записано еднозначно като сбор от два квадрата, а също така формулира теорема, че всяко число може да бъде представено като сбор от четири квадрата.

Той разработи нов метод на факторизация за големи числа и го демонстрира на числото 2027651281 = 44021 × 46061. Той също така доказа малката теорема на Ферма: ако p е просто число, тогава a p = a по модул p ще бъде вярно за всяко цяло число a.

Това твърдение доказва половината от това, което беше известно като "китайската хипотеза" и датира от 2000 години по-рано: цяло число n е просто, ако и само ако 2n-2 се дели на n. Втората част на хипотезата се оказа невярна - например 2341 - 2 се дели на 341, въпреки че числото 341 е съставно: 341 = 31 × 11.

Малката теорема на Ферма беше основата за много други резултати в теорията на числата и методи за тестване дали числата са прости, много от които все още се използват днес.

Ферма си кореспондира много със своите съвременници, особено с монах на име Марин Мерсен. В едно от писмата си той предположи, че числата от вида 2 n + 1 винаги ще бъдат прости, ако n е степен на две. Той тества това за n = 1, 2, 4, 8 и 16 и беше сигурен, че когато n не е степен на две, числото не е непременно просто. Тези числа се наричат числа на Ферма и едва 100 години по-късно Ойлер показа, че следващото число, 232 + 1 = 4294967297, се дели на 641 и следователно не е просто.

Числата от вида 2 n - 1 също са били обект на изследване, тъй като е лесно да се покаже, че ако n е съставно, то самото число също е съставно. Тези числа се наричат числа на Мерсен, защото той активно ги изучава.

Но не всички числа от вида 2 n - 1, където n е просто, са прости. Например 2 11 - 1 = 2047 = 23 * 89. Това е открито за първи път през 1536г.

В продължение на много години числата от този вид дадоха на математиците най-големите известни прости числа. Че числото M 19 е доказано от Каталди през 1588 г. и в продължение на 200 години е най-голямото известно просто число, докато Ойлер не доказа, че M 31 също е просто число. Този рекорд се запази още сто години, а след това Лукас показа, че M 127 е просто (и това вече е число от 39 цифри), а след това изследванията продължиха с появата на компютрите.

През 1952 г. е доказано простотата на числата M 521 , M 607 , M 1279 , M 2203 и M 2281.

До 2005 г. бяха открити 42 прости числа на Мерсен. Най-големият от тях, M 25964951, се състои от 7816230 цифри.

Работата на Ойлер има огромно влияние върху теорията на числата, включително простите числа. Той разшири Малката теорема на Ферма и въведе φ-функцията. Разложи на множители 5-то число на Ферма 2 32 +1, намери 60 двойки приятелски числа и формулира (но не успя да докаже) квадратичния закон за реципрочността.

Той е първият, който въвежда методите на математическия анализ и развива аналитичната теория на числата. Той доказа, че не само хармоничният ред ∑ (1/n), но и серия от вида

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

Получава се от сбора на количествата, обратни на простите числа, също се разминава. Сборът от n члена на хармоничния ред нараства приблизително като log(n), докато вторият ред се отклонява по-бавно, като log[ log(n) ]. Това означава, че например сборът от реципрочните числа на всички прости числа, намерени до момента, ще даде само 4, въпреки че редът все още се разминава.

На пръв поглед изглежда, че простите числа са разпределени между цели числа доста произволно. Например, сред 100-те числа непосредствено преди 10000000 има 9 прости числа, а сред 100-те числа непосредствено след тази стойност има само 2. Но на големи сегменти, простите числа са разпределени сравнително равномерно. Лежандър и Гаус се занимават с тяхното разпространение. Веднъж Гаус казал на приятел, че във всеки свободен 15 минути той винаги брои броя на простите числа в следващите 1000 числа. До края на живота си той е преброил всички прости числа до 3 милиона. Лежандър и Гаус еднакво изчислиха, че за големи n плътността на простите числа е 1/log(n). Лежандър изчисли броя на простите числа между 1 и n като

π(n) = n/(log(n) - 1,08366)

И Гаус - като логаритмичен интеграл

π(n) = / 1/log(t) dt

С интервал на интегриране от 2 до n.

Твърдението за плътността на простите числа 1/log(n) е известно като теорема за простите числа. Те се опитваха да го докажат през целия 19 век и Чебишев и Риман постигнаха напредък. Те го свързват с хипотезата на Риман, недоказана досега хипотеза за разпределението на нулите на дзета функцията на Риман. Плътността на простите числа е доказана едновременно от Адамар и де ла Вале-Пусен през 1896 г.

В теорията на простите числа все още има много нерешени въпроси, някои от които са на много стотици години:

Хипотеза за прости числа близнаци - за безкраен брой двойки прости числа, които се различават едно от друго с 2
Предположението на Голдбах: всяко четно число, започващо от 4, може да бъде представено като сбор от две прости числа
Има ли безкраен брой прости числа от вида n 2 + 1?
винаги ли е възможно да се намери просто число между n 2 и (n + 1) 2 ? (фактът, че между n и 2n винаги има просто число, е доказано от Чебишев)
Има ли безкраен брой прости числа на Ферма? има ли прости числа на Ферма след 4-то?
има ли аритметична прогресия на последователни прости числа за дадена дължина? например за дължина 4: 251, 257, 263, 269. Максималната намерена дължина е 26 .
Има ли безкраен брой набори от три последователни прости числа в аритметична прогресия?
n 2 - n + 41 е просто число за 0 ≤ n ≤ 40. Има ли безкраен брой такива прости числа? Същият въпрос за формулата n 2 - 79 n + 1601. Тези числа са прости за 0 ≤ n ≤ 79.
Има ли безкраен брой прости числа от вида n# + 1? (n# е резултат от умножаването на всички прости числа, по-малки от n)
Има ли безкраен брой прости числа от вида n# -1?
Има ли безкраен брой прости числа от вида n! +1?
Има ли безкраен брой прости числа от вида n! - един?
ако p е просто, 2 p -1 винаги ли не включва сред факторите на квадратните прости числа
Последователността на Фибоначи съдържа ли безкраен брой прости числа?

Най-големите прости числа близнаци са 2003663613 × 2 195000 ± 1. Те се състоят от 58711 цифри и са открити през 2007 г.

Най-голямото факториално просто число (от формата n! ± 1) е 147855! - 1. Състои се от 142891 цифри и е намерен през 2002г.

Най-голямото първично просто число (число от вида n# ± 1) е 1098133# + 1.

Етикети: Добавяне на етикети

Простите числа са едно от най-интересните математически явления, което привлича вниманието на учени и обикновени граждани повече от две хилядолетия. Въпреки факта, че сега живеем в ерата на компютрите и най-модерните информационни програми, много мистерии на простите числа все още не са разгадани, има дори такива, до които учените не знаят как да подходят.

Простите числа са, както е известно от курса на елементарната аритметика, тези, които се делят без остатък само на единица и на себе си. Между другото, ако естествено число се дели, в допълнение към изброените по-горе, на друго число, тогава то се нарича съставно. Една от най-известните теореми гласи, че всяко съставно число може да бъде представено като единственото възможно произведение на прости числа.

Няколко интересни факта. Първо, единицата е уникална в смисъл, че всъщност не принадлежи нито на прости, нито на съставни числа. В същото време в научната общност все още е обичайно да се приписва на първата група, тъй като формално тя напълно отговаря на изискванията му.

Второ, единственото четно число, което се е промъкнало в групата на „простите числа“, е, разбира се, две. Всяко друго четно число просто не може да стигне до тук, тъй като по дефиниция, освен себе си и едно, то също се дели на две.

Простите числа, чийто списък, както бе споменато по-горе, може да започне с едно, са безкраен ред, толкова безкраен, колкото и поредицата от естествени числа. Въз основа на основната теорема на аритметиката може да се стигне до заключението, че простите числа никога не се прекъсват и никога не свършват, тъй като в противен случай поредицата от естествени числа неизбежно би била прекъсната.

Простите числа не се появяват на случаен принцип в естествения ред, както може да изглежда на пръв поглед. След като ги анализирате внимателно, веднага можете да забележите няколко функции, най-любопитните от които са свързани с така наречените числа „близнаци“. Наричат се така, защото по някакъв неразбираем начин се озоваха един до друг, разделени само с четен разделител (пет и седем, седемнадесет и деветнадесет).

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

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

Превод