Властивості простих чисел

Размещено на http://www.allbest.ru/

Зміст

ВСТУП

I. ПРОСТІ ЧИСЛА

1. Означення простого та взаємно-простого числа. Деякі теореми про прості числа

2. Нескінченість множини простих чисел. Решето Ератосфена

3. Основна теорема арифметики

4. Прості числа-близнята

5. Прості числа Мерсенна

6. Найпростіші та суперпрості числа

7. Визначення великих простих чисел

8. Дружба чисел

9. Проблема Гольдбаха

II. ФУНКЦІЯ . Теорема Ейлера

1. Функція . Теорема Ейлера

2. Асимптотичний закон розподілу простих чисел

3. Таблиці Гаусса

ВИСНОВКИ

СПИСОК ДЖЕРЕЛ

Додатки



ВСТУП

Виникнення чисел у житті не випадковість. Важко уявити собі спілкування без використання чисел. Історія чисел захоплююча й загадкова. Людство встановило низку законів і закономірностей світу чисел. Без чудової науки про числа - математики - немислимо сьогодні минуле, ні майбутнє. А скільки ще нерозгаданого! "Найдавніші з походження числа - натуральні. "Струмки" натуральних чисел, зливаючись, породжують безмежний океан речовинних різного роду особливих спеціальних чисел", так писав про числа Б.А.Кордемський у своїй книжці "Дивний світ чисел". Особливої актуальності набувають питання, присвячені вивченню чисел Мерсенна, а саме їх зв'язок з критерієм простоти Люка - Кемера та питання постулата Бертрана. Моя робота заснована на аналізі доступних мені джерел: ресурси мережі Internet та наукова література з алгебри та теорії чисел. Об?єкт: прості числа. Предметом дослідження є властивості простих чисел та їх розподіл. Функція .

Мета роботи полягає у вивченні властивостей простих чисел і застосування їх на практиці, вивчення алгоритму пошуку кількості простих чисел на проміжку.

У відповідності з метою сформульовані завдання роботи:

1. Вивчити властивості натуральних чисел.

2. Розглянути застосування простих чисел на практиці.

3. Встановити низку властивостей, законів і закономірностей різних видів простих чисел.

4. Навчитися шукати кількість простих чисел на проміжку.

Основними методами дослідження простих чисел є вивчення та обробка літературних джерел, систематизація даних за видами простих чисел та їх властивостями. Робота буде корисна магістрантам, студентів старших курсів та викладачам, які цікавляться алгеброю та теорією чисел .



І. ПРОСТІ ЧИСЛА

1. Означення простого та взаємно-простого числа. Деякі теореми про прості числа

Взаємно прості числа -- натуральні або цілі числа, які не мають спільних дільників більших за 1, або, інакше кажучи, якщо їх найбільший спільний дільник дорівнює 1. Таким чином, 2 і 3 -- взаємно прості, а 2 і 4 -- ні (діляться на 2). Будь-яке натуральне число взаємно просте з 1. Якщо p -- просте, а n -- довільне ціле число, то вони взаємно прості тоді і тільки тоді, коли n не ділиться на p. Взаємна простота великих чисел може бути перевірена і доведена чи спростована за допомогою алгоритму Евкліда.

Число 1 має тільки один дільник, а саме 1, а кожне натуральне число а, відмінне від 1, має принаймні два дільники: 1 і а (тут і далі мова йде тільки про додатні дільники).

Означення 1.1 Відмінне від 1 натуральне число а називають простим, якщо воно не має дільників, відмінних від 1 і а. Його називають складеним, якщо воно має дільники, відмінні від 1 і а.

Простими є, наприклад, числа 2, 7, 13; числа 4, 9, 15 - складені. Число 1 не належить ні до простих, ні до складених чисел.

Доведемо кілька важливих теорем про прості числа.

Теорема 1.1 Всяке натуральне число а або ділиться на дане просте число р, або взаємно просте з р.

Справді, найбільший спільний дільник (а, р) як дільник числа р може дорівнювати або р, або 1. У першому випадку a ділиться на р, у другому а і р - взаємно прості числа.

Теорема 1.2 Якщо добуток кількох натуральних чисел ділиться на просте число р, то принаймні один із співмножників ділиться на р.

Справді, внаслідок попередньої теореми, кожен із співмножників або взаємно простий з р, або ділиться на р. Але якби всі множники були взаємно прості з р, то за теоремою їх добуток був би взаємно простий з р. Тому хоч один з множників ділиться на р.

Теорема 1.3 Найменший відмінний від 1 дільник більшого від 1 натурального числа а є число просте.

Нехай q - найменший дільник натурального числа а > 1. Якби q було числом складеним, то воно мало б дільник q₁, такий, що 1< q₁< q. Але тоді а ділилося б на q₁ і q не було б найменшим дільником числа а.

Теорема 1.4 Найменший відмінний від 1 дільник складеного числа а не більший за .

