7 е просто число или 9 е просто число. Как да определим просто число

Още в древността хората са знаели, че има числа, които не се делят на друго число. Последователност прости числаизглежда нещо подобно:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 …

Доказателството, че има безкрайно много от тези числа, също беше дадено от Евклид, живял през 300 г. пр.н.е. Около същите години друг гръцки математик, Ератостен, излезе с доста прост алгоритъм за получаване на прости числа, чиято същност беше последователно зачеркване на числа от таблицата. Останалите числа, които не се делят на нищо, са прости. Алгоритъмът се нарича „ситото на Ератостен“ и поради своята простота (няма операции за умножение или деление, само събиране) все още се използва в компютърните технологии.

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

Подчиняват ли се простите числа на някакви закони? Да, и те са доста любопитни.

Например френският математик Мерсеноще през 16 век той открива, че много прости числа имат формата 2^N - 1, тези числа се наричат ​​числа на Мерсен. Не много преди това, през 1588 г., италианският математик Каталдиоткрива простото число 2 19 - 1 = 524287 (според класификацията на Мерсен се нарича М19). Днес това число изглежда доста малко, но дори сега с калкулатор ще отнеме много дни, за да се провери неговата простота, но за 16-ти век това е наистина огромна работа.

200 години по-късно математик Ойлернамери друго просто число 2 31 - 1 = 2147483647. Отново всеки може сам да си представи необходимото количество изчисления. Той също така изложи хипотеза (по-късно наречена "проблемът на Ойлер" или "двоичният проблем на Голдбах"), чиято същност е проста: всяко четно число, по-голямо от две, може да бъде представено като сума от две прости числа.

Например можете да вземете произволни 2 четни числа: 123456 и 888777888.

С помощта на компютър можете да намерите тяхната сума под формата на две прости числа: 123456 = 61813 + 61643 и 888777888 = 444388979 + 444388909. Интересното тук е, че точно доказателство на тази теорема все още не е намерено, въпреки че с с помощта на компютрите е проверено до числа с 18 нули.

Има още една теорема на математика Пиер Ферма, открит през 1640 г., който казва, че ако едно просто число има формата 4*k+1, тогава то може да бъде представено като сбор от квадратите на други числа. Така, например, в нашия пример, простото число 444388909 = 4*111097227 + 1. И наистина, като използвате компютър, можете да откриете, че 444388909 = 19197*19197 + 8710*8710.

Теоремата е доказана от Ойлер едва 100 години по-късно.

И накрая Бернхард Риманпрез 1859 г. е представена така наречената „хипотеза на Риман“ за броя на разпределенията на простите числа, които не надвишават определено число. Тази хипотеза все още не е доказана, тя е включена в списъка на седемте „проблема на хилядолетието“, за решението на всеки от които Институтът по математика Клей в Кеймбридж е готов да плати награда от един милион щатски долара.

Така че не е толкова просто с простите числа. Има също невероятни факти. Например през 1883 г. руският математик ТЯХ. Первушинот област Перм доказа простотата на числото 2 61 - 1 = 2305843009213693951 . Дори и сега битовите калкулатори не могат да работят с толкова дълги числа, но по онова време това беше наистина гигантска работа и как е направено и до днес не е много ясно. Въпреки че наистина има хора, които имат уникални мозъчни способности - например, аутистите са известни с това, че могат да намерят (!) 8-цифрени прости числа в ума си. Как правят това не е ясно.

Модерност

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

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

Например, ако вземем две прости числа 444388979 и 444388909, тогава „частният ключ“ ще бъде 444388979, а продуктът 197481533549433911 (444388979*444388909) ще бъде предаден публично. Само познавайки другата си половина, можете да изчислите липсващото число и да дешифрирате текста с него.

Какъв е трикът тук? Въпросът е, че произведението на две прости числа не е трудно за изчисляване, но обратната операция не съществува - ако не знаете първата част, тогава такава процедура може да се извърши само с груба сила. И ако вземете наистина големи прости числа (например с дължина 2000 знака), тогава декодирането на техния продукт ще отнеме няколко години дори на модерен компютър (дотогава съобщението отдавна ще бъде без значение).

Гениалността на тази схема е, че в самия алгоритъм няма нищо тайно - той е отворен и всички данни са на повърхността (известни са както алгоритъмът, така и таблиците на големите прости числа). Самият шифър, заедно с публичен ключможе да се предава по всякакъв начин, по всякакъв начин отворена форма. Но без да знаем тайната част от ключа, която изпращачът е избрал, ние няма да получим шифрования текст. Например, можем да кажем, че описание на алгоритъма RSA е публикувано в списание през 1977 г. и там също е даден пример за шифър. Едва през 1993 г. с помощта на разпределени изчисления на компютрите на 600 доброволци е получен правилният отговор.

Така че простите числа се оказаха съвсем не толкова прости и очевидно тяхната история не свършва дотук.

Отговорът на Иля е правилен, но не много подробен. През 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 е просто число.

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

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 и други цели числа освен 1 и себе си. Горната формула премахва ненужните стъпки и спестява време: например след проверка дали дадено число се дели на 3, няма нужда да проверявате дали то се дели на 9.

• Функцията floor(x) закръгля x до най-близкото цяло число, което е по-малко или равно на x.

Научете за модулната аритметика.Операцията е "x mod y" (mod е съкращение от латинска дума"modulo" означава "разделяне на x на y и намиране на остатъка." С други думи, в модулната аритметика, при достигане на определена стойност, която се нарича модул, числата отново се „обръщат“ към нула. Например, часовникът поддържа време с модул 12: той показва 10, 11 и 12 часа и след това се връща на 1.

• Много калкулатори имат моден ключ. Краят на този раздел показва как ръчно да оцените тази функция за големи числа.

Научете за капаните на малката теорема на Ферма.Всички числа, за които не са изпълнени условията на теста, са съставни, но останалите числа са само вероятносе класифицират като прости. Ако искате да избегнете неправилни резултати, потърсете пв списъка с "числа на Кармайкъл" (съставни числа, които отговарят на този тест) и "псевдопрости числа на Ферма" (тези числа отговарят на условията на теста само за някои стойности а).

Ако е удобно, използвайте теста на Милър-Рабин.въпреки че този методдоста тромав при ръчно изчисляване, често се използва в компютърни програми. Той осигурява приемлива скорост и дава по-малко грешки от метода на Ферма. Съставно число няма да бъде прието като просто число, ако се правят изчисления за повече от ¼ от стойностите а. Ако произволно изберете различни стойности аи за всички тях тестът ще даде положителен резултат, можем да приемем с доста висока степен на увереност, че пе просто число.

За големи числа използвайте модулна аритметика.Ако нямате под ръка калкулатор с мод функция или калкулаторът не е предназначен за работа с такава големи числа, използвайте свойствата на степените и модулната аритметика, за да улесните изчисленията. По-долу е даден пример за 3 50 (\displaystyle 3^(50))мод 50:

• Препишете израза в по-удобна форма: mod 50. Когато правите ръчни изчисления, може да са необходими допълнителни опростявания.
• (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Тук взехме предвид свойството на модулното умножение.
• 3 25 (\displaystyle 3^(25))мод 50 = 43.
• (3 25 (\displaystyle (3^(25))мод 50 ∗ 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 ∗ 43) (\displaystyle (43*43))мод 50.
• = 1849 (\displaystyle =1849)мод 50.
• = 49 (\displaystyle =49).

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

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

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

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

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

Прости числаса цели числа, големи единици, които имат само два положителни делителя, а именно себе си и 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