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

В статията се разглеждат понятията прости и съставни числа. Дефинициите на такива числа са дадени с примери. Предоставяме доказателства, че количеството прости числанеограничен и запишете в таблицата на простите числа, като използвате метода на Ератостен. Ще бъдат дадени доказателства, за да се определи дали едно число е просто или съставно.

Yandex.RTB R-A-339285-1

Прости и съставни числа – дефиниции и примери

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

Определение 1

Простите числа са цели числа, които са по-големи от едно и имат два положителни делителя, тоест себе си и 1.

Определение 2

Съставните числа са цели числа, които са по-големи от едно и имат поне три положителни делителя.

Едното не е нито просто, нито съставно число. То има само един положителен делител, така че е различно от всички други положителни числа. Всички положителни числа се наричат ​​естествени числа, тоест използвани при броене.

Определение 3

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

Определение 4

Съставно числое естествено число, което има повече от два положителни делителя.

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

Определение 5

Естествените числа, които не са прости, се наричат ​​съставни числа.

Прости числа: 2, 3, 11, 17, 131, 523. Те се делят само на себе си и на 1. Съставни числа: 6, 63, 121, 6697. Тоест числото 6 може да се разложи на 2 и 3, а 63 на 1, 3, 7, 9, 21, 63 и 121 на 11, 11, тоест неговите делители ще бъдат 1, 11, 121. Числото 6697 се разлага на 37 и 181. Обърнете внимание, че понятията прости числа и взаимно прости числа са различни понятия.

За да улесните използването на прости числа, трябва да използвате таблица:

Таблица за всички съществуващи естествени числа е нереалистична, тъй като има безкраен брой от тях. Когато числата достигнат размери от 10000 или 1000000000, тогава трябва да помислите за използването на ситото на Ератостен.

Нека разгледаме теоремата, която обяснява последното твърдение.

Теорема 1

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

Доказателство 1

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

Да приемем, че b – съставно число. От тук имаме, че има делител за b, който е различен както от 1, така и от b. Такъв делител се означава като b 1. Необходимо е условие 1< b 1 < b беше завършен.

От условието става ясно, че a е разделено на b, b е разделено на b 1, което означава, че концепцията за делимост се изразява по следния начин: a = b qи b = b 1 · q 1 , от където a = b 1 · (q 1 · q) , където q и р 1са цели числа. Съгласно правилото за умножение на цели числа имаме, че произведението на цели числа е цяло число с равенство от вида a = b 1 · (q 1 · q) . Вижда се, че b 1 е делителя на числото a. Неравенство 1< b 1 < b Несъответства, тъй като откриваме, че b е най-малкият положителен и различен от 1 делител на a.

Теорема 2

Има безкраен брой прости числа.

Доказателство 2

Предполага се, че вземаме краен брой естествени числа 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 , откриваме, че ще се дели на pn + 1. Обърнете внимание, че изразът p n + 1 разделянето на числото p е равно на сумата p 1, p 2, ..., p n + 1. Получаваме, че изразът p n + 1 Вторият член на тази сума, който е равен на 1, трябва да се раздели, но това е невъзможно.

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

Тъй като има много прости числа, таблиците са ограничени до числата 100, 1000, 10000 и т.н.

Когато съставяте таблица с прости числа, трябва да имате предвид, че такава задача изисква последователна проверка на числата, като се започне от 2 до 100. Ако няма делител, той се записва в таблицата, ако е съставен, тогава не се въвежда в таблицата.

Нека го разгледаме стъпка по стъпка.

Ако започнете с числото 2, то има само 2 делителя: 2 и 1, което означава, че може да бъде въведено в таблицата. Същото с числото 3. Числото 4 е съставно; трябва да се разложи на 2 и 2. Числото 5 е просто, което означава, че може да бъде записано в таблицата. Направете това до числото 100.

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

Методът с помощта на ситото на Ератостен се счита за най-удобен. Нека разгледаме примерните таблици по-долу. Като начало се записват числата 2, 3, 4, ..., 50.

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

Преминаваме към задраскване на числа, кратни на 5. Получаваме:

Задраскайте числата, кратни на 7, 11. В крайна сметка таблицата изглежда така

Да преминем към формулировката на теоремата.

Теорема 3

Най-малкият положителен и различен от 1 делител на основното число a не превишава a, където a е аритметичният корен на даденото число.

Доказателство 3