Нехай найменшим відмінним від 1 дільником числа а є q. Тоді а = q * a₁ де а₁ - деяке натуральне число, причому а₁ ? q, бо в противному разі q не було б найменшим додатним дільником числа а. Отже, а * a₁ ? qa₁ * q і тому а ? q², q ? .

2. Нескінченість множини простих чисел. Решето Ератосфена

Давньогрецьких вчених зацікавило: скільки може бути простих чисел в натуральному ряді? Відповів на це питання Евклід, довівши, що множина простих чисел нескінченна.

Теорема 2.1 (Евкліда). Множина простих чисел нескінченна.

Припустимо, що множина простих чисел скінчена. Нехай вона складається з простих чисел p₁, p₂, ..., р_п. Отже, ми припускаємо, що простих чисел, відмінних від p₁, p₂, ..., р_п, немає. Розглянемо тепер ціле число р = p₁ p₂, ... р_п. Очевидно, що це число відмінне від кожного з чисел p₁, p₂, ..., р_п. Оскільки число 1 не має дільників, відмінних від самого себе, то жодне з простих чисел p₁, p₂, ..., р_п не може бути дільником числа р. Ціле число р > 1. Тому воно або само просте, або за теоремою 3 ділиться на просте число, відмінне від кожного з чисел p₁, p₂, ..., р_п Звідси випливає, що існує принаймні одне просте число, відмінне від чисел p₁, p₂, ..., р_п а це суперечить нашому припущенню. Отже, наше припущення неправильне. Цим теорему доведено. Природно постає запитання: як у ряду натуральних чисел виділити всі прості числа?

Таблицю всіх простих чисел, що не перевищують даного натурального числа N, можна скласти так. Випишемо підряд усі натуральні числа від 2 до N:

2, 3, 4, 5, ..., N (1)

Потім закреслимо в ряду (1) всі числа, кратні 2, крім самого числа 2. Першим числом у ряду (1), яке залишилося після цього, є число 3. Число 3 не ділиться на 2, бо в противному разі ми закреслили б його: отже, число 3 ділиться лише на 1 і на самого себе, тому воно просте. Закреслимо тепер у ряду (1) всі числа, кратні 3, крім самого числа 3.

Першим числом, яке залишилося після цього в ряду (1), є число 5; воно не ділиться ні на 2, ні на 3, бо в противному разі воно виявилося б закресленим; отже, 5 ділиться тільки на 1 і на самого себе, тому воно просте число. Потім у ряду (1) закреслимо всі числа, кратні 5, крім самого числа 5 і т. д. Закресливши в ряду (1) всі числа, кратні простим числам, не більшим ніж , дістанемо за теоремою 4 таблицю всіх простих чисел, які не перевищують числа N.

Уперше для складання таблиць простих чисел описаний щойно метод застосував грецький математик Ератосфен. Ератосфен писав числа на папірусі, натягнутому на рамку; числа він не закреслював, а проколював. Внаслідок цього він діставав дещо схоже на решето: складені числа «просіювалися» крізь це решето, а прості числа залишалися. Тому цей метод називають решетом Ератосфена.

Метод Ератосфена поступово удосконалювався, завдяки чому складання таблиць простих чисел спрощувалося. Це, в свою чергу, дало можливість скласти таблиці простих чисел, що містять порівняно велику кількість чисел. Тепер складені таблиці простих чисел приблизно до 10 мільйонів. Приклад 1. Знайти прості чиста на проміжку [2, 30].

Запишемо натуральні числа починаючи від 2 до 30 в ряд:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Перше число у списку, 2 - Просте. Пройдемо по ряду чисел, закреслюючи всі числа кратні 2 (тобто кожне друге, починаючи з 2² = 4 ):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Наступне не закреслене число 3 - просте. Пройдемо по ряду чисел, закреслюючи всі числа кратні 3 (тобто кожне третє, починаючи з 3² = 9 ):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Наступне незакреслене число 5 - Просте. Пройдемо по ряду чисел, закреслюючи всі числа кратні 5 (тобто кожне п'яте, починаючи з ² 5 = 25 ). І т. д. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Необхідно провести закреслення кратних для всіх простих чисел p , Для яких p ² ? n . У результаті всі складені числа будуть закреслені, а не закресленими залишаться всі прості числа. Для n=30 вже після закреслення кратних числу 5 всі складені числа виходять закресленими:

2 3 5 7 11 13 17 19 23 29

Отримали всі прості числа на даному проміжку.

Алгоритм пошуку простих чисел висіюванням

Для знаходження всіх простих чисел не більше заданого числа n, дотримуючись методу Ератосфена, потрібно виконати наступні кроки:

1) Виписати підряд всі цілі числа від 2 до n (2,3,4 ..., n)

2) Нехай змінна p спочатку дорівнює 2 - першому простому числу.

3) Викреслити зі списку всі числа від 2 p до n, що діляться на p (тобто, числа 2 p, 3 p, 4 p, ....)

4) Знайти перше не викреслене число, більше, ніж р, і привласнити значенням змінної p це число.

5) Повторювати кроки 3 та 4 до тих пір, поки p не стане більше, ніж n.

6) Всі не викреслені числа у списку - прості числа.

