Простым числом является натуральное число, которое делится только на себя и на единицу.
Остальные числа называют составными.
Простые натуральные числа
Но не все натуральные числа являются простыми числами.
Простыми натуральными числами являются лишь те из них, которые делятся только на себя и на единицу.
Примеры простых чисел:
2; 3; 5; 7; 11; 13;...
Простые целые числа
Из следует, что простыми числами являются только натуральные числа.
Это значит, что простые числа обязательно являются натуральными.
Но все натуральные числа являются одновременно целыми числами.
Таким образом, все простые числа являются целыми.
Примеры простых чисел:
2; 3; 5; 7; 11; 13; 17; 19; 23;...
Четные простые числа
Имеется только одно четное простое число - это число два.
Все остальные простые числа нечетные.
А почему не может быть простым числом четное число больше двух?
А потому, что любое четное число больше двух будет делиться на себя, не единицу и на два, т.е такое число всегда будет иметь три делителя, а возможно и больше.
Разделение натуральных чисел на простые и составные приписывают древнегреческому математику Пифагору. И если следовать Пифагору, то множество натуральных чисел можно разбить на три класса: {1} – множество, состоящее из одного числа – единицы; {2, 3, 5, 7, 11, 13, } – множество простых чисел; {4, 6, 8, 9, 10, 12, 14, 15, } – множество составных чисел.
Много различных загадок таит второе множество. Но сначала, давайте разберемся, что такое есть простое число. Открываем «Математический энциклопедический словарь» (Ю. В. Прохоров, издательство «Советская энциклопедия», 1988) и читаем:
«Простое число – целое положительное число, большее единицы, не имеющее других делителей, кроме самого себя и единицы: 2,3,5,7,11,13,
Понятие простого числа является основным при изучении делимости натуральных чисел; именно, основная теорема арифметики утверждает, что всякое целое положительное число, кроме 1, единственным образом разлагается в произведение простых чисел (порядок сомножителей при этом не принимается во внимание). Простых чисел бесконечно много (это предложение, названное теоремой Евклида, было известно еще древнегреческим математикам, его доказательство имеется еще в кн. 9 «Начал» Евклида). П. Дирихле (1837) установил, что в арифметической прогрессии a+bx при х=1. ,2,с с целыми взаимно простыми а и b также содержится бесконечно много простых чисел.
Для нахождения простых чисел от 1 до х служит известный с 3 в. до н. э. метод решета Эратосфена. Рассмотрение последовательности (*) простых чисел от 1 до х показывает, что с увеличением х она становится в среднем более редкой. Существуют сколь угодно длинные отрезки ряда натуральных чисел, среди которых нет ни одного простого числа (Теорема 4). В то же время встречаются такие простые числа, разность между которыми равна 2 (т. н. близнецы). До сих пор (1987) неизвестно, конечно или бесконечно множество таких близнецов. Таблицы простых чисел, лежащих в пределах первых 11 миллионов натуральных чисел, показывают наличие весьма больших близнецов (например, 10 006 427 и 10 006 429).
Выяснение распределения простых чисел в натуральном ряде чисел является весьма трудной задачей теории чисел. Она ставится как изучение асимптотического поведения функции, обозначающей количество простых чисел, не превосходящих положительного числа х. Из теоремы Евклида ясно, что при. Л. Эйлер в 1737 ввел дзета-функцию.
Он же доказал, что при
Где суммирование проводится по всем натуральным числам, а произведение берется по всем простым. Это тождество и его обобщения играют фундаментальную роль в теории распределения простых чисел. Исходя из этого, Л. Эйлер доказал, что ряд и произведение по простым р расходятся. Более того, Л. Эйлер установил, что простых чисел «много», ибо
И в то же время, почти все натуральные числа являются составными, так как при.
и, при любых (т. е. что растет, как функция). Хронологически следующим значительным результатом, уточняющим теорему Чебышева, является т. н. асимптотический закон распределения простых чисел (Ж. Адамар, 1896, Ш. Ла Валле Пуссен, 1896), заключавшийся в том, что предел отношения к равен 1. В дальнейшем значительные усилия математиков направлялись на уточнение асимптотического закона распределения простых чисел. Вопросы распределения простых чисел изучаются и элементарными методами, и методами математического анализа».
Здесь имеет смысл привести доказательство некоторых теорем, приведенных в статье.
Лемма 1. Если НОД(a, b)=1, то существуют целые числа x, y такие, что.
Доказательство. Пусть a и b взаимно простые числа. Рассмотрим множество J всех натуральных чисел z, представимых в виде, и выберем в нем наименьшее число d.
Докажем, что а делится на d. Разделим а на d с остатком: и пусть. Поскольку, оно имеет вид, следовательно,
Мы видим, что.
Поскольку мы предположили, что d – наименьшее число в J, получили противоречие. Значит, а делится на d.
Точно также докажем, что b делится на d. Значит, d=1. Лемма доказана.
Теорема 1. Если числа а и b взаимно просты и произведение bx делится на а, то х делится на а.
Доказательство1. Мы должны доказать, что ах делится на b и НОД(a,b)=1, то х делится на b.
По лемме 1, существуют x, y такие, что. Тогда, очевидно, делится на b.
Доказательство 2. Рассмотрим множество J всех натуральных чисел z таких, что zc делится на b. Пусть d – наименьшее число в J. Легко видеть, что. Аналогично доказательству леммы 1 доказывается, что а делится на d и b делится на d
Лемма 2. Если числа q,p1,p2,pn – простые и произведение делится на q, то одно из чисел pi равно q.
Доказательство. Прежде всего, заметим, что если простое число р делится на q, то p=q. Отсюда сразу следует утверждение леммы для n=1. Для n=2 оно вытекает прямо из теоремы 1: если р1р2 делится на простое число q и, то р2 делится на q(т. е).
Доказательство леммы для n=3 проведем так. Пусть р1 р2 р3 делится на q. Если р3 =q, то все доказано. Если, то согласно теореме 1, р1 р2 делится на q. Таким образом, случай n=3 мы свели к уже рассмотренному случаю n=2.
Точно также от n=3 мы можем перейти n=4, затем к n=5, и вообще, предполагая, что n=k утверждение леммы доказано, мы можем легко доказать его для n=k+1. Это убеждает нас, что лемма верна для всех n.
Основная теорема арифметики. Каждое натуральное число разлагается на простые множители единственным образом.
Доказательство. Предположим, что имеется два разложения числа а на простые множители:
Так как правая часть делится на q1, то и левая часть равенства должна делиться на q1. Согласно лемме 2, одно из чисел равно q1. Сократим обе части равенства на q1.
Проведем такое же рассуждение для q2, затем для q3, для qi. В конце концов, справа сократятся все множители и останется 1. Естественно, и слева не останется ничего, кроме единицы. Отсюда мы заключаем, что два разложения и могут различаться только порядком сомножителей. Теорема доказана.
Теорема Евклида. Ряд простых чисел бесконечен.
Доказательство. Предположим, что ряд простых чисел конечен, и обозначим последнее простое число буквой N. Составим произведение
Прибавим к нему 1. Получим:
Это число, будучи целым, должно содержать хотя бы один простой множитель, т. е. должно делиться хотя бы на одно простое число. Но все простые числа, по предположению, не превосходят N, число же M+1 не делится без остатка ни на одно из простых чисел, меньших или равных N, - всякий раз получится остаток 1. Теорема доказана.
Теорема 4. Участки составных чисел между простыми бывают любой длины. Мы сейчас докажем, что ряд состоит из n последовательных составных чисел.
Числа эти идут непосредственно друг за другом в натуральном ряду, так как каждое следующее на 1 больше предыдущего. Остается доказать, что все они составные.
Первое число
Четное, так как оба его слагаемых содержат множитель 2. А всякое четное число, большее 2, - составное.
Второе число состоит из двух слагаемых, каждое из которых кратно 3. Значит, это число составное.
Подобным же образом устанавливаем, что следующее число кратно 4 и т. д. Иначе говоря, каждое число нашего ряда содержит множитель, отличный от единицы и его самого; оно является, следовательно, составным. Теорема доказана.
Изучив доказательства теорем, продолжим рассмотрение статьи. В ее тексте был упомянут метод решета Эратосфена как способ нахождения простых чисел. Прочтем об этом методе из того же словаря:
«Эратосфена решето – метод, разработанный Эратосфеном и позволяющий отсеивать составные числа из натурального ряда. Сущность решета Эратосфена заключается в следующем. Зачеркивается единица. Число два – простое. Зачеркиваются все натуральные числа, делящиеся на 2. Число 3 – первое незачеркнутое число будет простым. Далее зачеркиваются все натуральные числа, которые делятся на 3. Число 5 – следующее незачеркнутое число – будет простым. Продолжая аналогичные вычисления, можно найти сколь угодно длинный отрезок последовательности простых чисел. Решето Эратосфена как теоретический метод исследования теории чисел развит В. Бруном (1919).
Вот наибольшее число, о котором в настоящее время известно, что оно просто:
Это число имеет около семисот десятичных знаков. Вычисления, с помощью которых было установлено, что это число является простым, проводилось на современных вычислительных машинах.
«Дзета-функция Римана, -функция, - аналитическая функция комплексного переменного, при σ>1 определяемая абсолютно и равномерно сходящимся рядом Дирихле:
При σ>1 справедливо представление в виде произведения Эйлера:
(2) где р пробегает все простые числа.
Тождественность ряда (1) и произведения (2) представляет собой одно из основных свойств дзета-функции. Оно позволяет получить различные соотношения, связывающие дзета-функцию с важнейшими теоретико-числовыми функциями. Поэтому дзета-функция играет большую роль в теории чисел.
Дзета-функция была введена как функция действительного переменного Л. Эйлером (1737, опубл. 1744), который указал ее расположение в произведение (2). Затем дзета-функция рассматривалась П. Дирихле и особенно успешно П. Л. Чебышевым в связи с изучением закона распределения простых чисел. Однако наиболее глубокие свойства дзета-функции были обнаружены после работ Б. Римана, впервые в 1859 рассмотревшего дзета-функцию как функцию комплексного переменного, им же введено название «дзета-функция» и обозначение «»».
Но возникает вопрос: какое практическое применение существует для всех этих работ о простых числах? Действительно, почти никакого применения для них нет, но существует одна область, где простые числа и их свойства применяются по сей день. Это – криптография. Здесь простые числа применяются в шифровальных системах без передачи ключей.
К сожалению, это все, что известно о простых числах. Также остается еще множество загадок. Например, неизвестно, бесконечно ли множество простых чисел, представимых как два квадрата.
«НЕПРОСТЫЕ ПРОСТЫЕ ЧИСЛА».
Я решил провести небольшие исследования с целью нахождения ответов на некоторые вопросы о простых числах. Прежде всего, мною была составлена программа, которая выдает все последовательные простые числа, меньшие 1 000 000 000 Кроме этого была составлена программа, определяющая, является ли введенное число простым. Для изучения проблем простых чисел мною был построен график, отмечающий зависимость величины простого числа от порядкового номера В качестве дальнейшего плана исследования я решил воспользоваться статьей И. С. Зельцера и Б. А. Кордемского «Занятные стайки простых чисел». Авторы выделили следующие пути исследования:
1. 168 мест первой тысячи натуральных чисел занимают простые числа. Из них 16 чисел – палиндромические – каждое равно обращенному:11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929.
Четырехзначных простых чисел всего 1061, и ни одно из них не является палиндромическим.
Пятизначных простых палиндромических чисел много. В их составе такие красавцы: 13331, 15551, 16661, 19991. Несомненно, есть стайки и такого вида: ,. Но сколько же экземпляров в каждой такой стайке?
3+х+х+х+3 = 6+3х = 3(2+х)
9+х+х+х+9 = 18+3х =3(6+х)
Видно, что сумма цифр чисел и делится на 3, следовательно эти числа сами тоже делятся на 3.
Что касается чисел вида, то среди них простыми являются числа 72227, 75557, 76667, 78887, 79997.
2. В первой тысяче чисел есть пять «квартетов», состоящих из подряд идущих простых чисел, последние цифры которых образуют последовательность 1, 3, 7, 9: (11, 13, 17, 19), (101, 103, 107, 109), (191, 193, 197, 199), (211, 223, 227, 229), (821, 823, 827, 829).
Сколько же таких квартетов есть среди n-значных простых чисел при n›3?
С помощью написанной мною программы был найден квартет, пропущенный авторами: (479, 467, 463, 461) и квартеты для n = 4, 5, 6. При n = 4 существуют 11 квартетов
3. Стайка из девяти простых чисел: 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879 – привлекательна не только тем, что она представляет собой арифметическую прогрессию с разностью 210, но и способностью разместиться в девяти клетках так, что образуется магический квадрат с константой, равной разности двух простых чисел: 3119 – 2:
Следующий, десятый член рассматриваемой прогрессии 2089 – также простое число. Если удалить из стайки число 199, но включить 2089, то и в этом составе стайка может образовать магический квадрат – тема для поиска.
Следует отметить, что существуют и другие магические квадраты, состоящие из простых чисел:
1847 6257 6197 3677 1307 1877 2687
2267 1427 5987 5927 1667 2027 4547
2897 947 2357 4517 3347 5867 3917
3557 4157 4397 3407 2417 2657 3257
4337 5717 3467 2297 4457 1097 2477
4817 4767 827 887 5147 5387 1997
4127 557 617 3137 5507 4937 4967
Предлагаемый квадрат любопытен поскольку
1. Он является магическим квадратом 7х7;
2. Он содержит в себе магический квадрат 5х5;
3. Магический квадрат 5х5 содержит в себе магический квадрат 3х3;
4. Все эти квадраты имеют одно общее центральное число – 3407;
5. Все 49 чисел, входящие в квадрат 7х7, оканчиваются цифрой 7;
6. Все 49 чисел, входящие в квадрат 7х7, - простые числа;
7. Каждое из 49 чисел, входящих в квадрат 7х7, представимо в виде 30n + 17.
Использованные программы были написаны мной на языке программирования Dev-С++ и их тексты я привожу в приложении (см. файлы с расширением. срр). Кроме всего перечисленного, я написал программу, раскладывающую последовательные натуральные числа на простые множители (см. Делители 1. срр) и программу, которая раскладывает на простые множители только введенное число (см. Делители 2. срр). Поскольку эти программы в скомпилированном виде занимают слишком много места, то приведены только их тексты. Однако все желающие могут скомпилировать их при наличии подходящей программы.
БИОГРАФИИ УЧЕНЫХ, ЗАНИМАВШИХСЯ ПРОБЛЕМОЙ ПРОСТЫХ ЧИСЕЛ
ЕВКЛИД(EUCLIDES)
(около 330 до н. э. – около 272 до н. э.)
О жизни самого знаменитого математика Античности сохранилось очень мало достоверных сведений. Полагают, что он учился в Афинах, чем и объясняется его блестящее владение геометрией, разработанной школой Платона. Однако, судя по всему, он не был знаком с трудами Аристотеля. Преподавал в Александрии, где заслужил высокую оценку своей педагогической деятельностью во время царствования Птолемея I Сотера. Существует предание о том, что этот царь потребовал открыть ему способ достижения быстрых успехов в математике, на что Евклид ответил, что в геометрии нет царских путей (аналогичную историю, впрочем, также рассказывают про Менхема, которого якобы о том же спросил Александр Великий). Традиция сохранила воспоминание о Евклиде как о благожелательном и скромном человеке. Евклид – автор трактатов на различные темы, но его имя ассоциируется главным образом с одним из трактатов, носящим название «Начала». Речь в нем идет о собрании работ математиков, трудившихся до него (известнейшим из них был Гиппократ из Коса), результаты которых он довел до совершенства благодаря своей способности к обобщению и трудолюбию.
ЭЙЛЕР(EULER) ЛЕОНАРД
(Базель, Швейцария 1707 – Санкт-Петербург, 1783)
Математик, механик и физик. Родился в семье небогатого пастора Пауля Эйлера. Образование получил сначала у отца, а в 1720–24 в Базельском университете, где слушал лекции по математике И. Бернулли.
В конце 1726 Эйлер был приглашен в Петербургскую АН и в мае 1727 приехал в Петербург. В только что организованной академии Эйлер нашёл благоприятные условия для научной деятельности, что позволило ему сразу же приступить к занятиям математикой и механикой. За 14 лет первого петербургского периода жизни Эйлер подготовил к печати около 80 трудов и опубликовал свыше 50. В Петербурге он изучил русский язык.
Эйлер участвовал во многих направлениях деятельности Петербургской АН. Он читал лекции студентам академического университета, участвовал в различных технических экспертизах, работал над составлением карт России, написал общедоступное «Руководство к арифметике» (1738–40). По специальному поручению академии Эйлер подготовил к печати «Морскую науку» (1749) – фундаментальный труд по теории кораблестроения и кораблевождения.
В 1741 Эйлер принял предложение прусского короля Фридриха II переехать в Берлин, где предстояла реорганизация АН. В Берлинской АН Эйлер занял пост директора класса математики и члена правления, а после смерти её первого президента П. Мопертюи несколько лет (с 1759) фактически руководил академией. За 25 лет жизни в Берлине он подготовил около 300 работ, среди них ряд больших монографий.
Живя в Берлине, Эйлер не переставал интенсивно работать для Петербургской АН, сохраняя звание её почётного члена. Он вёл обширную научную и научно-организационную переписку, в частности переписывался с М. Ломоносовым, которого высоко ценил. Эйлер редактировал математический отдел русского академического научного органа, где опубликовал за это время почти столько же статей, сколько в «Мемуарах» Берлинской АН. Он деятельно участвовал в подготовке русских математиков; в Берлин командировались для занятий под его руководством будущие академики С. Котельников, С. Румовский и М. Софронов. Большую помощь Эйлер оказывал Петербургской АН, приобретая для неё научную литературу и оборудование, ведя переговоры с кандидатами на должности в академии и т. д.
17(28) июля 1766 Эйлер вместе с семьей вернулся в Петербург. Несмотря на преклонный возраст и постигшую его почти полную слепоту, он до конца жизни продуктивно работал. За 17 лет вторичного пребывания в Петербурге им было подготовлено около 400 работ, среди них несколько больших книг. Эйлер продолжал участвовать и в организационной работе академии. В 1776 он был одним из экспертов проекта одноарочного моста через Неву, предложенного И. Кулибиным, и из всей комиссии один оказал широкую поддержку проекту.
Заслуги Эйлера как крупнейшего учёного и организатора научных исследований получили высокую оценку ещё при его жизни. Помимо Петербургской и Берлинской академий, он состоял членом крупнейших научных учреждений: Парижской АН, Лондонского королевского общества и других.
Одна из отличительных сторон творчества Эйлера – его исключительная продуктивность. Только при его жизни было опубликовано около 550 его книг и статей (список трудов Эйлера содержит примерно 850 названий). В 1909 Швейцарское естественнонаучное общество приступило к изданию полного собрания сочинений Эйлера, которое завершено в 1975; оно состоит из 72 томов. Большой интерес представляет и колоссальная научная переписка Эйлера (около 3000 писем), до сих пор опубликована лишь частично.
Необыкновенно широк был круг занятий Эйлера, охватывавших все отделы современной ему математики и механики, теорию упругости, математическую физику, оптику, теорию музыки, теорию машин, баллистику, морскую науку, страховое дело и т. д. Около 3/5 работ Эйлера относится к математике, остальные 2/5 преимущественно к её приложениям. Свои результаты и результаты, полученные другими, ученый систематизировал в ряде классических монографий, написанных с поразительной ясностью и снабженных ценными примерами. Таковы, например, «Механика, или Наука о движении, изложенная аналитически» (1736), «Введение в анализ» (1748), «Дифференциальное исчисление» (1755), «Теория движения твёрдого тела» (1765), «Универсальная арифметика» (1768–69), выдержавшая около 30 изданий на 6 языках, «Интегральное исчисление» (1768–94) и др. В XVIII в. , а отчасти и в XIX в. огромную популярность приобрели общедоступные «Письма о разных физических и философических материях, писанные к некоторой немецкой принцессе. » (1768–74), которые выдержали свыше 40 изданий на 10 языках. Большая часть содержания монографий Эйлера вошла затем в учебные руководства для высшей и частично средней школы. Невозможно перечислить все доныне употребляемые теоремы, методы и формулы Эйлера, из которых только немногие фигурируют в литературе под его именем [например, метод ломаных Эйлера, подстановки Эйлера, постоянная Эйлера, уравнения Эйлера, формулы Эйлера, функция Эйлера, числа Эйлера, формула Эйлера – Маклорена, формулы Эйлера – Фурье, эйлерова характеристика, эйлеровы интегралы, эйлеровы углы].
В «Механике» Эйлер впервые изложил динамику точки при помощи математического анализа: свободное движение точки под действием различных сил как в пустоте, так и в среде, обладающей сопротивлением; движение точки по данной линии или по данной поверхности; движение под действием центральных сил. В 1744 он впервые корректно сформулировал механический принцип наименьшего действия и показал его первые применения. В «Теории движения твёрдого тела» Эйлер разработал кинематику и динамику твёрдого тела и дал уравнения его вращения вокруг неподвижной точки, положив начало теории гироскопов. В своей теории корабля Эйлер внёс ценный вклад в теорию устойчивости. Значительны открытия Эйлера в небесной механике (например, в теории движения Луны), механике сплошных сред (основные уравнения движения идеальной жидкости в форме Эйлера и в т. н. переменных Лагранжа, колебания газа в трубах и пр.). В оптике Эйлер дал (1747) формулу двояковыпуклой линзы, предложил метод расчёта показателя преломления среды. Эйлер придерживался волновой теории света. Он считал, что различным цветам соответствуют разные длины волн света. Эйлер предложил способы устранения хроматических аберрации линз и дал методы расчёта оптических узлов микроскопа. Обширный цикл работ, начатый в 1748, Эйлер посвятил математической физике: задачам о колебании струны, пластинки, мембраны и др. Все эти исследования стимулировали развитие теории дифференциальных уравнений, приближённых методов анализа, спец. функций, дифференциальной геометрии и т. д. Многие математические открытия Эйлера содержатся именно в этих работах.
Главным делом Эйлера как математика явилась разработка математического анализа. Он заложил основы нескольких математических дисциплин, которые только в зачаточном виде имелись или вовсе отсутствовали в исчислении бесконечно малых И. Ньютона, Г. Лейбница, братьев Бернулли. Так, Эйлер первый ввёл функции комплексного аргумента и исследовал свойства основных элементарных функций комплексного переменного (показательные, логарифмические и тригонометрические функций); в частности, он вывел формулы, связывающие тригонометрические функции с показательной. Работы Эйлера в этом направлении положили начало теории функций комплексного переменного.
Эйлер явился создателем вариационного исчисления, изложенного в работе «Метод нахождения кривых линий, обладающих свойствами максимума, либо минимума. » (1744). Метод, с помощью которого Эйлер в 1744 вывел необходимое условие экстремума функционала – уравнение Эйлера, явился прообразом прямых методов вариационного исчисления XX в. Эйлер создал как самостоятельную дисциплину теорию обыкновенных дифференциальных уравнений и заложил основы теории уравнений с частными производными. Здесь ему принадлежит огромное число открытий: классический способ решения линейных уравнений с постоянными коэффициентами, метод вариации произвольных постоянных, выяснение основных свойств уравнения Риккати, интегрирование линейных уравнений с переменными коэффициентами с помощью бесконечных рядов, критерии особых решений, учение об интегрирующем множителе, различные приближённые методы и ряд приёмов решения уравнений с частными производными. Значительную часть этих результатов Эйлер собрал в своём «Интегральном исчислении».
Эйлер обогатил также дифференциальное и интегральное исчисление в узком смысле слова (например, учение о замене переменных, теорема об однородных функциях, понятие двойного интеграла и вычисление многих специальных интегралов). В «Дифференциальном исчислении» Эйлер высказал и подкрепил примерами убеждение в целесообразности применения расходящихся рядов и предложил методы обобщённого суммирования рядов, предвосхитив идеи современной строгой теории расходящихся рядов, созданной на рубеже XIX и XX вв. Кроме того, Эйлер получил в теории рядов множество конкретных результатов. Он открыл т. н. формулу суммирования Эйлера – Маклорена, предложил преобразование рядов, носящее его имя, определил суммы громадного количества рядов и ввёл в математику новые важные типы рядов (например, тригонометрические ряды). Сюда же примыкают исследования Эйлера по теории непрерывных дробей и других бесконечных процессов.
Эйлер является основоположником теории специальных функций. Он первым начал рассматривать синус и косинус как функции, а не как отрезки в круге. Им получены почти все классического разложения элементарных функций в бесконечные ряды и произведения. В его трудах создана теория γ-функции. Он исследовал свойства эллиптических интегралов, гиперболических и цилиндрических функций, ζ-функции, некоторых θ-функций, интегрального логарифма и важных классов специальных многочленов.
По замечанию П. Чебышева, Эйлер положил начало всем изысканиям, составляющим общую часть теории чисел. Так, Эйлер доказал ряд утверждений, высказанных П. Ферма (например, малая теорема Ферма), разработал основы теории степенных вычетов и теории квадратичных форм, обнаружил (но не доказал) квадратичный закон взаимности и исследовал ряд задач диофантова анализа. В работах о разбиении чисел на слагаемые и по теории простых чисел Эйлер впервые использовал методы анализа, явившись тем самым создателем аналитической теории чисел. В частности, он ввёл ζ-функцию и доказал т. н. тождество Эйлера, связывающее простые числа со всеми натуральными.
Велики заслуги Эйлера и в других областях математики. В алгебре ему принадлежат работы о решении в радикалах уравнений высших степеней и об уравнениях с двумя неизвестными, а также т. н. тождество Эйлера о четырёх квадратах. Эйлер значительно продвинул аналитическую геометрию, особенно учение о поверхностях второго порядка. В дифференциальной геометрии он детально исследовал свойства геодезических линий, впервые применил натуральные уравнения кривых, а главное, заложил основы теории поверхностей. Он ввёл понятие главных направлений в точке поверхности, доказал их ортогональность, вывел формулу для кривизны любого нормального сечения, начал изучение развёртывающихся поверхностей и т. д. ; в одной посмертно опубликованной работе (1862) он частично предварил исследования К. Гаусса по внутренней геометрии поверхностей. Эйлер занимался и отдельными вопросами топологии и доказал, например, важную теорему о выпуклых многогранниках. Эйлера-математика нередко характеризуют как гениального «вычислителя». Действительно, он был непревзойдённым мастером формальных выкладок и преобразований, в его трудах многие математические формулы и символика получили современный вид (например, ему принадлежат обозначения для e и π). Однако Эйлер также внёс в науку ряд глубоких идей, которые ныне строго обоснованы и служат образцом глубины проникновения в предмет исследования.
По выражению П. Лапласа, Эйлер явился учителем математиков второй половины XVIII в.
ДИРИХЛЕ (DIRICHLET) ПЕТЕР ГУСТАВ
(Дюрен, ныне Германия, 1805 – Геттинген, там же, 1859)
Учился в Париже, поддерживал дружеские отношения с выдающимися математиками, в частности с Фурье. По получению ученой степени был профессором университетов Бреслау (1826 – 1828), Берлина (1828 – 1855) и Геттингена, где стал заведовать кафедрой математики после смерти ученого Карла Фридриха Гаусса. Его самый выдающийся вклад в науку касается теории чисел, в первую очередь – изучения серий. Это позволило ему развить теорию серий, предложенную Фурье. Создал собственную версию доказательства теоремы Ферма, использовал аналитические функции для решения арифметических задач и ввел критерии конвергенции применительно к сериям. В области математического анализа улучшил дефиницию и понятие функции, в области теоретической механики сосредоточил внимание на изучение устойчивости систем и на Ньютоновой концепции потенциала.
ЧЕБЫШЕВ ПАФНУТИЙ ЛЬВОВИЧ
Российский математик, создатель петербургской научной школы, академик Петербургской АН (1856). Труды Чебышева положили начало развитию многих новых разделов математики.
Наиболее многочисленны работы Чебышева в области математического анализа. Ему была, в частности, посвящена диссертация на право чтения лекций, в которой Чебышев исследовал интегрируемость некоторых иррациональных выражений в алгебраических функциях и логарифмах. Интегрированию алгебраических функций Чебышев посвятил также ряд других работ. В одной из них (1853) была получена известная теорема об условиях интегрируемости в элементарных функциях дифференциального бинома. Важное направление исследований по математическому анализу составляют его работы по построению общей теории ортогональных многочленов. Поводом к её созданию явилось параболическое интерполирование способом наименьших квадратов. К этому же кругу идей примыкают исследования Чебышева по проблеме моментов и по квадратурным формулам. Имея в виду сокращение вычислений, Чебышев предложил (1873) рассматривать квадратурные формулы с равными коэффициентами (приближённое интегрирование). Исследования по квадратурным формулам и по теории интерполирования были тесно связаны с задачами, которые ставились перед Чебышевым в артиллерийском отделении военно-учёного комитета.
В теории вероятностей Чебышеву принадлежит заслуга систематического введения в рассмотрение случайных величин и создание нового приёма доказательства предельных теорем теории вероятностей – т. н. метода моментов (1845, 1846, 1867, 1887). Им был доказан больших чисел закон в весьма общей форме; при этом его доказательство поражает своей простотой и элементарностью. Исследование условий сходимости функций распределения сумм независимых случайных величин к нормальному закону Чебышев не довёл до полного завершения. Однако посредством некоторого дополнения методов Чебышева это удалось сделать А. А. Маркову. Без строгих выводов Чебышев наметил также возможность уточнений этой предельной теоремы в форме асимптотических разложений функции распределения суммы независимых слагаемых по степеням n¾1/2, где n – число слагаемых. Работы Чебышева по теории вероятностей составляют важный этап в её развитии; кроме того, они явились базой, на которой выросла русская школа теории вероятностей, вначале состоявшая из непосредственных учеников Чебышева.
РИМАН ГЕОРГ ФРИДРИГ БЕРНХАРД
(Брезеленц, Нижняя Саксония, 1826 - Селаска, близ Интры, Италия 66)
Немецкий математик. В 1846 поступил в Гёттингенский университет: слушал лекции К. Гаусса, многие идеи которого были им развиты позже. В 1847–49 слушал лекции в Берлинском университете; в 1849 вернулся в Гёттинген, где сблизился с сотрудником Гаусса физиком В. Вебером, который пробудил в нём глубокий интерес к вопросам математического естествознания.
В 1851 защитил докторскую диссертацию «Основы общей теории функций одной комплексной переменной». С 1854 приват-доцент, с 1857 профессор Гёттингенского университета.
Работы Римана оказали большое влияние на развитие математики 2-й половины XIX в. и в XX в. В докторской диссертации Риман положил начало геометрическому направлению теории аналитических функций; им введены так называемые римановы поверхности, важные при исследованиях многозначных функций, разработана теория конформных отображений и даны в связи с этим основные идеи топологии, изучены условия существования аналитических функций внутри областей различного вида (так называемый принцип Дирихле) и т. д. Разработанные Риманом методы получили широкое применение в его дальнейших трудах по теории алгебраических функций и интегралов, по аналитической теории дифференциальных уравнений (в частности, уравнений, определяющих гипергеометрические функции), по аналитической теории чисел (например, Риманом указана связь распределения простых чисел со свойствами ζ-функции, в частности с распределением её нулей в комплексной области – так называемая гипотеза Римана, справедливость которой ещё не доказана) и т. д.
В ряде работ Риман исследовал разложимость функций в тригонометрические ряды и в связи с этим определил необходимые и достаточные условия интегрируемости в смысле Римана, что имело значение для теории множеств и функций действительного переменного. Риман также предложил методы интегрирования дифференциальных уравнений с частными производными (например, с помощью так называемых инвариантов Римана и функции Римана).
В знаменитой лекции 1854 «О гипотезах, лежащих в основании геометрии» (1867) Риман дал общую идею математического пространства (по его словам, «многообразия»), включая функциональные и топологические пространства. Он рассматривал здесь геометрию в широком смысле как учение о непрерывных n-мерных многообразиях, т. е. совокупностях любых однородных объектов и, обобщая результаты Гаусса по внутренней геометрии поверхности, дал общее понятие линейного элемента (дифференциала расстояния между точками многообразия), определив тем самым то, что называется финслеровыми пространствами. Более подробно Риман рассмотрел так называемые римановы пространства, обобщающие пространства геометрий Евклида, Лобачевского и эллиптической геометрии Римана, характеризующиеся специальным видом линейного элемента, и развил учение об их кривизне. Обсуждая применение своих идей к физическому пространству, Риман поставил вопрос о «причинах метрических свойств» его, как бы предваряя то, что было сделано в общей теории относительности.
Предложенные Риманом идеи и методы раскрыли новые пути в развитии математики и нашли применение в механике и общей теории относительности. Ученый умер в 1866 от туберкулёза.
Простое число — это натуральное (целое положительное) число , которое делится без остатка только на два натуральных числа: на и на само себя. Иными словами, простое число имеет ровно два натуральных делителя: и само число .
В силу определения, множество всех делителей простого числа является двухэлементным, т.е. представляет собой множество .
Множество всех простых чисел обозначают символом . Таким образом, в силу определения множества простых чисел, мы можем записать: .
Последовательность простых чисел выглядит так:
Основная теорема арифметики
Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей. Таким образом, простые числа являются элементарными «строительными блоками» множества натуральных чисел.
Разложение натурального числа title="Rendered by QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют каноническим :
где — простое число, и . Например, каноническое разложение натурального числа выглядит так: .
Представление натурального числа в виде произведения простых также называют факторизацией числа .
Свойства простых чисел
Решето Эратосфена
Одним из наиболее известных алгоритмов поиска и распознавания простых чисел является решето Эратосфена . Так этот алгоритм был назван в честь греческого математика Эратосфена Киренского, которого считают автором алгоритма.
Для нахождения всех простых чисел, меньших заданного числа , следуя методу Эратосфена, нужно выполнить следующие шаги:
Шаг 1.
Выписать подряд все натуральные числа от двух до , т.е. .
Шаг 2.
Присвоить переменной значение , то есть значение равное наименьшему простому числу.
Шаг 3.
Вычеркнуть в списке все числа от до кратные , то есть числа: .
Шаг 4.
Найти первое незачёркнутое число в списке, большее , и присвоить переменной значение этого числа.
Шаг 5.
Повторить шаги 3 и 4 до достижения числа .
Процесс применения алгоритма будет выглядеть следующим образом:
Все оставшиеся незачёркнутые числа в списке по завершении процесса применения алгоритма будут представлять собой множество простых чисел от до .
Гипотеза Гольдбаха
Обложка книги «Дядюшка Петрос и гипотеза Гольдбаха»
Несмотря на то, что простые числа изучаются математиками достаточно давно, на сегодняшний день остаются нерешёнными многие связанные с ними проблемы. Одной из наиболее известных нерешённых проблем является гипотеза Гольдбаха , которая формулируется следующим образом:
- Верно ли, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел (бинарная гипотеза Гольдбаха)?
- Верно ли, что каждое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел (тернарная гипотеза Гольдбаха)?
Следует сказать, что тернарная гипотеза Гольдбаха является частным случаем бинарной гипотезы Гольдбаха, или, как говорят математики, тернарная гипотеза Гольдбаха является более слабой, чем бинарная гипотеза Гольдбаха.
Гипотеза Гольдбаха получила широкую известность за пределами математического сообщества в 2000-м году благодаря рекламному маркетинговому трюку издательских компаний Bloomsbury USA (США) и Faber and Faber (Великобритания). Указанные издательства, выпустив книгу «Uncle Petros and Goldbach’s Conjecture» («Дядюшка Петрос и гипотеза Гольдбаха»), пообещали выплатить в течение 2-х лет с момента издания книги приз 1 миллион долларов США тому, кто докажет гипотезу Гольдбаха. Иногда упомянутый приз от издательств путают с премиями за решение «Задач тысячелетия» (Millennium Prize Problems). Не стоит заблужаться, гипотеза Гольдбаха не отнесена «Институтом Клэя» к «задачам тысячелетия», хотя и является при этом тесно связанной с гипотезой Римана — одной из «задач тысячелетия».
Книга «Простые числа. Долгая дорога к бесконечности»
Обложка книги «Мир математики. Простые числа. Долгая дорога к бесконечности»
Дополнительно рекомендую прочесть увлекательную научно-популярную книгу , в аннотации к которой сказано: «Поиск простых чисел - одна из самых парадоксальных проблем математики. Ученые пытались решить ее на протяжении нескольких тысячелетий, но, обрастая новыми версиями и гипотезами, эта загадка по-прежнему остается неразгаданной. Появление простых чисел не подчинено какой-либо системе: они возникают в ряду натуральных чисел самопроизвольно, игнорируя все попытки математиков выявить закономерности в их последовательности. Эта книга позволит читателю проследить эволюцию научных представлений с древнейших времен до наших дней и познакомит с самыми любопытными теориями поиска простых чисел».
Дополнительно процитирую начало второй главы этой книги: «Простые числа представляют из себя одну из важных тем, которые возвращают нас к самым истокам математики, а затем по пути возрастающей сложности приводят на передний край современной науки. Таким образом, было бы очень полезно проследить увлекательную и сложную историю теории простых чисел: как именно она развивалась, как именно были собраны факты и истины, которые в настоящее время считаются общепринятыми. В этой главе мы увидим, как целые поколения математиков тщательно изучали натуральные числа в поисках правила, предсказывающего появление простых чисел, - правила, которое в процессе поиска становилось все более и более ускользающим. Мы также подробно рассмотрим исторический контекст: в каких условиях математики работали и в какой степени в их работе применялись мистические и полурелигиозные практики, которые совсем не похожи на научные методы, используемые в наше время. Тем не менее медленно и с трудом, но была подготовлена почва для новых воззрений, вдохновлявших Ферма и Эйлера в XVII и XVIII в.в.»
Числа бывают разными: натуральными, естественными, рациональными, целыми и дробными, положительными и отрицательными, комплексными и простыми, нечетными и четными, действительными и др. Из данной статьи можно узнать, что такое простые числа.
Какие числа называют английским словом “симпл”?
Очень часто школьники на один из самых несложных на первый взгляд вопросов математики, о том что такое простое число, не знают, как ответить. Они часто путают простые числа с натуральными (то есть числа, которые используются людьми при счете предметов, при этом в некоторых источниках они начинаются с нуля, а в других - с единицы). Но это совершенно два разных понятия. Простые числа - это, натуральные, то есть целые и положительные числа, которые большее единицы и которые имеют всего лишь 2 натуральных делителя. При этом один из этих делителей - это данное число, а второй - единица. Например, три - это простое число, поскольку он не делится без остатка ни на какое другое число, кроме себя самого и единицы.
Составные числа
Противоположностью простых чисел являются составные. Они также являются натуральным, также больше единицы, но имеют не два, а большее количество делителей. Так, например, числа 4, 6, 8, 9 и т. д. являются натуральными, составными, но не простыми числами. Как видите - это в основном четные числа, но не все. А вот “двойка” - четное число и “первый номер” в ряду простых чисел.
Последовательность
Чтобы построить ряд простых чисел, необходимо совершить отбор из всех натуральных чисел с учетом их определения, то есть нужно действовать методом от противного. Необходимо рассмотреть каждое из натуральных положительных чисел на предмет того, имеет ли оно более двух делителей. Давайте постараемся построить ряд (последовательность), который составляют простые числа. Список начинается с двух, следующим идет три, поскольку оно делится только на себя и на единицу. Рассмотрим число четыре. Имеет ли оно делители, кроме четырех и единицы? Да, это число 2. Значит, четыре не является простым числом. Пять также является простым (оно, кроме 1 и 5, ни на какое другое число не делится), а вот шесть - делится. И вообще, если проследить за всеми четными числами, то можно заметить, что кроме “двух”, ни одно из них не является простым. Отсюда сделаем вывод, что четные числа, кроме двух, не являются простыми. Еще одно открытие: все числа, делящиеся на три, кроме самой тройки, будь то четные или нечетные, также не являются простыми (6, 9, 12, 15, 18, 21, 24, 27 и т.д.). То же самое касается и чисел, которые делятся на пять и на семь. Все их множество также не является простым. Давайте подведем итоги. Итак, к простым однозначным числам относятся все нечетные числа, кроме единицы и девятки, а из четных - только “два”. Сами десятки (10, 20,... 40 и др.) не являются простыми. Двузначные, трехзначные и т. д. простые числа можно определить, исходя из вышеизложенных принципов: если они не имеют других делителей, кроме их самих и единицы.
Теории о свойствах простых чисел
Существует наука, которая изучает свойства целых чисел, в том числе и простых. Это раздел математики, которая называется высшей. Помимо свойств целых чисел, она также занимается алгебраическими, трансцендентными числами, а также функциями различного происхождения, связанными с арифметикой этих чисел. В этих исследованиях, помимо элементарных и алгебраических методов, также используются аналитические и геометрические. Конкретно изучением простых чисел занимается “Теория чисел”.
Простые числа — “строительные блоки” натуральных чисел
В арифметике есть теорема, которая называется основной. Согласно ей, любое натуральное число, кроме единицы, можно представить в виде произведения, множителями которого являются простые числа, причем порядок следования множителей единственен, этот означает, что и способ представления единственен. Он называется разложением натурального числа на простые множители. Есть и другое название этого процесса - факторизация чисел. Исходя из этого, простые числа можно назвать “строительным материалом”, "блоками" для построения натуральных чисел.
Поиск простых чисел. Тесты простоты
Множество ученых разных времен пытались найти какие-то принципы (системы) для нахождения списка простых чисел. Науке известны системы, которые называются решето Аткина, решето Сундартама, решето Эратосфена. Однако они не дают каких-то существенных результатов, и для нахождения простых чисел используется простая проверка. Также математиками были созданы алгоритмы. Их принято называть тестами простоты. Например, существует тест, разработанный Рабином и Миллером. Его используют криптографы. Также существует тест Каяла-Агравала- Саскены. Однако он, несмотря на достаточную точность, очень сложен в вычислении, что принижает его прикладное значение.
Имеет ли множество простых чисел предел?
О том, что множество простых является бесконечностью, писал в книге “Начала” древнегреческий ученый Евклид. Он говорил так: “Давайте на минуту представим, что простые числа имеют предел. Тогда давайте перемножим их друг с другом, а к произведению прибавим единицу. Число, полученное в результате этих простых действий, не может делиться ни на одно из ряда простых чисел, потому что в остатке всегда будет единица. А это значит, что существует какое-то другое число, которое еще не включено в список простых чисел. Следовательно, наше допущение не верно, и это множество не может иметь предела. Помимо доказательства Евклида, существует более современная формула, данная швейцарским математиком восемнадцатого века Леонардом Эйлером. Согласно ему, сумма, обратная сумме первых n чисел растет неограниченно с ростом числа n. А вот формула теоремы относительно распределения простых чисел: (n) растёт, как n/ln (n).
Какое наибольшее простое число?
Все тот же Леонард Эйлер смог найти самое большое для своего времени простое число. Это 2 31 - 1 = 2147483647. Однако к 2013 году было вычислено другое наиболее точное самое большое в списке простых чисел - 2 57885161 - 1. Его называют числом Мерсенна. Оно содержит около 17 миллионов десятичных цифр. Как видите, число, найденное ученым из восемнадцатого века, в несколько раз меньше этого. Так и должно было быть, ведь Эйлер вел данный подсчет вручную, нашему же современнику наверняка помогала вычислительная машина. Более того, это число было получено на факультете математики в одном из американских факультетов. Числа, названные в честь этого ученого, проходят через тест простоты Люка-Лемера. Однако наука не желает останавливаться на достигнутом. Фонд Электронных рубежей, который был основан в 1990 году в Соединенных Штатах Америки (EFF), назначил за нахождение больших простых чисел денежную награду. И если до 2013 года приз полагался тем ученным, которые найдут их из числа 1 и 10 миллионов десятичных чисел, то сегодня это цифра достигла от 100 миллионов до 1 миллиарда. Размер призов составляет от 150 до 250 тысяч долларов США.
Названия специальных простых чисел
Те числа, которые были найдены благодаря алгоритмам, созданным теми или иными учеными, и прошли тест простоты, называются специальными. Вот некоторые из них:
1. Мерссена.
4. Каллена.
6. Миллса и др.
Простота этих чисел, названных в честь вышеперечисленных ученых, устанавливается с использованием следующих тестов:
1. Люка-Лемера.
2. Пепина.
3. Ризеля.
4. Биллхарта - Лемера - Селфриджа и др.
Современная наука не останавливается на достигнутом, и, вероятно, в ближайшем будущем мир узнает имена тех, кто смог получить приз в 250.000 долларов, найдя наибольшее простое число.
В этой статье мы изучим простые и составные числа . Сначала дадим определения простых и составных чисел, а также приведем примеры. После этого докажем, что простых чисел бесконечно много. Далее запишем таблицу простых чисел, и рассмотрим методы составления таблицы простых чисел, особо тщательно остановимся на способе, получившем название решето Эратосфена. В заключение осветим основные моменты, которые нужно учитывать при доказательстве того, что данное число является простым или составным.
Навигация по странице.
Простые и составные числа – определения и примеры
Понятия простые числа и составные числа относятся к , которые больше единицы. Такие целые числа, в зависимости от количества их положительных делителей, подразделяются на простые и составные числа. Таким образом, чтобы понять определения простых и составных чисел , нужно хорошо представлять себе, что такое делители и кратные .
Определение.
Простые числа – это целые числа, большие единицы, которые имеют только два положительных делителя, а именно самих себя и 1 .
Определение.
Составные числа – это целые числа, большие единицы, которое имеют, по крайней мере, три положительных делителя.
Отдельно заметим, что число 1 не относится ни к простым, ни к составным числам. Единица имеет только один положительный делитель, которым является само число 1 . Этим число 1 отличается от всех остальных целых положительных чисел, которые имеют не менее двух положительных делителей.
Учитывая, что целые положительные числа – это , и что единица имеет только один положительный делитель, можно привести другие формулировки озвученных определений простых и составных чисел.
Определение.
Простыми числами называют натуральные числа, которые имеют только два положительных делителя.
Определение.
Составными числами называют натуральные числа, имеющие более двух положительных делителей.
Отметим, что каждое целое положительное число, большее единицы, есть либо простое, либо составное число. Иными словами, не существует ни одного такого целого числа, которое не являлось бы ни простым, ни составным. Это следует из свойства делимости , которое гласит, что числа 1 и a всегда являются делителями любого целого числа a .
Исходя из информации предыдущего абзаца, можно дать следующее определение составных чисел.
Определение.
Натуральные числа, которые не являются простыми, называются составными .
Приведем примеры простых и составных чисел .
В качестве примеров составных чисел приведем 6 , 63 , 121 и 6 697 . Это утверждение тоже нуждается в пояснении. Число 6 имеет кроме положительных делителей 1 и 6 еще и делители 2 и 3 , так как 6=2·3 , поэтому 6 – действительно составное число. Положительными делителями 63 являются числа 1 , 3 , 7 , 9 , 21 и 63 . Число 121 равно произведению 11·11 , поэтому его положительными делителями являются 1 , 11 и 121 . А число 6 697 составное, так как его положительными делителями кроме 1 и 6 697 являются еще и числа 37 и 181 .
В заключение этого пункта хочется еще обратить внимание на то, что простые числа и взаимно простые числа – это далеко ни одно и то же.
Таблица простых чисел
Простые числа, для удобства их дальнейшего использования, записывают в таблицу, которую называют таблицей простых чисел. Ниже представлена таблица простых чисел до 1 000 .
Возникает логичный вопрос: «Почему мы заполнили таблицу простых чисел только до 1 000 , разве нельзя составить таблицу всех существующих простых чисел»?
Ответим сначала на первую часть этого вопроса. Для большинства задач, при решении которых придется использовать простые числа, нам будет вполне достаточно простых чисел в пределах тысячи. В остальных случаях, скорее всего, придется прибегать к каким-либо специальным приемам решения. Хотя, несомненно, мы можем составить таблицу простых чисел до сколь угодно большого конечного целого положительного числа, будь то 10 000 или 1 000 000 000 , в следующем пункте мы поговорим о методах составления таблиц простых чисел, в частности, разберем способ, получивший название .
Теперь разберемся с возможностью (а точнее с невозможностью) составления таблицы всех существующих простых чисел. Мы не можем составить таблицу всех простых чисел, потому что простых чисел бесконечно много. Последнее утверждение представляет собой теорему, которую мы докажем после следующей вспомогательной теоремы.
Теорема.
Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.
Доказательство.
Пусть a – натуральное число, большее единицы, и b – наименьший положительный и отличный от единицы делитель числа a . Докажем, что b – простое число методом от противного.
Предположим, что b – составное число. Тогда существует делитель числа b (обозначим его b 1 ), который отличен как от 1 , так и от b . Если также учесть, что абсолютная величина делителя не превосходит абсолютной величины делимого (это мы знаем из свойств делимости), то должно выполняться условие 1
Так как число a делится на b по условию, и мы сказали, что b делится на b 1 , то понятие делимости позволяет говорить о существовании таких целых чисел q и q 1 , что a=b·q и b=b 1 ·q 1 , откуда a= b 1 ·(q 1 ·q) . Из следует, что произведение двух целых чисел есть целое число, тогда равенство a=b 1 ·(q 1 ·q) указывает на то, что b 1 является делителем числа a . Учитывая полученные выше неравенства 1
Теперь мы можем доказать, что простых чисел бесконечно много.
Теорема.
Простых чисел бесконечно много.
Доказательство.
Предположим, что это не так. То есть, предположим, что простых чисел всего 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 делилось бы на p n+1 . Но на p n+1 делится и число p , равное сумме p 1 ·p 2 ·…·p n +1 . Отсюда следует, что на p n+1 должно делиться второе слагаемое этой суммы, которое равно единице, а это невозможно.
Так доказано, что всегда может быть найдено новое простое число, не заключающееся среди любого количества наперед заданных простых чисел. Следовательно, простых чисел бесконечно много.
Итак, в силу того, что простых чисел бесконечно много, при составлении таблиц простых чисел всегда ограничивают себя сверху каким-либо числом, обычно, 100 , 1 000 , 10 000 и т.д.
Решето Эратосфена
Сейчас мы обсудим способы составления таблиц простых чисел. Предположим, что нам нужно составить таблицу простых чисел до 100 .
Самым очевидным методом решения этой задачи является последовательная проверка целых положительных чисел, начиная с 2 , и заканчивая 100 , на наличие положительного делителя, который больше 1 и меньше проверяемого числа (из свойств делимости мы знаем, что абсолютная величина делителя не превосходит абсолютной величины делимого, отличного от нуля). Если такой делитель не найден, то проверяемое число является простым, и оно заносится в таблицу простых чисел. Если же такой делитель найден, то проверяемое число является составным, оно НЕ заносится в таблицу простых чисел. После этого происходит переход к следующему числу, которое аналогично проверяется на наличие делителя.
Опишем несколько первых шагов.
Начинаем с числа 2 . Число 2 не имеет положительных делителей, кроме 1 и 2 . Следовательно, оно простое, поэтому, заносим его в таблицу простых чисел. Здесь следует сказать, что 2 является наименьшим простым числом. Переходим к числу 3 . Его возможным положительным делителем, отличным от 1 и 3 , является число 2 . Но 3 на 2 не делится, поэтому, 3 – простое число, и его также нужно занести в таблицу простых чисел. Переходим к числу 4 . Его положительными делителями, отличными от 1 и 4 , могут быть числа 2 и 3 , проверим их. Число 4 делится на 2 , поэтому, 4 – составное число, и его не нужно заносить в таблицу простых чисел. Обратим внимание на то, что 4 – наименьшее составное число. Переходим к числу 5 . Проверяем, являются ли его делителем хотя бы одно из чисел 2 , 3 , 4 . Так как 5 не делится ни на 2 , ни на 3 , ни на 4 , то оно простое, и его надо записать в таблицу простых чисел. Дальше происходит переход к числам 6 , 7 , и так далее до 100 .
Такой подход к составлению таблицы простых чисел является далеко не идеальным. Так или иначе, он имеет право на существование. Отметим, что при этом способе построения таблицы целых чисел можно использовать признаки делимости , которые немного ускорят процесс поиска делителей.
Существует более удобный способ для составления таблицы простых чисел, называемый . Присутствующее в названии слово «решето» не случайно, так как действия этого метода помогают как бы «просеять» сквозь решето Эратосфена целые числа, большие единицы, чтобы отделить простые от составных.
Покажем решето Эратосфена в действии при составлении таблицы простых чисел до 50 .
Сначала записываем по порядку числа 2, 3, 4, …, 50 .
Первое записанное число 2 является простым. Теперь от числа 2 последовательно перемещаемся вправо на два числа и зачеркиваем эти числа, пока не доберемся до конца составляемой таблицы чисел. Так будут вычеркнуты все числа, кратные двум.
Первым следующим за 2 невычеркнутым числом является 3 . Это число простое. Теперь от числа 3 последовательно перемещаемся вправо на три числа (учитывая и уже зачеркнутые числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные трем.
Первым следующим за 3 невычеркнутым числом является 5 . Это число простое. Теперь от числа 5 последовательно перемещаемся вправо на 5 чисел (учитываем и зачеркнутые ранее числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные пяти.
Дальше вычеркиваем числа, кратные 7 , затем, кратные 11 и так далее. Процесс заканчивается, когда не останется чисел для вычеркивания. Ниже показана законченная таблица простых чисел до 50 , полученная с помощью решета Эратосфена. Все незачеркнутые числа являются простыми, а все зачеркнутые числа – составными.
Давайте еще сформулируем и докажем теорему, которая позволит ускорить процесс составления таблицы простых чисел при помощи решета Эратосфена.
Теорема.
Наименьший положительный и отличный от единицы делитель составного числа a не превосходит , где - из a .
Доказательство.
Обозначим буквой b наименьший и отличный от единицы делитель составного числа a (число b является простым, что следует из теоремы, доказанной в самом начале предыдущего пункта). Тогда существует такое целое число q , что a=b·q (здесь q – положительное целое число, что следует из правил умножения целых чисел), причем (при b>q нарушится условие, что b – наименьший делитель числа a , так как q также является делителем числа a в силу равенства a=q·b ). Умножив обе части неравенства на положительное и большее единицы целое число b (это нам позволяют сделать ), получаем , откуда и .
Что же нам дает доказанная теорема, касательно решета Эратосфена?
Во-первых, вычеркивание составных чисел, кратных простому числу b следует начинать с числа, равного (это следует из неравенства ). Например, вычеркивание чисел, кратных двум, следует начинать с числа 4 , кратных трем – с числа 9 , кратных пяти – с числа 25 , и так далее.
Во-вторых, составление таблицы простых чисел до числа n с помощью решета Эратосфена можно считать законченным тогда, когда будут вычеркнуты все составные числа, кратные простым числам, не превосходящим . В нашем примере n=50 (так как мы составляем таблицу простых чисел до 50 ) и , поэтому решето Эратосфена должно отсеять все составные числа, кратные простым числам 2 , 3 , 5 и 7 , которые не превосходят арифметического квадратного корня из 50 . То есть, нам дальше не нужно заниматься поиском и вычеркиванием чисел, кратных простым числам 11 , 13 , 17 , 19 , 23 и так далее до 47 , так как они уже будут вычеркнуты, как кратные меньшим простым числам 2 , 3 , 5 и 7 .
Данное число простое или составное?
Некоторые задания требуют выяснения, является ли данное число простым или составным. В общем случае эта задача далеко не проста, особенно для чисел, запись которых состоит из значительного количества знаков. В большинстве случаев приходится искать какой-либо специфический способ ее решения. Однако мы попробуем дать направление ходу мыслей для несложных случаев.
Несомненно, можно попробовать воспользоваться признаками делимости для доказательства того, что данное число является составным. Если, к примеру, некоторый признак делимости показывает, что данное число делится на некоторое целое положительное число большее единицы, то исходное число является составным.
Пример.
Докажите, что число 898 989 898 989 898 989 составное.
Решение.
Сумма цифр данного числа равна 9·8+9·9=9·17 . Так как число, равное 9·17 делится на 9 , то по признаку делимости на 9 можно утверждать, что исходное число также делится на 9 . Следовательно, оно составное.
Существенный недостаток такого подхода заключается в том, что признаки делимости не позволяют доказать простоту числа. Поэтому при проверке числа на то, является ли оно простым или составным, нужно действовать иначе.
Самый логичный подход состоит в переборе всех возможных делителей данного числа. Если ни один из возможных делителей не будет истинным делителем данного числа, то это число будет простым, в противном случае – составным. Из теорем, доказанных в предыдущем пункте, следует, что делители данного числа a нужно искать среди простых чисел, не превосходящих . Таким образом, данное число a можно последовательно делить на простые числа (которые удобно брать из таблицы простых чисел), пытаясь найти делитель числа a . Если будет найден делитель, то число a – составное. Если же среди простых чисел, не превосходящих , не окажется делителя числа a , то число a – простое.
Пример.
Число 11 723 простое или составное?
Решение.
Выясним, до какого простого числа могут быть делители числа 11 723 . Для этого оценим .
Достаточно очевидно, что 
, так как 200 2 =40 000
, а 11 723<40 000
(при необходимости смотрите статью сравнение чисел
). Таким образом, возможные простые делители числа 11 723
меньше числа 200
. Это уже значительно облегчает нашу задачу. Если бы мы этого не знали, то нам бы пришлось перебирать все простые числа не до 200
, а вплоть до числа 11 723
.
При желании можно оценить более точно. Так как 108 2 =11 664
, а 109 2 =11 881
, то 108 2 <11 723<109 2
, следовательно, 
. Таким образом, любое из простых чисел, меньших 109
, потенциально является простым делителем данного числа 11 723
.
Теперь мы будем последовательно делить число 11 723 на простые числа 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 . Если число 11 723 разделится нацело на одно из записанных простых чисел, то оно будет составным. Если же оно не делится ни на одно из записанных простых чисел, то исходное число простое.
Не будем описывать весь этот монотонный и однообразный процесс деления. Сразу скажем, что 11 723