Курсовая работа: Властивості простих чисел

Виникнення чисел у житті не випадковість. Важко уявити собі спілкування без використання чисел. Історія чисел захоплююча й загадкова. Людство встановило низку законів і закономірностей світу чисел.

Дата добавления на сайт: 19 февраля 2025
Зміст

ВСТУП.ПРОСТІ ЧИСЛА
.Означення простого та взаємно-простого числа. Деякі теореми про прості числа
. Нескінченість множини простих чисел. Решето Ератосфена
.Основна теорема арифметики
. Прості числа-близнята
.Прості числа Мерсенна
.Найпростіші та суперпрості числа
. Визначення великих простих чисел
. Дружба чисел
. Проблема Гольдбаха
II. ФУНКЦІЯ . Теорема Ейлера
1. Функція . Теорема Ейлера
2. Асимптотичний закон розподілу простих чисел
. Таблиці Гаусса
ВИСНОВКИ
СПИСОК ДЖЕРЕЛ
Додатки

ВСТУП

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

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

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

Взаємно прості числа - натуральні або цілі числа, які не мають спільних дільників більших за 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 було числом складеним, то воно мало б дільник q1, такий, що 1 1. Тому воно або само просте, або за теоремою 3 ділиться на просте число, відмінне від кожного з чисел p1, p2, ..., рп Звідси випливає, що існує принаймні одне просте число, відмінне від чисел p1, p2, ..., рп а це суперечить нашому припущенню. Отже, наше припущення неправильне. Цим теорему доведено. Природно постає запитання: як у ряду натуральних чисел виділити всі прості числа?
Таблицю всіх простих чисел, що не перевищують даного натурального числа 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 в ряд:
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 (тобто кожне друге, починаючи з 22 = 4 ):
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 (тобто кожне третє, починаючи з 32 = 9 ):
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 (тобто кожне п\'яте, починаючи з 2 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 2 ≤ n . У результаті всі складені числа будуть закреслені, а не закресленими залишаться всі прості числа. Для n=30 вже після закреслення кратних числу 5 всі складені числа виходять закресленими:
3 5 7 11 13 17 19 23 29
Отримали всі прості числа на даному проміжку.
Алгоритм пошуку простих чисел висіюванням
Для знаходження всіх простих чисел не більше заданого числа n, дотримуючись методу Ератосфена, потрібно виконати наступні кроки:
)Виписати підряд всі цілі числа від 2 до n (2,3,4 ..., n)
)Нехай змінна p спочатку дорівнює 2 - першому простому числу.
)Викреслити зі списку всі числа від 2 p до n, що діляться на p (тобто, числа 2 p, 3 p, 4 p, ....)
)Знайти перше не викреслене число, більше, ніж р, і привласнити значенням змінної p це число.
)Повторювати кроки 3 та 4 до тих пір, поки p не стане більше, ніж n.
)Всі не викреслені числа у списку - прості числа.
На практиці, алгоритм можна трохи покращити таким чином:
На кроці № 3, числа можна викреслювати, починаючи відразу з числа p2 , тому що всі складові числа менше нього вже будуть викреслені до цього часу. І, відповідно, зупинити алгоритм можна, коли p2 стане більше, ніж n.

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

Доведемо тепер теорему, яка відіграє фундаментальну роль як у теорії подільності, так і в усій теорії чисел, її називають основною теоремою арифметики.
Теорема 6. (Основна теорема арифметики). Кожне відмінне від 1 натуральне число π можна записати у вигляді добутку простих чисел і притому єдиним способом, якщо не брати до уваги порядок розміщення співмножників.
Доведемо спочатку можливість запису натурального числа q ≠ 1 у вигляді добутку простих чисел. Для натурального числа 2 це можливо, бо число 2 просте, тобто його можна вважати добутком простих чисел з числом співмножників, що дорівнює одиниці. Припустимо, що це можливо для всякого натурального числа k, такого, при якому 2 0.
натуральний число теорема проміжок
2. Асимптотичний закон розподілу простих чисел