На практиці, алгоритм можна трохи покращити таким чином:

На кроці № 3, числа можна викреслювати, починаючи відразу з числа p² , тому що всі складові числа менше нього вже будуть викреслені до цього часу. І, відповідно, зупинити алгоритм можна, коли p² стане більше, ніж n.

3. Основна теорема арифметики

Доведемо тепер теорему, яка відіграє фундаментальну роль як у теорії подільності, так і в усій теорії чисел, її називають основною теоремою арифметики.

Теорема 6. (Основна теорема арифметики). Кожне відмінне від 1 натуральне число р можна записати у вигляді добутку простих чисел і притому єдиним способом, якщо не брати до уваги порядок розміщення співмножників.

Доведемо спочатку можливість запису натурального числа q ? 1 у вигляді добутку простих чисел. Для натурального числа 2 це можливо, бо число 2 просте, тобто його можна вважати добутком простих чисел з числом співмножників, що дорівнює одиниці. Припустимо, що це можливо для всякого натурального числа k, такого, при якому 2 < k < п, і доведемо, що в такому разі і натуральне число п можна записати у вигляді добутку простих чисел. Справді, якщо натуральне число п просте, то воно є добутком простих чисел з числом співмножників, що дорівнює одиниці. Якщо ж число п складене, то воно має дільник k₁ відмінний від 1 і від п. Отже,



n = k₁• k₂,

де k₂ - натуральне число, відмінне від 1. Тоді 2 ? k₁ < n, 2 ? k₂ < n. Через те що за припущенням кожне з чисел k₂ і k₂ записується у вигляді добутку простих чисел, то й число n = k₁• k₂ записується у вигляді добутку простих чисел. Отже, внаслідок принципу математичної індукції будь-яке натуральне число п можна записати у вигляді добутку простих чисел.

Доведемо тепер єдиність запису числа п у вигляді добутку простих чисел.

Нехай число п двома способами записано у вигляді добутку простих чисел, тобто

п = p₁ p₂ ... р_r і

п = q₁ q₂ ... q_s,

де r ? 2, s ? 2 і всі числа р_i і q_k прості. Доведемо, що ці записи можуть відрізнятися лише порядком співмножників, тобто що r = s і при належному виборі нумерації співмножників р_i = q_і, і = 1, 2, ..., s. Доводитимемо це індукцією по п. Для числа 2 правильність цього твердження очевидна. Число 2 є добуток простих чисел з числом співмножників, що дорівнює одиниці. Нехай твердження правильне для всякого числа k, такого, що 2 ? k < п. Доведемо, що в такому разі твердження правильне і для числа п. Справді, оскільки п = p₁ p₂ ... р_r і п = q₁ q₂ ... q_s, то

p₁ p₂ ... р_r = q₁ q₂ ... q_s(2)

Ліва частина цієї рівності ділиться на просте число p₁. Отже, і права частина її ділиться на просте число p₁. Звідси за теоремою 2 принаймні один із співмножників q₁ q_z, ..., q_s ділиться на просте число р₁. Змінивши, якщо потрібно, нумерацію множників q₁ q_z, ..., q_s, ми вважатимемо, що на p₁ ділиться співмножник q₁. Оскільки q₁ є просте число і ділиться на відмінне від 1 просте число р₁, то q₁ = р₁.

Поділивши обидві частини рівності (2) на число р₁ = q₁ дістанемо рівність p₂ p₃ ... р_r = q₂ q₃ ... q_s

Число n₁ = p₂ p₃ ... р_r = q₂ q₃ ... q_s задовольняє умову 2 ? n₁ < п. Тому за припущенням для нього твердження правильне, тобто r - l=s-l, і при відповідній нумерації р₂ = q₂. pз = q₃, … , p_s = q_s Звідси випливає, що r = s і при відповідній нумерації p_i = q_i, і = 1, 2, ..., s.

Отже, внаслідок принципу математичної індукції, всяке відмінне від 1 натуральне число n єдиним способом записується у вигляді добутку простих чисел. Цим теорему доведено.

Зауважимо, що запис n = p₁ p₂ ... p_s натурального числа п у вигляді добутку простих чисел p₁ , p₂ ... p_s називають також розкладом числа п у добуток простих множників, або розкладом на прості множники.

Основна теорема арифметики показує, що всі натуральні числа дістають з простих чисел за допомогою операції множення: кожне натуральне число (складене) є деякий добуток простих чисел, причому різні добутки дають різні числа. Тепер зрозуміло, чому одиницю не слід вважати простим числом: віднісши 1 до простих чисел, ми порушили б єдиність розкладу числа в добуток простих чисел, оскільки до будь-якого добутку можна приєднати множником 1.

4. Прості числа-близнята