Трябва да се посочи b най-малък делителсъставно число а. Има цяло число q, където a = b · q, и имаме, че b ≤ q. Неравностите на формата са недопустими b > q,защото условието е нарушено. Двете страни на неравенството b ≤ q трябва да се умножат по всяко положително число b, което не е равно на 1. Получаваме, че b · b ≤ b · q, където b 2 ≤ a и b ≤ a.

От доказаната теорема става ясно, че зачеркването на числа в таблицата води до факта, че е необходимо да се започне с число, което е равно на b 2 и удовлетворява неравенството b 2 ≤ a. Тоест, ако задраскате числа, кратни на 2, тогава процесът започва с 4, а кратни на 3 с 9 и така до 100.

Съставянето на такава таблица с помощта на теоремата на Ератостен предполага, че когато всички съставни числа бъдат задраскани, ще останат прости числа, които не надвишават n. В примера, където n = 50, имаме, че n = 50. От това получаваме, че ситото на Ератостен отсява всички съставни числа, чиято стойност не е по-голяма от стойността на корен от 50. Търсенето на номера става чрез задраскване.

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

Пример 1

Докажете, че числото 898989898989898989 е съставно.

Решение

Сборът от цифрите на дадено число е 9 8 + 9 9 = 9 17. Това означава, че числото 9 · 17 се дели на 9 въз основа на теста за делимост на 9. От това следва, че тя е съставна.

Такива знаци не са в състояние да докажат простотата на числото. Ако е необходима проверка, трябва да се предприемат други действия. Най-подходящият начин е да изброите числа. По време на процеса можете да намерите прости и съставни числа. Тоест числата не трябва да надвишават a по стойност. Тоест числото a трябва да бъде разложено на прости множители. ако това е изпълнено, тогава числото a може да се счита за просто.

Пример 2

Определете съставното или просто число 11723.

Решение

Сега трябва да намерите всички делители на числото 11723. Трябва да се оцени 11723 .

От тук виждаме, че 11723< 200 , то 200 2 = 40 000 и 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .

За още точна оценканомер 11723, трябва да напишете израза 108 2 = 11 664 и 109 2 = 11 881 , Че 108 2 < 11 723 < 109 2 . От това следва, че 11723г< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

Когато разширяваме, откриваме, че 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 са прости числа. всичко този процесможе да се изобрази като разделение от колона. Тоест, разделете 11723 на 19. Числото 19 е един от неговите множители, тъй като получаваме деление без остатък. Нека представим разделението като колона:

От това следва, че 11723 е съставно число, защото освен себе си и 1 има делител на 19.

Отговор: 11723 е съставно число.

Ако забележите грешка в текста, моля, маркирайте я и натиснете Ctrl+Enter

Числата са различни: естествени, рационални, рационални, цели и дробни, положителни и отрицателни, сложни и прости, нечетни и четни, реални и т.н. От тази статия можете да разберете какво представляват простите числа.

Кои числа се наричат ​​„прости“ на английски?

Много често учениците не знаят как да отговорят на един от най-простите на пръв поглед въпроси в математиката за това какво е просто число. Те често бъркат простите числа с естествените числа (т.е. числата, които хората използват при броене на предмети, докато в някои източници те започват с нула, а в други с единица). Но това са напълно две различни концепции. Простите числа са естествени числа, тоест цели числа и положителни числа, които по-голямо от еднои които имат само 2 естествени делителя. Освен това единият от тези делители е даденото число, а вторият е едно. Например, три е просто число, защото не може да бъде разделено без остатък на друго число, различно от себе си и едно.

Съставни числа

Обратното на простите числа са съставните числа. Те също са естествени, също по-големи от един, но имат не две, а голямо количестворазделители. Така например числата 4, 6, 8, 9 и т.н. са естествени, съставни, но не и прости числа. Както можете да видите, това са предимно четни числа, но не всички. Но „две“ е четно число и „първото число“ в поредица от прости числа.

Последователност

