История создания таблицы простых чисел. Научная работа
Свойства простых чисел впервые начали изучать математики Древней Греции. Математики пифагорейской школы (500 - 300 до н.э.) в первую очередь интересовались мистическими и нумерологическими свойствами простых чисел. Они первыми пришли к идеям о совершенных и дружественных числах.
У совершенного числа сумма его собственных делителей равна ему самому. Например, собственные делители числа 6: 1, 2 и 3. 1 + 2 + 3 = 6. У числа 28 делители - это 1, 2, 4, 7 и 14. При этом, 1 + 2 + 4 + 7 + 14 = 28.
Числа называются дружественными, если сумма собственных делителей одного числа равна другому, и наоборот – например, 220 и 284. Можно сказать, что совершенное число является дружественным для самого себя.
Ко времени появления работы Евклида «Начала» в 300 году до н.э. уже было доказано несколько важных фактов касательно простых чисел. В книге IX «Начал» Эвклид доказал, что простых чисел бесконечное количество. Это, кстати, один из первых примеров использования доказательства от противного. Также он доказывает Основную теорему арифметики – каждое целое число можно представить единственным образом в виде произведения простых чисел.
Также он показал, что если число 2 n -1 является простым, то число 2 n-1 * (2 n -1) будет совершенным. Другой математик, Эйлер, в 1747 году сумел показать, что все чётные совершенные числа можно записать в таком виде. По сей день неизвестно, существуют ли нечётные совершенные числа.
В году 200 году до н.э. грек Эратосфен придумал алгоритм для поиска простых чисел под названием «Решето Эратосфена».
А затем случился большой перерыв в истории исследования простых чисел, связанный со Средними веками.
Следующие открытия были сделаны уже в начале 17-го века математиком Ферма. Он доказал гипотезу Альбера Жирара, что любое простое число вида 4n+1 можно записать уникальным образом в виде суммы двух квадратов, и также сформулировал теорему о том, что любое число можно представить в виде суммы четырёх квадратов.
Он разработал новый метод факторизации больших чисел, и продемонстрировал его на числе 2027651281 = 44021 ? 46061. Также он доказал Малую теорему Ферма: если p – простое число, то для любого целого a будет верно a p = a modulo p.
Это утверждение доказывает половину того, что было известно как «китайская гипотеза», и датируется 2000 годами ранее: целое n является простым тогда и только тогда, если 2 n -2 делится на n. Вторая часть гипотезы оказалась ложной – к примеру, 2 341 - 2 делится на 341, хотя число 341 составное: 341 = 31 ? 11.
Малая теорема Ферма послужила основой множества других результатов в теории чисел и методов проверки чисел на принадлежность к простым – многие из которых используются и по сей день.
Ферма много переписывался со своими современниками, в особенности с монахом по имени Марен Мерсенн. В одном из писем он высказал гипотезу о том, что числа вида 2 n +1 всегда будут простыми, если n является степенью двойки. Он проверил это для n = 1, 2, 4, 8 и 16, и был уверен, что в случае, когда n не является степенью двойки, число не обязательно получалось простым. Эти числа называются числами Ферма, и лишь через 100 лет Эйлер показал, что следующее число, 2 32 + 1 = 4294967297 делится на 641, и следовательно, не является простым.
Числа вида 2 n - 1 также служили предметом исследований, поскольку легко показать, что если n – составное, то и само число тоже составное. Эти числа называют числами Мерсенна, поскольку он активно их изучал.
Но не все числа вида 2 n - 1, где n – простое, являются простыми. К примеру, 2 11 - 1 = 2047 = 23 * 89. Впервые это обнаружили в 1536 году.
Многие годы числа такого вида давали математикам наибольшие известные простые числа. Что число M 19 , было доказано Катальди в 1588 году, и в течение 200 лет было наибольшим известным простым числом, пока Эйлер не доказал, что M 31 также простое. Этот рекорд продержался ещё сто лет, а затем Люкас показал, что M 127 - простое (а это уже число из 39 цифр), и после него исследования продолжились уже с появлением компьютеров.
В 1952 была доказана простота чисел M 521 , M 607 , M 1279 , M 2203 и M 2281 .
К 2005 году найдено 42 простых чисел Мерсенна. Наибольшее из них, M 25964951 , состоит из 7816230 цифр.
Работа Эйлера оказала огромное влияние на теорию чисел, в том числе и простых. Он расширил Малую теорему Ферма и ввёл?-функцию. Факторизовал 5-е число Ферма 2 32 +1, нашёл 60 пар дружественных чисел, и сформулировал (но не смог доказать) квадратичный закон взаимности.
Он первым ввёл методы математического анализа и разработал аналитическую теорию чисел. Он доказал, что не только гармонический ряд? (1/n), но и ряд вида
1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…
Получаемый суммой величин, обратных к простым числам, также расходится. Сумма n членов гармонического ряда растёт примерно как log(n), а второй ряд расходится медленнее, как log[ log(n) ]. Это значит, что, например, сумма обратных величин ко всем найденным на сегодняшний день простым числам даст всего 4, хотя ряд всё равно расходится.
На первый взгляд кажется, что простые числа распределены среди целых довольно случайно. К примеру, среди 100 чисел, идущих прямо перед 10000000, встречается 9 простых, а среди 100 чисел, идущих сразу после этого значения – всего 2. Но на больших отрезках простые числа распределены достаточно равномерно. Лежандр и Гаусс занимались вопросами их распределения. Гаусс как-то рассказывал другу, что в любые свободные 15 минут он всегда подсчитывает количество простых в очередной 1000 чисел. К концу жизни он сосчитал все простые числа в промежутке до 3 миллионов. Лежандр и Гаусс одинаково вычислили, что для больших n плотность простых чисел составляет 1/log(n). Лежандр оценил количество простых чисел в промежутке от 1 до n, как
?(n) = n/(log(n) - 1.08366)
А Гаусс – как логарифмический интеграл
?(n) = ? 1/log(t) dt
С промежутком интегрирования от 2 до n.
Утверждение о плотности простых чисел 1/log(n) известно как Теорема о распределении простых чисел. Её пытались доказать в течение всего 19 века, а прогресса достигли Чебышёв и Риман. Они связали её с гипотезой Римана – по сию пору не доказанной гипотезой о распределении нулей дзета-функции Римана. Плотность простых чисел была одновременно доказана Адамаром и Валле-Пуссеном в 1896 году.
В теории простых чисел есть ещё множество нерешённых вопросов, некоторым из которых уже многие сотни лет:
- гипотеза о простых числах-близнецах – о бесконечном количестве пар простых чисел, отличающихся друг от друга на 2
- гипотеза Гольдбаха: любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел
- бесконечно ли количество простых чисел вида n 2 + 1 ?
- всегда ли можно найти простое число между n 2 and (n + 1) 2 ? (факт, что между n и 2n всегда есть простое число, было доказан Чебышёвым)
- бесконечно ли число простых чисел Ферма? есть ли вообще простые числа Ферма после 4-го?
- существует ли арифметическая прогрессия из последовательных простых чисел для любой заданной длины? например, для длины 4: 251, 257, 263, 269. Максимальная из найденных длина равна 26 .
- бесконечно ли число наборов из трёх последовательных простых чисел в арифметической прогрессии?
- n 2 - n + 41 – простое число для 0 ? n ? 40. Бесконечно ли количество таких простых чисел? Тот же вопрос для формулы n 2 - 79 n + 1601. Эти числа простые для 0 ? n ? 79.
- бесконечно ли количество простых чисел вида n# + 1? (n# - результат перемножения всех простых чисел, меньших n)
- бесконечно ли количество простых чисел вида n# -1 ?
- бесконечно ли количество простых чисел вида n! + 1?
- бесконечно ли количество простых чисел вида n! – 1?
- если p – простое, всегда ли 2 p -1 не содержит среди множителей квадратов простых чисел
- содержит ли последовательность Фибоначчи бесконечное количество простых чисел?
Самые большие близнецы среди простых чисел – это 2003663613 ? 2 195000 ± 1. Они состоят из 58711 цифр, и были найдены в 2007 году.
Самое большое факториальное простое число (вида n! ± 1) – это 147855! - 1. Оно состоит из 142891 цифр и было найдено в 2002.
Наибольшее праймориальное простое число (число вида n# ± 1) – это 1098133# + 1.
Вы можете помочь и перевести немного средств на развитие сайта
Простые и составные числа. Признаки делимости.
2014-02-01
Частное
делитель числа
кратное число
четное число
нечетное число
простое число
составное число
Признак делимости на 2
Признак делимости на 4
Признак делимости на 5
Признак делимости на 3 и 9
Если $a$ и $b$ - натуральные числа, причем
$a=bq$,
где $q$ - также натуральное число, то говорят, что $q$ -
частное от деления числа $a$ на число $b$, и пишут: $q = a/b$.
Также говорят, что $a$ делится на $b$ нацело
или без остатка
.
Всякое число $b$, на которое $a$ делится без остатка, называется делителем числа $a$
Само
число $a$ но отношению к своему делителю называется кратным
Таким образом, числа, кратные $b$, суть числа $b, 2b, 3b, \cdots$.
Числа, кратные числу 2 (т. е. делящиеся на 2 без остатка), называются четными
.Числа, не делящиеся на 2 нацело, называются нечетными
Каждое натуральное число либо четно, либо нечетно.
Если каждое из двух чисел $a_{1}, a_{2}$ является кратным числа $b$, то и сумма $a_{1}+a_{2}$ - кратное числа $b$. Это видно из записи $a_{1}=bq_{1}, a_{2}=bq_{2}; a_{1}+a_{2}=bq_{1}+bq_{2}= b (q_{1}+q_{2})$.
Обратно, если $a_{1}$ и $a_{1}+a_{2}$ - кратные числа $b$, то $a_{2}$ - также кратное числа $b$.
Всякое отличное от единицы натуральное число имеет по меньшей мере два делителя: единицу и самоё себя.
Если число не имеет никаких других делителей, кроме себя и единицы, оно называется простым
.Число, имеющее какой-нибудь делитель, отличный от себя и единицы, называют составным
Числом. Единицу принято не относить ни к простым, ни к составным числам. Вот несколько первых простых чисел, записанных в порядке возрастания:
$2,3,5,7,11,13,17, \cdots$
Число 2 - единственное четное простое число; все остальные простые числа - нечетные.
То, что простых чисел имеется бесконечное множество, было установлено еще в древности (Евклид, III век до нашей эры).
Идея доказательства Евклида бесконечности множества простых чисел весьма проста. Допустим, что простых чисел - конечное число; перечислим их все, например, расположив в порядке возрастания:
$2,3,5, \cdots , p$. (1)
Составим число, равное их произведению плюс единица:
$a = 2 \cdot 3 \cdot 5 \cdots p+1$.
Очевидно, что это число не делится ни на одно из чисел (1). Следовательно, либо оно само является простым, либо, если оно составное, то имеет простой делитель, отличный от чисел (1), что противоречит допущению о том, что в записи (1) перечислены все простые числа.
Это доказательство представляет большой интерес, так как дает пример доказательства теоремы существования (бесконечного множества простых чисел), не связанного с фактическим отысканием объектов, существование которых доказывается.
Можно доказать, что всякое составное число представимо в виде произведения простых чисел. Так, например,
$1176 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 7 \cdot 7$ или $1176 = 2^{3} \cdot 3 \cdot 7^{2}$.
Как видно из этого примера, в разложении данного числа на простые множители некоторые из них могут повторяться несколько раз.
В общем случае в записи разложения числа $a$ на простые множители
$a = p^{k_{1}}_{1} p^{k_{2}}_{2} \cdots p^{k_{n}}_{n}$ (2)
подразумевается, что все простые числа $p_{1},p_{2}, \cdots , p_{n}$ различны между собой (причем $p_{1}$ повторяется множителем $k_{1}$ раз, $p_{2}$ повторяется множителем $k_{2}$ раз и т. д.). При этом условии можно доказать, что разложение единственно с точностью до порядка записи сомножителей.
При разложении числа на простые множители полезно бывает использовать признаки делимости, позволяющие выяснить, делится ли данное число на некоторое другое число без остатка, не производя самого деления. Мы выведем признаки делимости на числа 2, 3, 4, 5, 9.
Признак делимости на 2. На 2 делятся те и только те числа, в записи которых последняя цифра выражает четное число (0, 2, 4, 6 или 8).
Доказательство. Представим число $\overline{c_{1}c_{2} \cdots c_{m}}$ в виде $\overline{c_{1}c_{2} \cdots c_{m}} = \overline{c_{1}c_{2} \cdots 0} + c_{m}$.
Первое слагаемое в правой части делится на 10 и потому - четное; сумма будет четной тогда и только тогда, когда $c_{m}$ - четное число.
Признак делимости на 4 Число $\overline{c_{1}c_{2} \cdots c_{m}}$ делится на 4 тогда и только тогда, когда двузначное число, выражаемое его последними двумя цифрами, делится на 4.
Доказательство. Представим число $\overline{c_{1}c_{2} \cdots c_{m}}$ в виде
$\overline{c_{1}c_{2} \cdots c_{m}} = \overline{c_{1}c_{2} \cdots 00} + \overline{c_{m-1}c_{m}}$
Первое слагаемое делится на 100 и тем более на 4. Сумма будет делиться на 4 в том и только в том случае, если $\overline{c_{m-1}c_{m}}$ делится на 4.
Признак делимости на 5. На 5 делятся те и только те числа, запись которых заканчивается цифрой 0 или цифрой 5.
Признаки делимости на 3 и на 9. Число делится на 3 {соответственно на 9) в том и только в том случае, когда сумма его цифр делится на 3 (соответственно на 9).
Доказательство. Запишем очевидные равенства
$10 = 9+1$,
$100 = 99 + 1$,
$1000 = 999+1$,
$ \cdots $,
в силу которых можно число $\overline{c_{1}c_{2} \cdots c_{m}}$ представить в виде
$a_{m}=c_{1}(99 \cdots 9 + 1) + \cdots + c_{m-1} (9+1) + c_{m}$
или
$a_{m}=c_{1} \cdot 99 \cdots 9 + \cdots + c_{m-1} \cdot 9 + (c_{1} + c_{2} + \cdots + c_{m-1} + c_{m})$.
Видно, что все слагаемые, кроме, быть может, последней скобки, делятся на 9 (и тем более на 3). Поэтому данное число делится на 3 или на 9 тогда и только тогда, когда делится на 3 или на 9 сумма его цифр $c_{1}+c_{2}+ \cdots + c_{m}$.
Разные задачи, связанные с простыми числами, были и остаются до сих пор важными и интересными для математики, многие из них до сих пор не решены, и с их исследованием связаны любопытные факты из истории математики .
Так, еще в XVI-XVII вв. математиками начали рассматриваться числа вида $2^n-1$, и при исследовании их на простоту в истории было допущено много ошибок. Ясно, что если n - составное число , то это число также составное: если $n=km$, то $2^n-1=(2^k)^m-1^m$ - как разность степеней делится на разность оснований, т.е. не является простым, и поэтому естественно рассматривать только n.
Но и при простых n это число может оказаться составным: например, 2 11 =2047=23 89, оно составное и при n=23, и n=37, что установлено Ферма , через 40 с лишним лет обнаружившим ошибку в работе другого исследователя, утверждавшего, что при n=23, 29, 31, 37 число $2^n-1$ простое, но не заметившего другой ошибки: при n=29 оно также не является простым. А это обнаружил - еще примерно через 100 лет - Эйлер , а также и то, что при n=31 это число все же действительно является простым.
В XVII в. числами вида $2^n-1$ занимался французский монах Марен Мерсенн , который привел полный список простых n от 2 до 257, для которых эти числа являются простыми, в котором он предвосхитил указанный выше результат Эйлера, но и этот список содержал ошибки, и одну из них нашел спустя два с половиной века, в 1883 г., русский сельский священник-учитель Иван Михеевич Первушин . Это событие отмечено мемориальной доской на его доме в Зауралье - в г. Шадринске Курганской области. А ошибочно указанные Мерсенном n=67 и n=257 были исключены из его списка лишь в XX в.
Конечно, в современном Мире за такие ошибки могли бы и в суд подать, и тогда Мерсенну понадобилось бы юридическое представительство интересов в суде от хорошего адвоката. Хотя сейчас юридически представлять интересы в суде могут многие, но настоящими профессионалами являются только единицы. А французскому монаху уже вообще все равно!
Простые числа вида $2^n-1$ получили название чисел Мерсенна , и до сих пор математики не знают, конечно или бесконечно множество таких чисел, а в 1996 г. найдено тридцать пятое число Мерсенна - при n=1 398 629, и в нем примерно 400 тысяч цифр, 15 мая 2004 г. найдено тридцать шестое число, при этом компьютеру понадобилось на это несколько часов. Ясно, что найти такое громадное число без использования компьютеров немыслимо. В истории математики есть и еще один казус, связанный с простыми числами, так называемыми числами Ферма - числами вида $2^{2^n}+1$. Опять понятно, почему показатель степени k=2 п имеет такой, казалось бы, частный вид, но 2 п - это общий вид числа, не имеющего нечетных простых делителей, а если этот показатель k имеет такой делитель p, то число 2 п +1 не является простым: если k=pq, то 2 k +1=(2 q) р +1 p , а сумма нечетных степеней делится на сумму оснований. Сам Ферма считал, что эти числа все являются простыми, но Эйлер показал, что это утверждение ошибочно, нашел к нему контрпример: $2^{32}+1=4 294 967 297=641\times6 700 417$.
И самое удивительное открытие в связи с числами Ферма сделал великий математик Гаусс , имя которого вы наверняка слышали в связи с его моментальным вычислением суммы 1+2+3+…+100: оказывается, что правильный n-угольник можно построить тогда и только тогда, когда все нечетные простые делители числа n являются числами Ферма. Поэтому, в частности, правильный 7-угольник циркулем и линейкой построить нельзя, а 17-угольник - можно: $17=2^{2^2}+1$.
Факты о числах. Это и простые числа и многие другие. Некоторые числа, такие как число Пи и ряд других мы вынесли в отдельные материалы. Так что советуем почитать и их. Приведем здесь несколько занимательных фактов о числах , которые, наверняка, будут вам интересны.
Факты про отрицательные числа
В наше время отрицательные числа известны многим, но так было далеко не всегда. Впервые отрицательные числа стали применять в Китае в III веке, но разрешено было их использовать лишь в исключительных случаях, так как их считали бессмыслицей. Несколько позднее отрицательные числа стали применять в Индии для обозначения долгов.
Так, в труде «Математика» в девяти книгах, изданном в 179 г. н. э., во времена династии Хань и прокомментированном в 263 г. Лю Хуэйем, в китайской системе счётных палочек для отрицательных чисел применялись чёрные палочки, а для положительных - красные. Также, для обозначения отрицательных чисел, Лю Хуэй использовал наклонные счётные палочки.
Знак «-», который сейчас используется для обозначения отрицательных чисел впервые был замечен в древнем манускрипте Бахшали в Индии, но среди учёных нет единого мнения относительно того, когда он был составлен, диапазон разногласий составляет от 200 г. до 600 г. н. э.
Отрицательные числа уже были известны в Индии в 630 г. н. э.. Они были использованы математиком Брахмагуптой (598-668 гг).
Впервые в Европе отрицательные числа начали использовать примерно в 275 г. н. э.. Их ввёл в обиход греческий математик Диофант Александрийский, но на Западе их считали абсурдными вплоть до появления книги «Ars Magna» («Великое искусство»), написанной в 1545 г. итальянским математиком Джироламо Кардано (1501-1576).
Факты о простых числах
Числа 2 и 5 являются единственными из ряда простых чисел, которые заканчиваются на 2 и 5.
Прочие факты о числах
Число 18, является единственным (кроме 0) числом, сумма цифр которого в 2 раза меньше него самого.
2520 является самым маленьким числом, которое можно без остатка поделить на все числа начиная с 1 и заканчивая 10.
Число «пять» на тайском языке произносится как «ха». Поэтому число составленное из трёх пятёрок - 555, будет произносится как сленг-фраза, обозначающая человеческий смех - "Ха, ха, ха".
Все мы знаем, что существую слова палиндромы. То есть те, которые можно читать слева направо и справа налево и значение их не меняется. Однако, существуют и числа-палиндромы (палиндромоны). Они представляют собой зеркальные числа, которое будет читается и иметь одинаковое значение в обоих направлениях, например, 1234321.
Слово Googol (происхождение бренда Google) обозначает число 1 со 100 нулями.
Единственным числом, которое нельзя написать римскими цифрами является "Ноль". Также, в современной математике ноль имеет некоторые особенности своей трактовки. Так, в российской математике его не причисляют к ряду натуральных чисел, а зарубежная наука относит.
Отдел образования и молодежной политики администрации
Яльчикского района Чувашской Республики
Проект
Простые числа…
Так ли проста их история?
Выполнила ученица 7 класса МОУ «Новошимкусская СОШ Яльчикского района Чувашской Республики» Ефимова Марина
Руководитель: учитель математики I категории МОУ «Новошимкусская СОШ Яльчикского района Чувашской Республики» Кириллова С.М.
с.Новые Шимкусы - 2007
Определение простых чисел 3
Заслуги Эйлера 3
Основная теорема арифметики 4
Простые числа Мерсена 4
Простые числа Ферма 5
Решето Эратосфена 5
Открытие П.Л.Чебышева 6
Проблема Гольдбаха 7
И.М.Виноградов 8
Заключение 8
Литература 10
Интерес к изучению простых чисел возник у людей в глубокой древности. И вызван он был не только практической необходимостью. Привлекала их необычайная магическая сила. Числа, которыми можно выразить количество любых предметов. Неожиданные и в то же время естественные свойства натуральных чисел, обнаруженные древними математиками, удивляли их своей замечательной красотой и вдохновляли на новые исследования.
Должно быть, одним из первых свойств чисел, открытых человеком, было то, что некоторые из них могут быть разложены на два или более множителей, например,
6=2*3, 9=3*3, 30=2*15=3*10, в то время как другие, например 3, 7, 13, 37, не могут быть разложены подобным образом.
Когда число с = а b является произведением двух чисел а и b, то числа а и b называются множителями или делителями числа с. Каждое число может быть представлено в виде произведения двух сомножителей. Например, с = 1 *с = с*1.
Простым называется число, которое делится только само на себя и на единицу.
Единица, имеющая только один делитель, к простым числам не относится. Не относится она и к составным числам. Единица занимает особое положение в числовом ряду. Пифагорейцы учили, что единица - матерь всех чисел, дух, из которого происходит весь видимый мир, она есть разум, добро, гармония.
В Казанском университете профессор Никольский с помощью единицы ухитрился доказать существование Бога. Он говорил: «Как не может быть числа без единицы, так и Вселенная без единого Владыки существовать не может».
Единица и в самом деле - число уникальное по свойствам: она делится только сама на себя, но любое другое число на нее делится без остатка, любая ее степень равна тому же самому числу - единице!
После деления на нее ни одно число не изменяется, а если и поделить любое число на самое себя, получится опять же единица! Не удивительно ли это? Поразмыслив над этим, Эйлер заявил: «Нужно исключить единицу из последовательности простых чисел, она не является ни простым, ни составным».
Это было уже существенно важное упорядочивание в темном и сложном вопросе о простых числах.
Заслуги Эйлера
Леонард Эйлер
(1707-1783)
У Эйлера учились все - ив Западной Европе, и в России. Диапазон его творчества широк: дифференциальное и интегральное исчисления, алгебра, механика, диоптрика, артиллерия, морская наука, теория движения планет и Луны, теория музыки - всего не перечислить. Во всей этой научной мозаике находится и теория чисел. Эйлер отдал ей немало сил и немалого добился. Он, как и многие его предшественники, искал магическую формулу, которая позволяла бы выделить простые числа из бесконечного множества чисел натурального ряда, т. е. из всех чисел, какие можно себе представить. Эйлер написал более ста сочинений по теории чисел.
...Доказано, например, что число простых чисел неограничено, т. е.: 1) нет самого большого простого числа; 2) нет последнего простого числа, после которого все числа были бы составными. Первое доказательство этого положения принадлежит ученым древней Греции (V-Ш вв. до н. э.), второе доказательство - Эйлеру (1708-1783).
Основная теорема арифметики
Всякое натуральное число, отличное от 1, либо является простым, либо может быть представлено в виде произведения простых чисел, причем однозначно, если не обращать внимания на порядок следования множителей.
Доказательство.
Возьмем натуральное число п≠
1. Если n - простое, то это тот случай, о котором сказано в заключении теоремы. Теперь предположим, что n - составное. Тогда оно представлено в виде произведения п = а
b
,
где натуральные числа а и b меньше n. Опять либо a и b - простые, тогда все доказано, либо хотя бы одно из них составное, т. е. составлено из меньших множителей и так далее; в конце концов мы получим разложение на простые множители.
Если число n не делится ни на одно простое, не превосходящее √ n , то оно является простым.
Доказательство. Предположим противное, пусть n - составное и п = аЬ, где 1 ≤b и р - простой делитель числа а, значит, и числа n. По условию п не делится ни на одно простое, не превосходящее √ n . Следовательно, р >√ n . Но тогда а >√ n и √ n ≤ а ≤ b,
откуда п = а b = √ n √ n = п; пришли к противоречию, предположение было неверным, теорема доказана.
Пример 1. Если с = 91, то √ с = 9, ... проверим простые числа 2, 3, 5, 7. Находим, что 91 = 7 13.
Пример 2. Если с = 1973, то находим √ c = √ 1973 =44, ...
так как ни одно простое число до 43 не делит с, то это число является простым.
Пример 3. Найдите простое число, следующее за простым числом 1973. Ответ: 1979.
Простые числа Мерсена
В течение нескольких столетий шла погоня за простыми числами. Многие математики боролись за честь стать открывателями самого большого из известных простых чисел.
Простые числа Мерсена являются простыми числами специального вида M p = 2 p - 1
где р - другое простое число.
Эти числа вошли в математику давно, они появляются еще в евклидовых размышлениях о современных числах. Свое название они получили в честь французского монаха Меренна Мерсена (1589-1648), который долго занимался проблемой современных чисел.
Если вычислять числа по этой формуле, получим:
M 2 = 2 2 – 1 = 3 – простое;
M 3 = 2 3 – 1 = 7 – простое;
M 5 = 2 5 – 1 = 31– простое;
M 7 = 2 7 – 1 = 127 – простое;
M 11 = 2 11 – 1 = 2047 = 23 * 89
Общий способ нахождения больших простых чисел Мерсена состоит в проверке всех чисел M p для различных простых чисел р.
Эти числа очень быстро увеличиваются и столь же быстро увеличиваются затраты труда на их нахождение.
В исследовании чисел Мерсена можно выделить раннюю стадию, достигшую своей кульминации в 1750 г., когда Эйлер установил, что число M 31 является простым. К тому времени было найдено восемь простых чисел Мерсена: " г
р = 2, р= 3, р = 5, р = 7, р = 13, р = 17, р = 19, р =31.
Эйлерово число M 31 оставалось самым большим из известных простых чисел более ста лет.
В 1876 г. французский математик Лукас установил, что огромное число M 127 - с 39 цифрами. 12 простых чисел Мерсена были вычислены с помощью только карандаша и бумаги, а для вычисления следующих уже использовались механические настольные счетные машины.
Появление вычислительных машин с электрическим приводом позволило продолжить поиски, доведя их до р = 257.
Однако результаты были неутешительными, среди них не оказалось новых простых чисел Мерсена.
Затем задача была переложена на ЭВМ.
Самое большое известное в настоящее время простое число имеет 3376 цифр. Это число было найдено на ЭВМ в Иллинойском университете (США). Математический факультет этого университета был так горд своим достижением, что изобразил это число на своем почтовом штемпеле, таким образом воспроизводя его на каждом отсылаемом письме для всеобщего обозрения.
Простые числа Ферма
Существует еще один тип простых чисел с большой и интересной историей. Они были впервые введены французским юристом Пьером Ферма (1601-1665), который прославился своими выдающимися математическими работами.
Пьер Ферма (1601-1665)
Первыми простыми числами Ферма были числа, которые удовлетворяли формуле F n =
+ 1.
F 0 =
+ 1 = 3;
F 1 =
+ 1 = 5;
F 2 =
+ 1 = 17;
F 3 =
+ 1 = 257;
F 4 =
+ 1 = 65537.
Однако, это предположение было сдано в архив неоправдавшихся математических гипотез, но после того, как Леонард Эйлер сделал еще один шаг и показал, что следующее число Ферма F 5 = 641 6 700 417 является составным.
Возможно, что история чисел Ферма была бы закончена, если бы числа Ферма не появились в совсем другой задаче - на построение правильных многоугольников при помощи циркуля и линейки.
Однако ни одного простого числа Ферма не было найдено, и сейчас многие математики склонны считать, что их больше нет.
Решето Эратосфена
Существуют таблицы простых чисел, простирающихся до очень больших чисел. Как подступиться к составлению такой таблицы? Эта задача была, в известном смысле, решена (около 200 г. до н. э.) Эратосфеном, математиком из Александрии. -
Его схема состоит в следующем. Напишем последовательность всех целых чисел от 1 до числа, которым мы хотим закончить таблицу.
Начнем с простого числа 2. Будем выбрасывать каждое второе число. Начнем с 2 (кроме самого числа 2), т. е. четных чисел: 4, 6, 8, 10 и т. д., подчеркиваем каждое из них.
После этой операции первым неподчеркнутым числом будет 3. Оно простое, так как не делится на 2. Оставляя число 3 неподчеркнутым, будем подчеркивать каждое третье число после него, т. е. числа 6, 9, 12, 15... Некоторые из них были уже подчеркнуты, поскольку они являются четными. На следующем шаге первым неподчеркнутым числом окажется число 5; оно простое, так как не делится ни на 2, ни на 3. Оставим число 5 неподчеркнутым, но подчеркнем каждое пятое число после него, т. е. числа 10, 15, 20... Как и раньше, часть из них оказалась подчеркнутой. Теперь наименьшим неподчеркнутым числом окажется число 7. Оно простое, так как не делится ни на одно из меньших его простых чисел 2, 3, 5. Повторяя этот процесс, мы в конце концов получим последовательность неподчеркнутых чисел; все они (кроме числа 1) являются простыми. Этот метод отсеивания чисел известен как «решето Эратосфена». Любая таблица простых чисел создается по этому принципу.
Эратосфен создал таблицу простых чисел от 1 до 120 более 2000 лет назад. Он писал на папирусе, натянутом на рамку, или на восковой дощечке, и не зачеркивал, как это делаем мы, а прокалывал составные числа. Получалось нечто вроде решета, через которое «просеивались» составные числа. Поэтому таблицу простых чисел называют «решетом Эратосфена».
Сколько всего простых чисел? Есть ли последнее простое число, т. е. такое, после которого все числа будут составными? Если такое число есть, то как его найти? Все эти вопросы интересовали ученых еще в глубокой древности, но ответ на них оказалось не так-то просто найти.
Эратосфен был остроумнейшим человеком. Этот современник и друг Архимеда, с которым он постоянно переписывался, был и математиком, и астрономом, и механиком, что считалось естественным для великих мужей того времени. Он первым измерил диаметр земного шара, причем не выходя из александрийской библиотеки, где работал. Точность его измерения была поразительно высокой, даже выше той, с которой измерил Землю Архимед.
Эратосфен изобрел хитроумный прибор - мезолабит, с помощью которого механически решил известную задачу об удвоении куба, чем очень гордился, и потому отдал распоряжение изобразить этот прибор на колонне в Александрии. Мало того, он поправил египетский календарь, добавив один день к четырем годам - в високосный год.
Решето Эратосфена - это примитивное и в то же время гениальное изобретение, до которого не додумался и Евклид, - наводит на общеизвестную мысль, что все гениальное просто.
Эратосфеново решето неплохо поработало на исследователей далеко не простых чисел. Шло время. Шли поиски способов отлова простых чисел. Началось своеобразное соревнование на изыскание наибольшего простого числа с древнейших времен до Чебышева и даже до наших дней.
Открытие П.Л. Чебышева
Итак, число простых чисел бесконечно. Мы уже видели, что простые числа размещаются без какого-либо порядка. Проследим более подробно.
2 и 3 - простые числа. Это единственная пара простых чисел, стоящих рядом.
Затем идут 3 и 5, 5 и 7, 11 и 13, 17 и 19 и т.д. Это так называемые смежные простые числа или близнецы. Близнецов много: 29 и 31, 41 и 43, 59 и 61, 71 и 73, 101 и 103, 827 и 829 и т. д. Самая большая известная сейчас пара близнецов такая: 10016957 и 10 016 959.
Панфутий Львович Чебышев
Как же распределены простые числа в натуральном ряду, в котором не будет ни одного простого числа? Есть ли какой-нибудь закон в их распределении или нет?
Если есть, то какой? Как найти его? Но ответ на эти вопросы не находился более 2000 лет.
Первый и очень большой шаг в разрешении этих вопросов сделал великий русский ученый Панфутий Львович Чебышев. В 1850 г. он доказал, что между любым натуральным числом (не равным 1) и числом, в два раза больше его (т. е. между n и 2n), находится хотя бы одно простое число.
Проверим это на несложных примерах. Примем для n несколько произвольных значений n.
и найдем соответственно значение 2n.
n = 12, 2n = 24;
n = 61, 2n = 122;
n = 37, 2n = 74.
Мы видим, что для рассмотренных примеров теорема Чебышева верна.
Чебышев доказал ее для любого случая, для любого n. За эту теорему его назвали победителем простых чисел. Открытый Чебышевым закон распределения простых чисел был поистине фундаментальным законом в теории чисел после закона, открытого Евклидом, о бесконечности количества простых чисел.
Едва ли не самый добрый, самый восторженный отклик на открытие Чебышева пришел из Англии от известного математика Сильвестра: «...Дальнейших успехов теории простых чисел можно ожидать тогда, когда родится некто, настолько превосходящий Чебышева своей проницательностью и вдумчивостью, насколько Чебышев превосходит этими качествами обыкновенных людей».
Более чем полвека спустя немецкий математик Э. Ландау, крупный специалист в теории чисел, добавил к этому высказыванию следующее: «Первым после Евклида Чебышев пошел правильным путем при решении проблемы простых чисел и достиг важных результатов».
Проблема Гольдбаха
Выпишем все простые числа от 1 до 50:
2, 3, 5, 7, 9, 11, 17, 19, 23, 29, 31, 37, 41, 43, 47.
А теперь попытаемся любое число от 4 до 50 представить в виде суммы двух или трех простых чисел. Возьмем несколько чисел наугад:
Как видим, поставленную задачу мы выполнили без труда. А всегда ли это возможно? Любое ли число можно представить в виде суммы нескольких простых чисел? И если можно, то скольких: двух? трех? десяти?
В 1742 г. член Петербургской академии наук Гольдбах в письме к Эйлеру высказал предположение, что любое целое положительное число, большее пяти, представляет собой сумму не более чем трех простых чисел.
Гольдбах испытал очень много чисел и ни разу не встретил такого числа, которое нельзя было бы разложить на сумму двух или трех простых слагаемых. Но будет ли так всегда, он не доказал. Долго ученые занимались этой задачей, которая названа «проблемой Гольдбаха» и сформулирована следующим образом.
Требуется доказать или опровергнуть предложение:
всякое число, большее единицы, является суммой не более трех простых чисел.
Почти 200 лет выдающиеся ученые пытались разрешить проблему Гольдбаха-Эйлера, но безуспешно. Многие пришли к выводу о невозможности ее решить.
Но решение ее, и почти полностью, было найдено в 1937 г. советским математиком И.М. Виноградовым.
И.М. Виноградов
Иван Матвеевич Виноградов является одним из крупнейших современных математиков. Родился он 14 сентября 1891 г. в селе Милолюб Псковской губернии. В 1914 г. окончил Петербургский университет и был оставлен для подготовки к профессорскому званию.
Свою первую научную работу И.М. Виноградов написал в 1915 г. С тех пор им написано более 120 различных научных работ. В них он разрешил много задач, над которыми ученые всего мира трудились десятки и сотни лет.
Иван Матвеевич Виноградов
За заслуги в области математики И.М. Виноградов всеми учеными мира признан одним из первых математиков современности, избран в число членов многих академий мира.
Мы гордимся нашим замечательным соотечественником.
Заключение.
Из класса - в мировое пространство
Беседу о простых числах начнем увлекательным рассказом о воображаемом путешествии из класса в мировое пространство. Это воображаемое путешествие придумал известный советский педагог-математик профессор Иван Козьмич Андронов (род. в 1894 г.). «...а) мысленно возьмем прямолинейный провод, выходящий из классной комнаты в мировое пространство, пробивающий земную атмосферу, уходящий туда, где Луна совершает вращение, и далее - за огненный шар Солнца, и далее - в мировую бесконечность;
б) мысленно подвесим на провод через каждый метр электрические лампочки, нумеруя их, начиная с ближайшей: 1, 2, 3, 4, ..., 100, ..., 1000, ..., 1 000 000...;
в) мысленно включим ток с таким расчетом, чтобы загорелись все лампочки с простыми номерами и только с простыми номерами; : .
г) мысленно долетим вблизи провода.
Перед нами развернется следующая картина.
1. Лампочка с номером 1 не горит. Почему? Потому что единица не есть простое число.
2. Две следующие лампочки с номерами 2 и 3 горят, так как 2 и 3 - оба простые числа. Могут ли в дальнейшем встретиться две смежные горящие лампочки? Нет, не могут. Почему? Всякое простое число, кроме двух, есть число нечетное, а смежные с простым по ту и другую сторону будут числа четные, а всякое четное, отличное от двух, является составным числом, так как делится на два.
3. Дальше наблюдаем пару лампочек, горящих через одну лампочку с номерами 3 и 5, 5 и 7 и т. д. Понятно, почему они горят: это близнецы. Замечаем, что в дальнейшем они встречаются реже; все пары близнецов, как и пары простых чисел, имеют вид 6n ± 1; например
6*3 ± 1 равно 19 и 17
или 6*5 ± 1 равно 31 и 29, ...;
но 6*20 ± 1 равно 121 и119- эта пара не близнец, так как есть пара составных чисел.
Долетаем до пары близнецов 10 016 957 и 10 016 959. Будут ли и дальше пары близнецов? Современная наука пока ответа не дает: неизвестно, существует ли конечное или бесконечное множество пар близнецов.
4. Но вот начинает действовать закон большого промежутка, заполненного только составными номерами: летим в темноте, смотрим назад - темнота, и впереди не видно света. Вспоминаем свойство, открытое Евклидом, и смело движемся вперед, так как впереди должны быть светящиеся лампочки, и впереди их должно быть бесконечное множество.
5. Залетев в такое место натурального ряда, где уже несколько лет нашего движения проходит в темноте, вспоминаем свойство, доказанное Чебышевым, и успокаиваемся, уверенные, что во всяком случае, надо лететь не больше того, что пролетели, чтобы увидеть хотя бы одну светящуюся лампочку».
Литература
1.
Великий мастер индукции Леонард Эйлер.
2. За страницами учебника математики.
3. Прудников Н.И. П.Л. Чебышев.
4. Сербский И. А. Что мы знаем и чего не знаем о простых числах.
5. Издательский дом «Первое сентября». Математика №13, 2002 г.
6. Издательский дом «Первое сентября». Математика №4, 2006 г.