Прості числа-близнята - числа, різниця між якими дорівнює 2. Між двома простими числами можуть знаходитися мільйони і мільярди складених чисел або лише одне, бо це найкоротша відстань між простими числами, за виключенням 2 і 3,так як прості числа ніколи не слідують один за одним. Цей факт був використаний у вигляді метафори в назві книги Паоло Джордано «Самотність простих чисел». В одному з романів ця метафора була описана більш детально: «В університеті на одній з лекцій Маттіа дізнався, що серед простих чисел є особливі. Математики називають їх парними або числами-близнятами. Це пари простих чисел, які стоять майже поруч, тому що між ними завжди виявляється інше число, яке заважає їм по-справжньому доторкнутися один до одного. Наприклад, це числа 11 і 13, 17 і 19, 41 і 43, Маттіа думав, що вони з Аліче - ось такі числа-близнята, самотні і загублені, разом, але недостатньо близькі, щоб по-справжньому доторкнутися один до одного».

В першій сотні натуральних чисел ми зможемо знайти наступні пари чисел, з різницею 2: 3 і 5, 5 і 7, 11 і 13, 17 і 19, 29 і 31, 41 і 43, 59 і 61, 71 і 73.

Такі «парні» числа можуть бути описані виразом (p, p+2), де p - просте число. Нижче наведено список усіх простих чисел-близнят з першої тисячі:

3 і 5, 5 і 7, 11 і 13, 17 і 19, 29 і 31, 41 і 43, 59 і 61, 71 і 73, 101 і 103, 107 і 109, 137 і 139, 149 і 151, 179 і 181, 191 і 193, 179 і 181, 191 і 193, 197 і 199, 227 і 229, 239 і 241, 269 і 271, 281 і 283, 311 і 313, 347 і 349, 419 і 421, 431 і 433, 461 і 463, 521 і 523, 569 і 571, 599 і 601, 617 і 619, 641 і 643, 659 і 661, 809 і 811, 821 і 823, 827 і 829, 857 і 859, 881 і 883.

Ми знаємо, що прості числа-близнята зустрічаються все рідше і рідше. Проте комп'ютерні розрахунки показують, що вони продовжують зустрічатися навіть серед незвичайно великих чисел. А так як існує нескінченна кількість простих чисел, можна висунути гіпотезу, що існує незліченна кількість простих чисел-близнят, але цього ще нікому не вдалося довести. Найбільшою парою чисел-близнят вважають 65516468355-1 і 65516468 +1. Найбільш вражаючим є те, що кожне число складається з 100355 цифр! Цю пару чисел відкрили 2009 року.

Ще одна чудова група простих чисел, яка зустрічається в першій сотні натурального ряду, містить три такі числа: 3, 5, 7.Вони можуть бути записані як (р,р+2,р+4), де р- просте число. Ця група простих чисел складається з так званих «трійок».



5. Прості числа Мерсенна

Числа Мерсенна - це числа виду, де p - довільне ціле число, зване показником. Ці числа вабили математиків з найдавніших часів, орієнтовно з Евкліда (приблизно 300 рік до нашої ери), правда, до XVI століття вчені вважали, що всі ці числа прості, тобто діляться тільки на себе і одиницю. Це, звичайно ж, неправильно - досить поглянути на четверте число Мерсенна: воно дорівнює 15 і подається у вигляді добутку 3 і 5.

Мабуть, першим, хто помітив, що не всі числа Мерсенна з простими показниками (відомо, що для складених показників число Мерсенна не може бути простим) є простими, був Худальрікус Регіус в 1536 році. Він показав, що при p = 11 число, що вийшло - це 2047 - виявляється складеним, оскільки подається у вигляді добутку 23 і 89.

У XVII столітті пошук простих чисел Мерсенна став досить популярною серед математиків розвагою. У 1640р. до вивчення цих чисел підключився знаменитий П'єр Ферма - він показав, що роботи його попередників, в яких затверджувалася простота чисел для p = 23 і p = 37, були помилкові. Але взагалі, Ферма не унікальний у своєму інтересі до цього предмету. В історії цих чисел відзначилися багато відомих учених: Ейлер, Паскаль, Галілео, Гюйгенс. Ім'я ж своє числа Мерсенна отримали на честь французького ченця Марена Мерсенна, філософа, теолога і математика. Він натрапив на ці числа в пошуках універсальної формули, яка дозволяла б перераховувати всі прості числа. У 1648 році він випустив працю Cogitata Physica-Mathematica, в якій висловив припущення, що числа виду -1 повинні бути простими для показників 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 і складеними для всіх інших цілих чисел, що не перевищують 257. Звідки взялася така гіпотеза, достовірно невідомо - сучасники вагаються, що Мерсенн міг розібрати всі ці випадки вручну, та й він сам, кажуть, це визнавав. Втім, ця гіпотеза стала популярною вже після смерті автора. Так часто буває з деякими математичними твердженнями - по абсолютно незрозумілій причині вони опиняються в центрі уваги безлічі математиків. Можливо, на руку їй зіграла, як і у випадку з легендарною теоремою Ферма, простота формулювання. Як би там не було, але з рядом Мерсенна вчені розібралися тільки в середині XX століття - тоді вони встановили, що список показників, які дають прості числа Мерсенна і не перевищуючих 257, виглядає наступним чином: 2, 3, 5, 7, 13, 17 , 19, 31, 61, 89, 107 і 127. Це і є перші 12 простих чисел Мерсенна. До речі, простоту числа Мерсенна для показника 61 (воно дорівнює 2 305 843 009 213 693 951) довів російський математик Іван Первушин в 1878 році.