За да конструирате поредица от прости числа, е необходимо да изберете от всички естествени числа, като вземете предвид тяхната дефиниция, тоест трябва да действате от противоречие. Необходимо е всяко от положителните естествени числа да се изследва дали има повече от два делителя. Нека се опитаме да изградим редица (последователност), която се състои от прости числа. Списъкът започва с две, следвани от три, тъй като се дели само на себе си и на едно. Помислете за числото четири. Има ли делители, различни от четири и едно? Да, това число е 2. Така че четири не е просто число. Пет също е просто (не се дели на друго число, освен на 1 и 5), но шест се дели. И като цяло, ако проследите всички четни числа, ще забележите, че освен "две", нито едно от тях не е просто. От това заключаваме, че четните числа, с изключение на две, не са прости. Друго откритие: всички числа, които се делят на три, с изключение на самата тройка, независимо дали са четни или нечетни, също не са прости (6, 9, 12, 15, 18, 21, 24, 27 и т.н.). Същото важи и за числата, които се делят на пет и седем. Цялото им множество също не е просто. Нека да обобщим. И така, към простите едноцифрени числаВсички нечетни числа са включени с изключение на едно и девет, а дори „две“ са четни числа. Самите десетки (10, 20,... 40 и т.н.) не са прости. Двуцифрените, трицифрените и т.н. прости числа могат да бъдат определени въз основа на горните принципи: ако нямат делители, различни от себе си и единица.

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

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

Простите числа са „градивните елементи“ на естествените числа

В аритметиката има една теорема, наречена фундаментална теорема. Според него всяко естествено число, с изключение на едно, може да бъде представено като произведение, чиито множители са прости числа, а редът на множителите е уникален, което означава, че методът на представяне също е уникален. Нарича се разлагане на естествено число на прости множители. Има и друго име за този процес - факторизация на числата. Въз основа на това простите числа могат да бъдат наречени „ строителен материал”, „блокове” ​​за построяване на естествени числа.

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

Много учени от различни времена се опитват да намерят някои принципи (системи) за намиране на списък от прости числа. Науката познава системи, наречени сито на Аткин, сито на Сундартам и сито на Ератостен. Те обаче не дават значими резултати и за намиране на прости числа използваме проста проверка. Математиците също създават алгоритми. Те обикновено се наричат ​​тестове за първичност. Например, има тест, разработен от Рабин и Милър. Използва се от криптографи. Съществува и тестът Kayal-Agrawal-Sasquena. Въпреки достатъчната точност обаче е много трудно да се изчисли, което намалява практическото му значение.

Наборът от прости числа има ли ограничение?

Древногръцкият учен Евклид пише в книгата си „Елементи“, че множеството от прости числа е безкрайно. Той каза следното: „Нека си представим за момент, че простите числа имат ограничение. След това нека ги умножим един с друг и добавим едно към произведението. Числото, получено в резултат на тези прости действия, не може да бъде разделено на нито една от серията прости числа, тъй като остатъкът винаги ще бъде единица. Това означава, че има друго число, което все още не е включено в списъка с прости числа. Следователно нашето предположение не е вярно и това множество не може да има граница. Освен доказателството на Евклид, има по-модерна формула, дадена от швейцарския математик от осемнадесети век Леонхард Ойлер. Съгласно него сумата, реципрочна на сумата от първите n числа, нараства неограничено с нарастване на числото n. А ето и формулата на теоремата относно разпределението на простите числа: (n) расте като n/ln (n).

Кое е най-голямото просто число?

Същият Леонард Ойлер успя да намери най-голямото просто число на своето време. Това е 2 31 - 1 = 2147483647. До 2013 г. обаче беше изчислено друго най-точно най-голямо в списъка с прости числа - 2 57885161 - 1. Нарича се числото на Мерсен. Съдържа около 17 милиона десетични цифри. Както можете да видите, числото, открито от учен от осемнадесети век, е няколко пъти по-малко от това. Трябваше да е така, защото Ойлер извърши това изчисление ръчно, но нашият съвременник вероятно е бил подпомогнат от Изчислителна машина. Освен това това число е получено в Математическия факултет на един от американските отдели. Числата, кръстени на този учен, преминават теста за простота на Luc-Lemaire. Науката обаче не иска да спре дотук. Electronic Frontier Foundation, която е основана през 1990 г. в Съединените американски щати (EFF), предложи парична награда за намиране на големи прости числа. И ако до 2013 г. наградата се присъждаше на тези учени, които биха ги намерили измежду 1 и 10 милиона десетични числа, то днес тази цифра е достигнала от 100 милиона до 1 милиард. Наградите варират от 150 до 250 хиляди щатски долара.

Имена на специални прости числа

Тези числа, които са открити благодарение на алгоритми, създадени от определени учени и преминали теста за простота, се наричат ​​специални. Ето някои от тях:

1. Мерсен.

4. Кълън.

6. Mills et al.

Простотата на тези числа, кръстени на горните учени, се установява с помощта на следните тестове:

1. Люк-Льометр.

2. Пепина.

3. Ризел.

4. Billhart – Lemaire – Selfridge и др.

Съвременната наука не спира дотук и вероятно в близко бъдеще светът ще научи имената на тези, които са успели да спечелят наградата от $250 000, като са намерили най-голямото просто число.

Задача 2.30
Даден е едномерен масив A, състоящ се от естествени числа. Покажете броя на простите числа в масива.

Първо, нека ви напомня какво представляват простите числа.

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

Как да определим просто число в Pascal

Алгоритъм за решение с подробен анализЩе го дам на Паскал. Можете да видите решението в примерната програма на C++.

ВАЖНО!
Това е мястото, където много хора могат да сбъркат. Дефиницията казва, че едно просто число има гладкадве различниразделител Следователно числото 1 не е просто (също не е просто, тъй като нулата може да бъде разделена на произволно число).

Ще проверим дали едно число е просто с помощта на , което ще създадем сами. Тази функция ще върне TRUE, ако числото е просто.

Във функцията първо ще проверим дали числото е по-малко от две. Ако е така, то вече не е просто число. Ако числото е 2 или 3, то очевидно е просто и не са необходими допълнителни проверки.

Но ако числото N е повече от три, тогава в този случай ще преминем през всички възможни делители, започвайки от 2 до (N-1). Ако числото N се дели на някакъв делител без остатък, то също не е просто число. В този случай прекъсваме цикъла (защото няма смисъл да проверяваме допълнително) и функцията връща FALSE.

Няма смисъл да се проверява дали едно число се дели само на себе си (затова цикълът продължава само до N-1).

Тук няма да представям самата функция - вижте я в примерните програми.

Решаване на задача 2.30 в Pascal mytask; //************************************************ *************** //КОНСТАНТИ //******************************** ********* *********************************** БРОЙ = 100; //Брой елементи в масива //**************************************** ********** *********************** // ФУНКЦИИ И ПРОЦЕДУРИ //********** *********** *************************************** ** //***** ***************************************** * ******** // Проверява дали числото е просто // INPUT: N - число // OUTPUT: TRUE - числото N е просто, FALSE - не е просто //********** **************************************** **** IsPrimeNumber(N: WORD) : ; var i: ; начало := ВЯРНО;

N от 0..3: начало N Изход;край; край; i:= 2 to (N-1) do if (N i) = 0 then //Не е просто число begin Result:= FALSE; ; използване на пространство от имена std; //************************************************ *************** //КОНСТАНТИ //******************************** ********* *********************************** const int COUNT = 100; //Брой елементи в масива //**************************************** ********** *********************** // ФУНКЦИИ И ПРОЦЕДУРИ //********** *********** *************************************** ** //***** ***************************************** * ******** // Проверява дали числото е просто // INPUT: N - число // OUTPUT: TRUE - числото N е просто, FALSE - не е просто //********** **************************************** **** bool IsPrimeNumber(int N) ( bool Res = true; switch (N) ( case 0: Res = false; break; case 1: Res = false; break; case 2: Res = true; break; case 3: Res = true; break; default: for (int i = 2; i

Отговорът на Иля е правилен, но не много подробен. През 18 век, между другото, единицата все още се смяташе за просто число. Например такива велики математици като Ойлер и Голдбах. Голдбах е автор на един от седемте проблема на хилядолетието – хипотезата на Голдбах. Оригиналната формулировка гласи, че всяко четно число може да бъде представено като сбор от две прости числа. Освен това първоначално 1 беше взето предвид като просто число и виждаме това: 2 = 1+1. Това най-малък пример, удовлетворяващи първоначалната формулировка на хипотезата. По-късно беше коригирано и формулировката стана модерен вид: „всяко четно число, започващо с 4, може да бъде представено като сбор от две прости числа.“

Нека си припомним определението. Простото число е естествено число p, което има само 2 различни естествени делителя: самото p и 1. Следствие от определението: простото число p има само един прост делител - самото p.

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

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

С това съображение не е трудно да се открият аналози на прости числа в други алгебрични структури. Да предположим, че имаме мултипликативна група, образувана от степени на 2, като се започне от 1: 2, 4, 8, 16, ... и т.н. 2 действа като формиращ елемент тук. Просто число в тази група е число, по-голямо от най-малкия елемент и делимо само на себе си и на най-малкия елемент. В нашата група само 4 имат такива имоти. В нашата група вече няма прости числа.

