Разберете, че числото е просто. Как да намерим прости числа

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