Марен Мерсенн протягом першої половини XVII століття був по суті координатором наукового життя Європи, ведучи активну переписку практично з усіма видатними вченими того часу. Це листування має величезну наукову та історичну цінність. Мерсенн має також серйозні особисті наукові заслуги в галузі математики, акустики та теорії музики.

7. Найпростіші та суперпрості числа

Просте число називають найпростішим, якщо після відкидання однієї, двох, трьох і т.д. цифр ми будемо одержувати просте число. Очевидно, що таке число може починатися тільки на 2, 3, 5, 7, а всередині числа не можуть бути цифри 0, 2, 4, 6, 8, 5.

Маючи таблицю простих чисел легко скласти комп'ютерну програму, яка відбере найпростіші числа. Наводимо приклади найпростіших чисел 23, 53, 317, 539, 797, 2393, 3793, 3797, 73331, 373393, 2399333, 73939133, 59393133, 73939133. Можна показати, використавши подільність на три і принцип Діріхле, що найпростіших дев'ятицифрових і довших не існує. Тобто, множина найпростіших чисел скінченна.

Просте число називають суперпростим, якщо після відкидання одно, двоцифрового і т.д. чисел , які будуть простими - числа, які при цьому отримаємо теж будуть простими. Очевидно, що суперпрості числа є підмножиною найпростіших чисел. Тому підмножину суперпростих чисел легко скласти за допомогою нескладної комп'ютерної програми, яка відбере суперпрості числа з найпростіших чисел.

Наведемо приклади суперпростих чисел: 29, 317, 3797, і т.д. Ця підмножина теж скінченна.

7. Визначення великих простих чисел

З'ясування того, чи відноситься число до простих чи ні є доволі складною задачею, адже якщо допустити, що маємо число n, то необхідно перевірити його на подільність на проміжку від 2 до n-1 цілих чисел. Щоб скоротити цей процес в математиці (теорії чисел) було доведено, що для доведення простоти числа, його можна перевірити на подільність на проміжку від 2 до округленого кореня з n, це значно скорочує кількість дій.

8. Дружба чисел

Два натуральних числа m і n називаються дружніми, якщо сума власних дільників m дорівнює n, а сума власних дільників n дорівнює m. Історія дружніх чисел губиться в глибині століть. За свідченням античного філософа Ямвлиха (III - IV ст.), Великий Піфагор на питання, кого слід вважати своїм другом, відповів: «Того, хто є моїм другим я, як числа 220 і 284».

У 1747-1750 рр.. Леонард Ейлер провів унікальні числові розкопки. Він придумав оригінальні методи пошуку і виявив відразу 61 нову пару дружніх чисел. Примітно, що серед них опинилися і не парні числа: 69 615 і 11498355; 87633 і 12024045. Зараз відомо близько 1100 пар дружніх чисел. Цікаво, що в 1866 р. італійський школяр Н. Паганіні знайшов пару дружніх чисел 1184 і 1210, яку всі, в тому числі і видатні математики, прогледіли.

Ось пари дружніх чисел в межі 100 000:

220 - 284; 1184 - 1210; 2620 - 2924; 5020 - 5564; 6232 - 6368; 10744 - 10856

12285 - 14595; 17296 - 18416; 63020 - 76084; 66928 - 66992; 67095 - 71145; 69615 - 87633; 79750 - 88730.

Дружні числа продовжують приховувати безліч таємниць. Чи є змішані пари, у яких одне число парне, а інше не парне? Чи існує загальна формула, що описує всі дружні пари? На ці та інші питання відповіді поки не знайдені.

З досвіду обчислення люди знали, що кожне число є або простим, або добутком декількох простих чисел. Але вони не вміли цього доводити. Піфагор або хтось із його послідовників знайшов доказ цього твердження.

Тепер легко пояснити роль простих чисел в математиці: вони є тими цеглинками, з яких за допомогою множення будують всі інші числа. Добре було б, якщо всі прості числа можна було порахувати. Хай їх було б хоч мільйон - все одно ми знали б, що, перемноживши ці прості числа, можемо отримати всі інші. Але це виявилося не так. Через два століття після Піфагора грецький геометр Евклід написав книгу «Начала». І одним із тверджень цієї книги було наступне: найбільшого простого числа не існує.

Прості числа в натуральному ряді чисел розташовані дуже химерно. Іноді між ними є тільки одне парне число (всі прості числа, крім числа 2, непарні). Такими близнюками (так їх кличуть у науці), є: 11 і 13, 17 і 19, 29 і 31. Досі невідомо, чи є найбільші близнюки чи ні. А іноді між сусідніми простими числами лежить прірва в мільйони і мільярди чисел. Першим глибокі результати про те, як розкидані прості числа серед інших натуральних чисел, отримав великий російський математик Пафнутій Львович Чебишев, засновник і керівник російських математичних досліджень в минулому столітті.