Нерівності Чебишова вперше дали змогу судити про характер зростання функції π(х) при зростанні х. Результати Чебишова в дослідженні функції π(х) привели математиків до висновку, що при х→Ґ відношення π(х) : прямує до 1. Як зазначалось вище, Чебишов довів, що коли при х→Ґ границя відношення π(х) : існує, то вона дорівнює 1. Проте довести існування цієї границі Чебишов не зміг. У 1881 р. англійському математикові Сільвестру вдалося вмістити відношення π(х) : у більш тісні межі:
0,95695 p має вигляд 2pk+1, де k - ціле число .
Кожне парне досконале число має вигляд , де число Мерсенна є простим.
Викладений матеріал може бути використаний при вивченні курсу алгебри та теорії чисел, зокрема при розв’язанні математичних задач та як основа для спецкурсів(розрахованих на магістрантів та студентів старших курсів).
Також не малопомітним було те, що прості числа мають багато цікавих властивостей. Наприклад, різниця деяких простих чисел дорівнює 2, тому вони будуть числами-близнятами. Прості числа становлять одну із найважливіших тем, яка повертає нас до самого початку математики, а потім, по мірі зростання важкості, приводять на край сучасної науки. Окрім того, що прості числа становлять з себе одну з найцікавіших тем математики, вони дуже корисні в нашому житті. На їхніх властивостях побудовані секретні коди, які захищають електронну пошту, банківські операції, кредитні картки і мобільний телефонний зв’язок.
Прості числа досліджували багато вчених - математиків, вони хотіли віднайти формулу, завдяки якої могли згенерувати прості числа, але жодному не вдалося. Можна сказати, що пошук простих чисел, пошук формули, щоб згенерувати їх - як шкідливий вірус, якщо він захвачує розум математика, то його дуже важко викоренити. Історію простих чисел порівнюють з історією поразок і невдач, але прекрасних невдач, які привели до появи нових теорій, свіжих поглядів і передових рубежів.
Також прості числа важливі не лише в криптографії (банківські операції, кредитні картки, електронна пошта, мобільний телефонний зв’язок), а й самому житті. Вони відграють велику роль у характері людини, особливостях її долі, ставленні до навколишнього світу, суспільства.
Велику роль прості числа займають і в різних прислів’ях, приказках, повір’ях та казках, в яких величезної популярності здобули числа 2, 3, 7 і 13.
Вивчення простих чисел потрібні для розв’язування різноманітних задач, які часто трапляються в завданнях олімпіад, конкурсів та вікторин.
Піфагор був правий: « Світом керують числа».

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

1.Алгебра и начала анализа: Учебн. для 10-11 кл. общ. учредж. / Под ред.А. Н. Колмогорова. - 12-е изд.- М.: Просвещение, 2002. - 384 с.
.Маслова Т. Н., Суходений А. М. Ваш домашний репетитор. - М.: ООО «Изд. дом “ОНИКС 21 век”», 2003. - 672 с.
.Амелькин В. Задачи з параметром. - Минск, 1994.
.Вишенський В. А., Перестюк М. О., Самойленко А. М. Збірник задач з математики: Навч. посібник. - 2-ге вид., доп. - К.: Либідь, 1993. - 344 с.
.Чайковський М. А. Квадратні рівняння. - К., 1970. - 242 с.
.Гусак Г. М., Капуцкая Д. А. Математика для подготовительных отделений вузов: Справ. пособие / Под ред. А. А. Гусака. - Мн.: Высш. шк., 1989. - 495 с.
.Математика для поступающих в экономические вузы: Уч. пос. для вузов / Под ред. проф. Н. М. Кремера. - 2-ге изд., перераб. и доп. - М.: ЮНИТИ, 1998. - 430 с.
.Мордкович А. Г. Наибольшее и наименьше значения величин. - М.: Школа-Пресс, 1995. - 144 с.
.Маслай Г. С., Шоголева Л. О. Рівняння та системи рівнянь з параметрами: Математика. № 21-22 (81-82), Червень 2000.
.Саушкін О. Ф. Розв’язування алгебраїчних рівнянь. - К.: КНЕУ.
Лурьве М. В., Александров Б. И. Задачи на составление уравнений: Учеб. на составление уравнений: Учеб. рук-во. - 3-е изд., перераб. - М.: Наука, 1990. - 96 с.

ДОДАТКИ

Додаток A

Приклад перевірки простоти числа:
Чи є число 43 простим?
спосіб: перевіряємо число 43 на подільність числами від 2 до 42.
спосіб: перевіряємо число 43 на подільність числами від 2 до 7 (округлений корінь числа 42=7)
Як бачимо в першому випадку кількість дій 41, а в другому 6. При збільшенні числа кількість дій буде ще більше різнитися. Тому раціонально буде використати 2 спосіб для програмування цієї задачі.
Складена програма, яка визначить чи є вказане число простим:

Код Pascalproste;chislo,korin,i:integer;vidpovid:string[3];
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;.

Додаток В

Таблиця 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

Комментарии:

Вы не можете оставлять комментарии. Пожалуйста, зарегистрируйтесь.