Магията делителите
Прости числа — от решетото на Ератостен до приятелските числа
Числата, които се делят само на 1 и на себе си — и без разбирането на чиято природа съвременната криптография, теория на числата и информатика просто не биха съществували. Историята на простите числа е история на хиляди години търсене.
Спомняте ли си кои са първите операции с числа, на които се учехте в училище? След събирането и изваждането идват умножението и делението. Делението, особено на по-големи числа, за повечето от нас си остава предизвикателство — но именно в неговата сложност се крие и магията. Ако се захванем да намираме всички делители на всяко число, ще станем свидетели на любопитни закономерности.
Какво са простите числа?
Числата 2, 3, 5, 7, 11 се делят само на 1 и на себе си. Числата 4, 6, 8, 9, 10 имат и допълнителни делители. Всички числа, които се делят само на 1 и на себе си, наричаме прости числа. Числото 1 не считаме нито за просто, нито за съставно, защото много свойства на простите числа имат по-малко изключения, ако 1 не е включено.
На пръв поглед списъкът 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47… изглежда без логична последователност. И наистина — ако съществува формула за предвиждане на следващото просто число, тя все още не ни е известна.
Решетото на Ератостен
Древногръцкият математик Ератостен (III в.пр.Хр.) предложил елегантен метод за намиране на всички прости числа до даден предел. Той записвал числата върху папирус, опънат на рамка, и вместо да ги задрасква — ги пробождал с игла. В крайна сметка папирусът приличал на решето — оттам и името на метода. Незадрасканите числа са точно простите.
Алгоритъм: Пишем числата от 2 до N. Задраскваме всички кратни на 2, после на 3, после на 5, после на 7. Незадрасканите са простите до N.
Въпреки ефикасността си, методът е твърде бавен при значително по-големи числа. Оттук идва вечното търсене на формула. Известна е формулата n² − n + 41, чийто резултат е просто число за всяко n от 1 до 40 — но при n = 41 дава 1681 = 41², което е съставно.
Числата на Ферма
Французинът Пиер Ферма изказал хипотезата, че числата от вида Fn = 22n + 1 са прости за всяко n ∈ ℕ. Първите резултати изглеждат обещаващо:
| n | Fn = 22n + 1 | Стойност | Просто? |
|---|---|---|---|
| 1 | 2² + 1 | 5 | ✓ Да |
| 2 | 2⁴ + 1 | 17 | ✓ Да |
| 3 | 2⁸ + 1 | 257 | ✓ Да |
| 4 | 2¹⁶ + 1 | 65 537 | ✓ Да |
| 5 | 2³² + 1 | 4 294 967 297 | ✗ Не (= 641 × 6 700 417) |
През 1732 г. Ойлер открива, че F₅ е съставно, с което опровергава хипотезата на Ферма. Числата Fn все пак намират приложение: Карл Фридрих Гаус, само на 17 години, доказва, че правилен p-ъгълник може да се построи с линийка и пергел единствено когато p е просто число на Ферма.
Числата-близнаци
Сред простите числа се срещат двойки, различаващи се само с две единици: 3 и 5, 17 и 19, 2087 и 2089, 10 999 949 и 10 999 951. Такива двойки се наричат числа-близнаци. Дали броят им е краен или безкраен е едно от най-известните нерешени проблеми в съвременната математика.
Приятелските числа
Много по-сложна, но изключително любопитна зависимост се открива между т.нар. приятелски числа. Това са двойки (x, y), при които сборът на собствените делители на x е равен на y, и обратно.
Делители на 220: 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284
Делители на 284: 1 + 2 + 4 + 71 + 142 = 220
Тази двойка е известна още от времето на Питагор. Теоремата на Табит (IX в.) дава метод: ако за естествено число n числата a = 3·2ⁿ−1, b = 3·2ⁿ⁻¹−1 и c = 9·2²ⁿ⁻¹−1 са прости, то 2ⁿ·ab и 2ⁿ·c са приятелски. За момента са известни само три такива n: 2, 4 и 7.
При n = 4 Ибн ал-Бана и Ферма независимо намират двойката (17 296; 18 416). Декарт при n = 7 открива (9 363 584; 9 437 056). Ойлер добавя над 62 нови двойки. Любопитно е, че двойката (1184; 1210) остава неразкрита до 1866 г., когато я открива едва 16-годишният Николо Паганини — прочутият цигулар и композитор. Днес с помощта на компютри са намерени над 7500 приятелски двойки.
Хронология на простите числа
Запишете урок
Индивидуални и групови онлайн уроци по математика за цялата страна
- ›НВО по математика след 7 клас
- ›НВО по математика след 10 клас
- ›Кандидатстудентски изпити по математика
- ›Прием в университети в чужбина (ISEE, SAT, A-Level)
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти: Мат. анализ, Линейна алгебра, Аналитична геометрия, Диф. уравнения, Теория на вероятностите, Статистика и др.
Харесва ли ви съдържанието?
Ако тази статия ви е харесала, можете да подкрепите създаването на нови безплатни материали.
Коментари
Публикуване на коментар