6. Проблема Гольдбаха

З простих чисел можна отримати будь-яке число за допомогою множення. А що буде, якщо складати прості числа? Звичайно, якщо брати скільки завгодно доданків, то можна отримати будь-яке число: парні числа виходять шляхом складання двійок, а не парні шляхом складання однієї трійки і декількох двійок. Але жив в Росії в XVIII столітті математик Гольдбах, який вирішив складати непарні прості числа лише попарно. Він виявив дивовижну річ: кожен раз йому вдавалося представити парне число у вигляді суми двох простих чисел. Ось ці розкладання для двозначних чисел:

4 = 1 +3, 6 = 1 +5, 8 = 1 +7, 10 = 3 +7, 12 = 5 +7, 14 = 3 +11,

16 = 3 +13, 18 = 5 +13, 20 = 3 +17, 22 = 11 +11, 24 = 11 +13,

26 = 13 +13, 28 = 23 +5, 30 = 23 +7, 32 = 19 +13, 34 = 17 +17,

36 = 17 +19, 38 = 19 +19, 40 = 37 +3, 42 = 37 +5, 44 = 37 +7,

46 = 23 +23, 48 = 47 +1, 50 = 47 +3, 52 = 47 +5, 54 = 47 +7,

56 = 53 +3, 58 = 53 +5, 60 = 53 +7, 62 = 31 +31, 64 = 61 +3,

66 = 61 +5, 68 = 61 +7, 70 = 67 +3, 72 = 67 +5, 74 = 37 +37,

76 = 73 +3, 78 = 73 +5, 80 = 73 +7, 82 = 41 +41, 84 = 41 = 43,

86 = 43 +43, 88 = 87 +1, 90 = 87 +3, 92 = 87 +5,94 = 87 +7,

96 = 89 +7, 98 = 97 +1.

Про своє спостереження Гольдбах написав великому математику XVIII століття Леонарду Ейлеру, який був членом Петербурзької академії наук. Перевіривши ще багато парних чисел, Ейлер переконався, що всі вони є сумами двох простих чисел. Але парних чисел нескінченно багато. З цього обчислення Ейлера давали надію на те, що властивість, що помітив Гольдбах, мають всі числа. Проте спроби довести, що це завжди буде так, ні до чого не привели.

Двісті років математики міркували над проблемою Гольдбаха. І тільки радянському вченому Івану Матвійовичу Виноградову вдалося зробити вирішальний крок. Він встановив, що будь-яке досить велике натуральне число є сумою трьох простих чисел. Але число, починаючи з якого вірне твердження Виноградова, неймовірно велике. За цим поки що, на жаль, немає надії навіть за допомогою самих кращих ЕОМ перевірити, чи є вірним це твердження для всіх інших чисел.



II. ФУНКЦІЯ

1. Функція . Теорема Ейлера

Функція - функція, яка визначає кількість простих чисел на деякому проміжку.

Теорема Ейлера. При зростанні х до відношення прямує до нуля

Справді, з нерівностей (4) дістаємо

А звідси, оскільки

У першій сотні натуральних чисел міститься 25 простих чисел, тобто прості числа становлять 25%. У першій тисячі натуральних чисел є 169 простих чисел (16,9%); серед перших десяти тисяч натуральних чисел є 1229 простих чисел (12,29%); серед перших ста тисяч натуральних чисел 9522 простих числа (9,592%). Таблиці простих чисел показують, що при зростанні х процент простих чисел на відрізку [1, х] зменшується. Проте цей факт сам по собі не виключає того, що при як завгодно великому х прості числа, що належать відрізку [1, х], все-таки становлять не менш ніж, наприклад, 0,0000001% від числа всіх натуральних чисел відрізка [1, х]. Теорема Ейлера свідчить про те, що цього не може бути: при зростанні х до «середня щільність» простих чисел на відрізок [1, х] стає меншою від будь-якого числа > 0.

натуральний число теорема проміжок

2. Асимптотичний закон розподілу простих чисел

Нерівності Чебишова вперше дали змогу судити про характер зростання функції р(х) при зростанні х. Результати Чебишова в дослідженні функції р(х) привели математиків до висновку, що при х> відношення р(х) : прямує до 1. Як зазначалось вище, Чебишов довів, що коли при х> границя відношення р(х) : існує, то вона дорівнює 1. Проте довести існування цієї границі Чебишов не зміг. У 1881 р. англійському математикові Сільвестру вдалося вмістити відношення р(х) : у більш тісні межі:

0,95695 < р(х) : < 1,04423

А в 1896 р. французький математик Адамар і бельгійський математик Валле Пуссен за допомогою апарата теорії функцій комплексної змінної незалежно один від одного довели існування границі відношення р(х) : . Таким чином, було доведено, що

Якщо при х > відношення додатних функцій f(x) і g(x), визначених для дійсних додатних значень х, прямує до 1, тобто то функції f(x) і g(x) називають асимптотично рівними і записують f(x) g(x).

Отже, р(х) .