Ако 2 също беше просто число в нашата група, тогава вижте първия параграф - отново ще се окаже, че само 2 е просто число.

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

Навигация в страницата.

Прости и съставни числа – дефиниции и примери

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

Определение.

прости числаса цели числа, големи единици, които имат само два положителни делителя, а именно себе си и 1.

Определение.

Съставни числаса цели числа, големи, които имат поне три положителни делителя.

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

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

Определение.

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

Определение.

Съставни числаса естествени числа, които имат повече от два положителни делителя.

Имайте предвид, че всяко положително цяло число, по-голямо от едно, е или просто, или съставно число. С други думи, няма нито едно цяло число, което да не е нито просто, нито съставно. Това следва от свойството за делимост, което гласи, че числата 1 и a винаги са делители на всяко цяло число a.

Въз основа на информацията в предходния параграф, можем да дадем следната дефиниция на съставните числа.

Определение.

Наричат ​​се естествени числа, които не са прости композитен.

Да дадем примери за прости и съставни числа.

Примерите за съставни числа включват 6, 63, 121 и 6697. Това твърдение също се нуждае от пояснение. Числото 6, в допълнение към положителните делители 1 и 6, също има делители 2 и 3, тъй като 6 = 2 3, следователно 6 е наистина съставно число. Положителните фактори на 63 са числата 1, 3, 7, 9, 21 и 63. Числото 121 е равно на произведението 11·11, така че неговите положителни делители са 1, 11 и 121. А числото 6697 е съставно, тъй като негови положителни делители, освен 1 и 6697, са още числата 37 и 181.

В заключение на тази точка бих искал също да обърна внимание на факта, че простите числа и взаимнопростите числа далеч не са едно и също нещо.

Таблица с прости числа

Простите числа, за удобство на по-нататъшното им използване, се записват в таблица, наречена таблица на простите числа. По-долу е таблица с прости числадо 1000.

Възниква логичен въпрос: „Защо попълнихме таблицата на простите числа само до 1000, не е ли възможно да създадем таблица на всички съществуващи прости числа“?

Нека първо отговорим на първата част от този въпрос. За повечето задачи, които изискват използването на прости числа, прости числа в рамките на хиляда ще бъдат достатъчни. В други случаи най-вероятно ще трябва да прибегнете до някои специални решения. Въпреки че със сигурност можем да създадем таблица с прости числа до произволно голямо крайно положително цяло число, било то 10 000 или 1 000 000 000, в следващия параграф ще говорим за методи за създаване на таблици с прости числа, по-специално ще разгледаме метод Наречен.

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

Теорема.

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

Доказателство.

Позволявам a е естествено число, по-голямо от едно, а b е най-малкият положителен делител на a, различен от едно. Нека докажем, че b е просто число от противното.

Да приемем, че b е съставно число. След това има делител на числото b (нека го означим с b 1), който е различен както от 1, така и от b. Ако вземем предвид също, че абсолютната стойност на делителя не надвишава абсолютна стойностделимо (знаем това от свойствата на делимост), то условие 1 трябва да е изпълнено

Тъй като числото a се дели на b според условието и казахме, че b се дели на b 1, концепцията за делимост ни позволява да говорим за съществуването на цели числа q и q 1, така че a=b q и b=b 1 q 1 , откъдето a= b 1 ·(q 1 ·q) . От това следва, че произведението на две цели числа е цяло число, тогава равенството a=b 1 ·(q 1 ·q) показва, че b 1 е делител на числото a. Като се вземат предвид горните неравенства 1

Сега можем да докажем, че има безкрайно много прости числа.

Теорема.

Има безкраен брой прости числа.

Доказателство.

Да приемем, че това не е така. Тоест, да предположим, че има само 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 също се дели на p n+1, равно на сумата p 1 ·p 2 ·…·p n +1. От това следва, че p n+1 трябва да раздели втория член на тази сума, който е равен на единица, но това е невъзможно.

По този начин е доказано, че винаги може да се намери ново просто число, което не е включено сред нито един брой предварително определени прости числа. Следователно има безкрайно много прости числа.

И така, поради факта, че има безкраен брой прости числа, когато съставяте таблици с прости числа, вие винаги се ограничавате отгоре до някакво число, обикновено 100, 1000, 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, трябва да започне с число, равно на (това следва от неравенството). Например, зачеркването на числа, кратни на две, трябва да започва с числото 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