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

📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆ 📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆

★ Интересно от математиката

Простите числа —
градивните елементи на математиката

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

Д-р Атанас Илчев • Поредица: Интересно от математиката

Простите числа са един от крайъгълните камъни на математиката. От Питагор и Евклид в Древна Гърция до Ферма и Ойлер в модерната епоха — поколения математици са прекарвали живота си в изучаването им. Въпросът „защо?" има прост отговор: защото зад тяхното просто определение се крие изненадваща дълбочина.

Какво са простите числа?

Определение: Едно естествено число е просто, ако е по-голямо от 1 и се дели само на 1 и на себе си.

Числата 2, 3, 5, 7 са прости. Числото 4 = 2·2 и 6 = 2·3 — не са прости, те са съставни. Всички прости числа под 100:

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

Фундаменталната теорема на аритметиката

Простите числа са изключително важни, защото всяко естествено число може да се запише като произведение на прости числа — и то по точно един начин. Тази забележителна теорема е описана за първи път от Евклид около 300 г. пр.н.е.

Фундаментална теорема на аритметиката: Всяко естествено число \(n \gt 1\) може да се запише като произведение на прости числа, и това разлагане е единствено (до размяна на реда на множителите).

Примери за разлагане

\[11 = 11 \qquad 15 = 3\cdot 5 \qquad 20 = 2^2\cdot 5\] \[42 = 2\cdot 3\cdot 7 \qquad 100 = 2^2\cdot 5^2\]

Именно тази теорема ни дава право да мислим за простите числа като за „атоми" на аритметиката — от тях се изгражда всяко останало число, по уникален начин.

Колко са простите числа?

Интуитивно изглежда, че с нарастването на числата простите ще стават все по-рядко срещани — в крайна сметка ще се „изчерпят". Евклид доказва, че това не е така: простите числа са безкрайно много. Доказателството му е едно от най-ранните запазени доказателства чрез противоречие в историята на математиката.

Идеята на Евклид: Допуснем, че простите числа са краен списък \(p_1, p_2, \ldots, p_k\). Разгледаме числото \(N = p_1 \cdot p_2 \cdots p_k + 1\). То не се дели на нито едно от \(p_1,\ldots,p_k\), следователно или е само просто, или има прост делител извън списъка — противоречие.

Макар прости числа да има безкрайно много, те стават все по-рядко срещани. Теоремата за простите числа, доказана независимо от Жак Адамар и Шарл-Жан дьо ла Вале Пусен през 1896 г., описва точно колко бавно намалява тяхната честота.

Дефинираме функцията \(\pi(x)\) — броят на простите числа, по-малки или равни на \(x\). Например \(\pi(10) = 4\), защото простите числа до 10 са 2, 3, 5, 7. Теоремата за простите числа гласи:

\[\pi(x) \sim \frac{x}{\ln x} \quad (x \to \infty).\]

Интерпретация: Вероятността едно произволно число около \(x\) да бъде просто е приблизително \(\dfrac{1}{\ln x}\). При \(x = 10^6\) тази вероятност е около 7%; при \(x = 10^{12}\) — около 4%. Простите числа стават все по-редки, но никога не изчезват — честотата им намалява бавно (логаритмично), а не рязко.

Закономерности и спиралата на Улам

Липсва прост алгоритъм за разграничаване на прости от съставни числа при произволно голям вход. Именно затова намирането на нови рекордни прости числа изисква масивна изчислителна мощ. Към момента на писане на тази статия най-голямото известно просто число е \(M_{136279841} = 2^{136279841}-1\) с 41 024 320 цифри, открито от GIMPS (виж статията ни за тази тема).

Въпреки привидния хаос в разпределението на простите числа, визуализацията разкрива изненадваща скрита структура. Спиралата на Улам, създадена от математика и физик Станислав Улам, се получава, като се запишат естествените числа по спирала, започваща от центъра, и се маркират само простите:

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

В картината ясно се открояват диагонални линии — ивици от прости числа, пресичащи спиралата. Тези линии не са случайни. Всяка от тях съответства на квадратен полином. Ойлер забелязва, че полиномът \(P(n) = n^2 + n + 41\) дава прости числа за \(n = 0, 1, 2, \ldots, 39\) — 40 последователни прости стойности. Подобни полиноми пораждат видимите диагонали в спиралата.

ⓘ Хипотезата на Риман

Скритата структура в разпределението на простите числа е свързана с нулите на дзета функцията на Риман \(\zeta(s)\). Хипотезата на Риман — че всички нетривиални нули лежат на правата \(\text{Re}(s) = \frac{1}{2}\) — би дала точна информация за „грешките" в апроксимацията \(\pi(x) \approx \frac{x}{\ln x}\). Тя е включена в списъка на Проблемите на хилядолетието и носи награда от 1 000 000 долара.

Прости числа Фундаментална теорема на аритметиката Спирала на Улам Теорема за простите числа Хипотеза на Риман Евклид История на математиката

Следваща статия от поредицата

Интересни факти от историята на математиката

Запишете урок

Индивидуални и групови онлайн уроци по математика за цялата страна

🎓 Подготовка за изпити

• ›НВО по математика след 7 клас
• ›НВО по математика след 10 клас
• ›Кандидатстудентски изпити по математика
• ›Прием в университети в чужбина (ISEE, SAT, A-Level)

📚 Текущо обучение и студенти

• ›Усвояване на текущия учебен материал (всички класове)
• ›Студенти: Мат. анализ, Линейна алгебра, Аналитична геометрия, Диф. уравнения, Теория на вероятностите, Статистика и др.

✆ 0883 375 433 ☎ Viber

Харесва ли ви съдържанието?

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

📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆ 📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