Теорему про те, що називають асимптотичним законом розподілу простих чисел. Адамар і Валле Пуссен, власне, довели, що



р(х)

Дослідження Рімана, Адамаре і Валле Пуссена показали, що за величиною абсолютної похибки функція дає більш точне наближення до р(х), ніж .

Із встановленням асимптотичного закону розподілу простих чисел дослідження характеру зростання функції р(х) не припинилися. Дальші зусилля математиків були спрямовані на якомога точнішу оцінку модуля різниці між р(х) і істотних результатів в цьому напрямку досягли радянські математики М. Г. Чудаков, І. М. Виноградов, М. М. Коробов.

Вище ми зазначали, що при доведенні асимптотичного закону розподілу простих чисел Адамар і Валле Пуссен використовували зовнішні для теорії чисел методи теорії функцій комплексної змінної. Сам же асимптотичний закон належить виключно до натуральних чисел. Тому математикам здавалося природним шукати таке доведення цього закону, в якому не використовувалися б сторонні для теорії чисел ідеї. Пошуки такого доведення успішно закінчилися порівняно недавно: у 1949 р. норвезький математик А. Сальберг і угорський математик II. Ердеш опублікували доведення асимптотичного закону, в якому вони оперували тільки з натуральними числами.

3. Таблиці Гаусса

Ми вже знаємо, що перший десяток вміщує в собі чотири простих числа (2, 3, 5, 7). В першій сотні міститься 25 простих чисел. Для визначення цієї кількості Гаусс ввів відому нам наступну функцію . Символ, який використовується в цій формулі, більш відоме як число пі, але в даному контексті він не має цього математичного змісту. Потім Гаусс побудував таблицю з двома стовпчиками. В лівому він записав степені числа 10, а в правому - значення функції .

Зрозуміло, що число буде збільшуватися, але як саме, ми не знаємо. Додамо до таблиці ще один стовпчик, що показує частку простих чисел, менших заданого числа. Для цього вирахуємо відношення .

Ми знаємо, що є 168 простих чисел, менших 1000. Їх частку становить

Це число говорить нам, що 16,8% чисел між 1 і 1000 є простими. Інші 83,2% являють собою складені числа. Додамо цей третій стовпчик в таблицю.

Ми бачимо, що доля простих чисел зменшується. Це важливий, хоч і досить передбачуваний факт. Число є простим, коли воно не ділиться на жодне число з тих, які підуть перед ним. Наприклад, щоб число 11 було простим, воно не повинно ділитися ні на 2, 3, 4, 5, 6, 7, 8, 9, ні на 10. Але Гаусс, звичайно, не думав, що звідси випливає, що прості числа в кінці кінців, закінчаться, так як прекрасно знав про існування основної теореми алгебри, за допомогою якої Евклід довів, що кількість простих чисел нескінченна.

У Гаусса третій стовпчик таблиці містив не значення , а обернені їм .

На цій таблиці видно, що, наприклад, серед перших ста чисел одне із чотирьох - просте, а в першій тисячі - одне із шести, і так далі. Це звичайно приблизна оцінка. Таблиця не гарантує, що серед першої сотні кожне четверте число - просте, що можна легко перевірити за допомогою решета Ератосфена. Таким чином, наведена вище таблиця лише вказує приблизну вірогідну відстань між простими числами.



ВИСНОВКИ

В ході даної роботи я розглянув та вивчив основні властивості простих чисел аналізуючи доступні мені джерела, розглянув деякі приклади застосування теорем, алгоритмів для пошуку простих чисел.

Основними властивостями простих чисел є:

- Множина простих чисел нескінченна;

- Будь - яке натуральне число більше 1 можна представити у вигляді добутку простих чисел і таке представлення є єдиним з точністю до порядку множників.

- Якщо р - просте, і аb ділиться на р, то а ділиться на р або b ділиться на р.

- Будь-яке натуральне число n більше 1 ділиться хоча б на одне просте число.

- Якщо р - просте число і якщо і відомо, що рn, n=p або n=-p.

Також ознайомився з властивостями чисел Мерсенна:

- Будь-який дільник числа для простого p має вигляд 2pk+1, де k -- ціле число.

- Кожне парне досконале число має вигляд , де число Мерсенна є простим.

Викладений матеріал може бути використаний при вивченні курсу алгебри та теорії чисел, зокрема при розв'язанні математичних задач та як основа для спецкурсів(розрахованих на магістрантів та студентів старших курсів).

Також не малопомітним було те, що прості числа мають багато цікавих властивостей. Наприклад, різниця деяких простих чисел дорівнює 2, тому вони будуть числами-близнятами. Прості числа становлять одну із найважливіших тем, яка повертає нас до самого початку математики, а потім, по мірі зростання важкості, приводять на край сучасної науки. Окрім того, що прості числа становлять з себе одну з найцікавіших тем математики, вони дуже корисні в нашому житті. На їхніх властивостях побудовані секретні коди, які захищають електронну пошту, банківські операції, кредитні картки і мобільний телефонний зв'язок.

