Простые числа и их свойства

В 1747—1750 гг. Леонард Эйлер провел уникальные числовые раскопки. Он придумал оригинальные методы поиска и обнаружил сразу 61 новую пару дружественных чисел. Примечательно, что среди них оказались и не четные числа: 69 615 и 11 498 355; 87 633 и 12 024 045. Сейчас известно около 1100 пар дружественных чисел. Любопытно, что в 1866 г. итальянский школьник Н. Паганини (однофамилец известного скрипача) нашел пару дружественных чисел 1184 и 1210, которую все, в том числе и выдающееся математики, проглядели! Вот пары дружественных чисел в пределе 100 000: 220 — 2 841 184 — 12 102 620 — 29 245 020 — 55 646 232 — 636 810 744 — 1 085 612 285 — 1 459 517 296 — 1 841 663 020 — 7 608 466 928 — 6 699 267 095 — 7 114 569 615 — 8 763 379 750 — 88 730

Дружественные числа продолжают скрывать множество тайн. Есть ли смешанные пары, у которых одно число четное, а другое не четное? Существует общая формула, описывающая все дружественные пары? На эти и другие вопросы ответы пока не найдены. Из опыта вычисления люди знали, что каждое число является либо простым, либо произведением нескольких простых чисел.

Но они не умели этого доказывать. Пифагор или кто-то из его последователей нашел доказательство этого утверждения. Теперь легко объяснить роль простых чисел в математике: они являются теми кирпичиками, из которых с помощью умножения строят все остальные числа. Хорошо было бы, если все простые числа можно было сосчитать! Пусть их было бы хоть миллион — все равно мы знали бы, что, перемножая эти простые числа, можем получить все остальные.

Но это оказалось не так. Через два столетия после Пифагора греческий геометр Евклид написал книгу «Начала». И одними из утверждений этой книги было следующее: самого большого простого числа не существует. Простые числа в натуральном ряде чисел, расположены очень причудливо. Иногда между ними есть только одно четное число (все простые числа, кроме числа 2, нечетные). Такими близнецами так их зовут в науке, являются: 11 и 13, 17 и 19, 29 и 31. До сих пор не известно, есть ли самые большие близнецы или нет.

А иногда между соседними простыми числами лежит пропасть в миллионы и миллиарды чисел. Первым глубокие результаты о том, как разбросаны простые числа среди остальных натуральных чисел, получил великий русский математик Пафнутий Львович Чебышев, основатель и руководитель русских математических исследований в прошлом веке.

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

Из простых чисел можно получить любое число с помощью умножения. А что будет, если складывать простые числа? Конечно, если брать сколько угодно слагаемых, то можно получить любое число: четные числа получаются путем сложения двоек, а не четные путем сложения одной тройки и нескольких двоек. Но живший в России в XVIII веке математик Гольдбах решил складывать нечетные простые числа лишь попарно.

Он обнаружил удивительную вещь: каждый раз ему удавалось представить четное число в виде суммы двух простых чисел. Вот эти разложения для двухзначных чисел (как это было во времена Гольдбаха, мы считаем 1 простым числом): 4=1+3, 6=1+5, 8=1+7, 10=3+7, 12=5+7, 14=3+11,16=3+13, 18=5+13, 20=3+17, 22=11+11, 24=11+13,26=13+13, 28=23+5, 30=23+7, 32=19+13, 34=17+17,36=17+19, 38=19+19, 40=37+3, 42=37+5, 44=37+7,46=23+23, 48=47+1, 50=47+3, 52=47+5, 54=47+7,56=53+3, 58=53+5, 60=53+7, 62=31+31, 64=61+3,66=61+5, 68=61+7, 70=67+3, 72=67+5, 74=37+37,76=73+3, 78=73+5, 80=73+7, 82=41+41, 84=41=43,86=43+43, 88=87+1, 90=87+3, 92=87+5,94=87+7,96=89+7, 98=97+1.О своем наблюдении Гольдбах написал великому математику XVIII века Леонарду Эйлеру, который был членом Петербургской академии наук. Проверив еще много четных чисел, Эйлер убедился, что все они являются суммами двух простых чисел. Но четных чисел бесконечно много.

По этому вычисления Эйлера давали надежду на то, что свойством, которое заметил Гольдбах, обладают все числа. Однако попытки доказать, что это всегда будет так, ни к чему не привели. Двести лет математики размышляли над проблемой Гольдбаха. И только советскому ученому Ивану Матвеевичу Виноградову удалось сделать решающий шаг. Он установил, что любое достаточно большое натуральное число является суммой трех простых чисел.

Но число, начиная с которого верно утверждение Виноградова, невообразимо велико. По этому пока что, к сожалению, нет надежды даже с помощью самых лучших ЭВМ проверить, верно ли это утверждение для всех остальных чисел. 2. Задачи на простые числа2.

1. Алгоритм поиска простых чисел

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

1) Выписать подряд все целые числа от 2 до n (2,3,4…, n)2) Пусть переменная p изначально равна 2-первому простому числу.

3) Вычеркнуть из списка все числа от 2p до n, делящиеся на p (то есть, числа 2p, 3p, 4p,… .)4) Найти первое невычеркнутое число, большее, чем р, и присвоить значению переменной p это число.

5) Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n.6) Все невычеркнутые числа в списке — простые числа. На практике, алгоритм можно немного улучшить следующим образом. На шаге № 3, числа можно вычеркивать, начиная сразу с числа p2, потому что все составные числа меньше его уже будут вычеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.

2.2. Задача 1Последовательность an определена рекурсивно: a1 = 2, an+1 = - an + 1Доказать, что ai и ajявляются взаимно простыми.Доказательство. Можно доказать, что an+1 = a1a2… an + 1. Из теоремы Евклида следует, что ai и aj являются взаимно простыми.

2.3. Задача 2Числа Ферма Fn (n > 0) имеют вид: Fn = Доказать, что Fi и Fj, = являются взаимно простыми.Доказательство. Для чисел Ферма имеет место соотношение: Fn+1 = F0F1F2… Fn + 2. Из теоремы Евклида следует, что Fi и Fj являются взаимно простыми.

2.4. Задача 3Не используя таблицу простых чисел, покажите, что 1997 — простое число. Простых чисел существует бесконечно много. Действительно, предполагая противное, то есть числа для некоторого натурального n являются всеми простыми числами, тогда согласно основной теореме арифметики число должно делиться на какое-то простое число p, которое в силу предположения будет одним из чисел. Откуда должно делиться на p, что невозможно. Противоречие и означает, что множество простых чисел бесконечно (это доказательство принадлежит Евклиду). Особую трудность представляют задачи, в которых требуется найти простые числа заданного вида. Оказывается, что существует бесконечно много простых чисел вида а+bxn, где a и b — фиксированные взаимно простые натуральные числа, а n — произвольное натуральное число (теорема Дирихле). Например, при натуральных числах n существует бесконечно много простых чисел вида 1996+1997xn. До сих пор неизвестно: является ли множество натуральных чисел вида (числа Ферма) или вида (числа Мерсенна) конечными или нет?2.

5. Задача 4 а) Найдите все простые числа p, чтобы p-28 и p+40 тоже были простыми. б) Докажите, что остаток при делении любого простого числа на 30 не является составным числом.Решение. а)

Так как и, то числа, p и p+40 имеют разные остатки при делении на 3. Поэтому, хотя бы одно из них делится на 3 и в силу простоты равно 3. Так как — наименьшее из них, то =3 и тогда p=31 и p+40=71 тоже простые числа. Ответ: p=31.б) Для простого p имеем p=30q+r, где q — частное при делении на 30, а r — остаток, т. е. r<30. Если r — составное число, то легко проверить, что d=НОД (r;30)¹1. Поэтому d делит нацело 30xq+r, равное p. Но p — простое и d¹1, откуда d=p и p½r. В силу имеем r=p. Это противоречит предположению, что r — составное число. Заключение

Простые числа — это ключ к разрешению многих математических проблем, они также играют большую роль в криптографии (шифровании), благодаря чему интересуют не только математиков, но и военных, разведку и контрразведку. Простое число — то, которое делится без остатка только на единицу и на само себя. Так, к простым числам относятся 2, 3, 5, 7, 11, 13 и так далее по возрастающей. Первым проблему определения простых чисел поставил древнегреческий ученый Эратосфен примерно в 220 году до нашей эры, предложив один из путей определения простых чисел. С тех пор ученые постепенно продвигались вперед, а в последние десятилетия им на помощь в проверке делимости огромных чисел пришли компьютеры. Математики, а позже и специалисты по компьютерному программированию разработали много способов решения этой проблемы, однако все они несут небольшую потенциальную возможность ошибки. В данной работе рассмотрены вопросы:

История возникновения простых чисел. Рассмотрен алгоритм нахождения простых чисел. Названы имена ученых, которые занимались изучениям простых чисел. А также подобраны задачи на простые числа.

Список литературы

Алгебраическая теория чисел: Г. Вейль — Санкт-Петербург, Ком

Книга, 2007 г.- 226 с. Высшая математика: В. С. Шипачев — Москва, Высшая школа, 2007 г.- 479 с. Геометрия чисел: П. М.

Грубер, К. Г. Леккеркеркер — Санкт-Петербург, Наука, 2008 г.- 728 с. Новые методики решения задач о числах. Закон распределения простых и составных чисел. Представление четных чисел суммой и разностью двух простых чисел (доказательство): П. М. Орлов — Москва, Либроком, 2011 г.- 48 с. Обобщения чисел: Л. С.

Понтрягин — Москва, Едиториал УРСС, 2010 г.- 224 с. Распределение простых чисел: А. Э. Ингам — Москва, Либроком, 2009 г.- 162 с. Странности цифр и чисел. Занимательная информация: Тим Глинн-Джонс — Москва, Рипол Классик, 2009 г.- 208 с. Трансцендентные и алгебраические числа: А.

О. Гельфонд — Москва, Ком

Книга, 2006 г.- 224 с. Число и наука о нем. Общедоступные очерки по арифметике натуральных чисел: Г. Н. Берман — Санкт-Петербург, ЛКИ, 2007 г.- 170 с. Числовое поле.

Введение

в методы теории функций пространственного комплексного переменного: В. И. Елисеев — Москва, Москва, 2007 г.- 318 с. Чудеса и тайны в мире чисел: А. П. Ковалев — Санкт-Петербург, Гегемон, 2010 г.- 158 с.