Прості числа досліджували багато вчених - математиків, вони хотіли віднайти формулу, завдяки якої могли згенерувати прості числа, але жодному не вдалося. Можна сказати, що пошук простих чисел, пошук формули, щоб згенерувати їх - як шкідливий вірус, якщо він захвачує розум математика, то його дуже важко викоренити. Історію простих чисел порівнюють з історією поразок і невдач, але прекрасних невдач, які привели до появи нових теорій, свіжих поглядів і передових рубежів.

Також прості числа важливі не лише в криптографії (банківські операції, кредитні картки, електронна пошта, мобільний телефонний зв'язок), а й самому житті. Вони відграють велику роль у характері людини, особливостях її долі, ставленні до навколишнього світу, суспільства.

Велику роль прості числа займають і в різних прислів'ях, приказках, повір'ях та казках, в яких величезної популярності здобули числа 2, 3, 7 і 13.

Вивчення простих чисел потрібні для розв'язування різноманітних задач, які часто трапляються в завданнях олімпіад, конкурсів та вікторин.

Піфагор був правий: « Світом керують числа».



СПИСОК ДЖЕРЕЛ

1. Алгебра и начала анализа: Учебн. для 10--11 кл. общ. учредж. / Под ред.А. Н. Колмогорова. -- 12-е изд.-- М.: Просвещение, 2002. -- 384 с.

2. Маслова Т. Н., Суходений А. М. Ваш домашний репетитор. -- М.: ООО «Изд. дом “ОНИКС 21 век”», 2003. -- 672 с.

3. Амелькин В. Задачи з параметром. -- Минск, 1994.

4. Вишенський В. А., Перестюк М. О., Самойленко А. М. Збірник задач з математики: Навч. посібник. -- 2-ге вид., доп. -- К.: Либідь, 1993. -- 344 с.

5. Чайковський М. А. Квадратні рівняння. -- К., 1970. -- 242 с.

6. Гусак Г. М., Капуцкая Д. А. Математика для подготовительных отделений вузов: Справ. пособие / Под ред. А. А. Гусака. -- Мн.: Высш. шк., 1989. -- 495 с.

7. Математика для поступающих в экономические вузы: Уч. пос. для вузов / Под ред. проф. Н. М. Кремера. -- 2-ге изд., перераб. и доп. -- М.: ЮНИТИ, 1998. -- 430 с.

8. Мордкович А. Г. Наибольшее и наименьше значения величин. -- М.: Школа-Пресс, 1995. -- 144 с.

9. Маслай Г. С., Шоголева Л. О. Рівняння та системи рівнянь з параметрами: Математика. № 21--22 (81--82), Червень 2000.

10. Саушкін О. Ф. Розв'язування алгебраїчних рівнянь. -- К.: КНЕУ.

Лурьве М. В., Александров Б. И. Задачи на составление уравнений: Учеб. на составление уравнений: Учеб. рук-во. -- 3-е изд., перераб. -- М.: Наука, 1990. -- 96 с.



ДОДАТКИ

Додаток A

Приклад перевірки простоти числа:

Чи є число 43 простим?

1спосіб: перевіряємо число 43 на подільність числами від 2 до 42.

2спосіб: перевіряємо число 43 на подільність числами від 2 до 7 (округлений корінь числа 42=7)

Як бачимо в першому випадку кількість дій 41, а в другому 6. При збільшенні числа кількість дій буде ще більше різнитися. Тому раціонально буде використати 2 спосіб для програмування цієї задачі.

Складена програма, яка визначить чи є вказане число простим:

Код Pascal

program proste;

var chislo,korin,i:integer;vidpovid:string[3];

BEGIN

writeln(`Введіть ціле число більше 2');

readln(chislo); { chislo - це змінна в яку запишемо введене значення}

korin:=round(sqrt(chislo)); { round - це функція, яка округлює значення параметру, що записаний в дужках}

for i:=2 to korin do { перевіряємо на проміжку від 2 до кореня..}

begin {..введеного числа чи є дільник вказаного числа серед них }

if chyslo mod i=0 then

begin

vidpovid:='no';

break;

end;

end;

if vidpovid='no' then

writeln(Число,'- не просте')

else

writeln(Число,'- просте');

readln;

END.



Додаток В

Таблиця 1

х
10	4
100	25
1000	168
10000	1229
100000	9592
1000000	78498
10000000	664579
100000000	5761455
1000000000	50847534
10000000000	455052512

Таблиця 2

х		/х
10	4	0,4
100	25	0,25
1000	168	0,168
10000	1229	0,1229
100000	9592	0,09592
1000000	78498	0,078498
10000000	664579	0,0664579
100000000	5761455	0,05761455
1000000000	50847534	0,05084753
10000000000	455052512	0,04550525

Таблиця 3

х		х?р(х)
10	4	2,5
100	25	4
1000	168	6
10000	1229	8,1
100000	9592	10,4
1000000	78498	12,7
10000000	664579	15
100000000	5761455	17,4
1000000000	50847534	19,7
10000000000	455052512	22

Размещено на Allbest.ru