Как сделать число простым
Добавил пользователь Alex Обновлено: 04.10.2024
Натуральные числа, которые больше единицы и не являются простыми, называются составными. Таким образом, все натуральные числа разбиваются на три класса: единицу (имеющую один натуральный делитель), простые числа (имеющие два натуральных делителя) и составные числа (имеющие больше двух натуральных делителей) [1] . Изучением свойств простых чисел занимается теория чисел. Как простых, так и составных чисел бесконечно много.
Последовательность простых чисел начинается так:
Свойство числа быть простым называется простотой. Простой, но медленный метод проверки простоты заданного числа n известен как перебор делителей; существуют и более эффективные алгоритмы.
Простые числа широко используются в математике и в смежных науках — например, во многих алгоритмах информационных технологий, таких как криптосистема с открытым ключом, которая использует такие свойства, как сложность разложения чисел на простые множители [4] .
В школе это проходят в 5 или 6 классе, в зависимости от программы обучения.
И интересно, что если спросить школьников, что такое простые числа, то они, скорее всего, ответят правильно.
А вот взрослые задумаются и не факт, что вспомнят точное определение. Так что это статья скорее для них.
Простые числа — это.
Итак, вот как выглядит официальное определение:
Простые числа – это такие числа, которые имеют только два делителя. Один из них – единица, а другое – само число.
Чтобы было более понятно, приведем простой пример. Для чисел 5 и 7 надо найти все возможные делители, чтобы в результате образовалось целое число.
Если вы попробуете решить эту задачку, то получите, что 5 и 7 делятся только на 1 и 5, и 1 и 7 соответственно. Во всех других случаях вы получите дробное число. И это как раз означает, что числа 5 и 7 относятся к простым.
А вот попробуем по той же схеме разобрать числа 6 и 9. В первом случае мы получим, что 6 можно поделить на 1, 2, 3 и 6, а число 9 – на 1, 3 и 9. И это уже противоречит определению простых чисел, значит, 6 и 9 таковыми не являются.
Они называются в математике – СОСТАВНЫМИ ЧИСЛАМИ.
Вот и все, что мы хотели рассказать о ПРОСТЫХ ЧИСЛАХ в математике.
Эта статья относится к рубрикам:
Комментарии и отзывы (1)
Математика весьма хитрая наука, да и простые числа не такие уж и простые, понимание простых и составных чисел привело человечество к тому техническому прогрессу, что окружает нас сейчас.
Как находить простые числа
Автор работы награжден дипломом победителя II степени
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Всякий, кто изучает простые числа, бывает, очарован и одновременно ощущает собственное бессилие. Определение простых чисел так просто и очевидно; найти очередное простое число так легко; разложение на простые сомножители - такое естественное действие.
Почему же простые числа столь упорно сопротивляются нашим попыткам постичь порядок и закономерности их расположения? Может быть, в них вообще нет порядка, или же мы так слепы, что не видим его?
(Ч. Узерелл.1982)
Данная тема была выбрана потому, что существует тайна распределения простых чисел в ряду натуральных чисел - в одних частях ряда их больше, в других – меньше. Возник интерес к способам нахождения простых чисел, возможности создания модели, с помощью которой можно найти все простые числа и как полученные знания помогут разобраться с решением некоторых олимпиадных задач.
Исходя, из этого актуальность исследования обусловлена наличием в работе представлений о поисках простых чисел и подборкой олимпиадных задач по теме разных уровней сложности.
Цель: сбор и систематизация сведений о нахождении множества простых чисел для овладения способами решения олимпиадных задач с простыми числами.
1. Проанализировать источники исследования.
2. Найти сведения об истории отыскания простых чисел в интернете.
3. Попытаться составить модели для нахождения простых чисел с помощью найденных сведений.
4. Найти и решить олимпиадные задачи с простыми числами.
Объект исследования: простые числа
Предмет исследования: олимпиадные задачи с простыми числами разных уровней сложности.
Гипотеза: все простые числа нужно отыскивать одно за другим.
Методы исследования: изучение источников по теме исследования, анализ полученных материалов, моделирование.
Практическая значимость: материалы будут способствовать повышению интереса к математике и помогут разобраться с решением некоторых олимпиадных задач. Возможно использование материала на внеклассных мероприятиях, занятиях внеурочной деятельности.
Основная часть
Глава 1. Теоретические сведения
Интерес к изучению простых чисел возник у людей в глубокой древности. И вызван он был не только практической необходимостью. Привлекала их необычная магическая сила. Числа, которыми можно выразить количество любых предметов.
Одним из первых свойств чисел, открытым человеком, было то, что некоторые из них могут быть разложены на два или более множителей, например:
6=2 3, 9=3∙3, 30=2∙15=3∙10.
А, например, числа 3,7,13,37 не могут быть разложены подобным образом.
Определение. Простым называется число, которое делится только само на себя и на единицу.
Числа, не являющиеся простыми, называются составными. Всякое составное число имеет не меньше двух делителей отличных от 1.
1 – особое число, оно не является ни простым, ни составным.
Простые числа-близнецы это пара простых чисел, отличающихся на 2.
Если натуральное число a делится на натуральное число b , то число b называют делителем числа a , а число а – кратным числа b .
Таким образом, простые числа – это как бы “кирпичики” для строительства всех натуральных чисел. Например, число N = 500 представимо в виде такого произведения: N = 2 2 ∙5 3
Представление составного числа в указанном виде называют разложением числа на простые множители.
Свойства делимости.
Если в сумме натуральных чисел каждое слагаемое делится на некоторое число, то и сумма делится на это число.
Если уменьшаемое и вычитаемое делится на одно и то же число, то и разность делится на это число.
Если в произведении натуральных чисел один из множителей делится на некоторое число, то и произведение делится на это число.
Основная теорема арифметики.
Каждое натуральное число, отличное от 1, может быть представлено в виде произведения простых множителей, и притом только единственным образом (с точностью до порядка следования сомножителей).
Глава 2 Модели простых чисел
Эратосфен Кире́нский древнегреческий ученый, жил в третьем веке до новой эры в Александрии.
В математике Эратосфена интересовал вопрос о том, как найти все простые числа среди натуральных чисел от 1 до… . Он придумал для этого следующий способ: сначала вычеркивают все числа, делящиеся на 2 (исключая само число 2). Потом берут первое из оставшихся чисел (а именно 3). Ясно, что это число - простое. Вычеркивают все идущие после него числа, делящиеся на 3. Первым оставшимся числом будет 5. Вычеркивают все идущие после него числа, делящиеся на 5, и т.д. Числа, которые уцелеют после всех вычеркиваний, и являются простыми. Так как во времена Эратосфена писали на восковых табличках и не вычеркивали, а "выкалывали" цифры, то табличка после описанного процесса напоминала решето. Поэтому метод Эратосфена для нахождения простых чисел получил название "решето Эратосфена". (Приложение 1).
Древнейший алгоритм такого поиска был предложен 2000 лет назад.
Итак, Решето Эратосфена работает как своего рода аналоговая вычислительная машина. И, значит, вот что изобрел великий грек: он изобрел счетную машину. Простые числа располагаются на числовом ряду весьма причудливым образом.
Найти редкие оазисы простых чисел, затерянные в обширных пустынях составных чисел, нелегко. Решето Эратосфена позволяет это сделать! Но всё же найти все простые числа таким способом нельзя.
Анализируя Решето видно, что все простые числа либо на 1 меньше, либо на 1 больше чисел, кратных 6, т.е. 6n – 1, 6n + 1.
6 ∙ 1–1=5, 6 ∙ 1+1=7, 6 ∙ 2–1=11, 6 ∙ 2+1=13, 6 ∙ 3–1=17, 6 ∙ 3+1=19,
6 ∙ 4–1=23, 6 ∙4+1=25, 6 ∙5–1=29, 6 ∙ 5+1=31,
6 ∙ 6–1=35 – составное число.
2 2 – 1 = 3, 2 5 – 1 = 31, 2 7 – 1 = 127, . .
Но, 2 11 – 1 составное. 2 11 – 1 =2047 = 23∙ 89.
3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607.
2 67 – 1 = 193707721 ∙ 761838257287.
2 43112609 – 1 (46 -е число Мерсенна) – это самое большое найденное простое число.
В течение почти 200 лет математики считали, что число Мерсенна 2 67 – 1 простое. В 1903 г профессор Коул доказал, что это число имеет два простых множителя: 193707721 и 761838257287. Коул, чтобы разложить число на множители потратил все воскресенья в течение трёх лет.
Маре́н Мерсе́нн (1588 — 1648) — французский математик, физик, философ и теолог.
Числа вида 2 р – 1, где p – простое число, называются числами Мерсенна, впервые заметившего, что среди таких чисел много простых.
Как видно, среди первых девяти чисел Мерсенна только два составные.
В настоящее время составлены специальные программы для поиска чисел Мерсенна. Последнее число найдено в 2018 г.
Глава 3. Как искали?
Изучали таблицу простых чисел, двигаясь по натуральному ряду. (Приложение 2)
Простые числа в среднем встречаются все реже.
Числа-близнецы - два простых числа идут через одно, (например, 17 и 19, 29 и 31), а иногда подряд идет миллион составных чисел.
Простые числа могут оканчиваться только на следующие цифры: 1, 3, 7 или 9. Если число оканчивается на 2, 5 или 0, то оно не может быть простым, просто потому, что делится без остатка соответственно на 2, на 5 или на 10 (естественно, кроме 2 и 5).
Глава 4. Как применяются простые числа в жизни человека
Люди поняли, что простые числа являются не только ключом к выживанию, но и огромным количеством строительного материала в математике. Каждое число, по сути, представляет собой совокупность простых чисел, а совокупность чисел составляет математику, а из математики получается целый научный мир.
Простые числа находят спрятанными в природе, но человечество научилось их использовать.
Криптография, ( криптография — обеспечение конфиденциальности и целостности данных) благодаря которой наши кредитные карточки остаются в безопасности, когда мы покупаем что-нибудь онлайн, использует простые числа. Каждый раз, когда вы вводите номер своей кредитной карты на вебсайте, вы полагаетесь на то, что простые числа сохранят ваши тайны и информацию о вас в секрете. Для кодирования вашей кредитной карты ваш компьютер получает публичный номер Н с вебсайта, который и будет использоваться для совершения операций с вашей кредитной картой.
Причиной, по которой такое кодирование является настолько безопасным, является то, что очень легко перемножить простые числа между собой, но разложить число на простые множители практически невозможно.
Шифрование – это не единственная область применения простых чисел на практике. Простые числа используются в компьютерном моделировании различных процессов. Так же без них не обойтись и в машиностроении – например, количество лопаток турбин реактивных самолётов должно составлять простое число. Если этим правилом пренебречь, то возникает резонанс, разрушающий лопатки турбины.
Глава 5. Какие задачи нашли?
1. Докажите, что любое простое число, большее 3, можно записать в одном из двух видов: 6n + 1 либо 6n – 1, где n – натуральное число.
2. Найти все такие натуральные числа p, что p и 5p + 1 – простые.
3. В книге рекордов Гиннесса написано, что наибольшее известное простое число равно 23021377 – 1. Не опечатка ли это?
4. Найдите все простые числа, которые отличаются на 17.
5. Найдите все натуральные n, при которых 2n – 1 и 2n + 1 – простые.
Какие задачи смогли решить?
Олимпиадных задач на простые числа много.
Задачи разного уровня сложности.
Чтобы решить любую задачу необходимо много знать.
Глава 6. Решение олимпиадных задач с простыми числами
Найти все такие натуральные числа p, что p и 5p + 1 – простые.
Решение: если p нечётно, то 5p + 1 чётно, значит, p чётное число, а чётное и одновременно простое число только при p = 2.
Найти все такие натуральные числа p, что p и 3p² + 1 – простые.
Решение: если p нечётно, то 3p² + 1 чётно.
В книге рекордов Гиннесса написано, что наибольшее известное простое число равно 23021377 – 1. Не опечатка ли это?
Решение: Какая последняя цифра у числа 23021377 – 1? Любая степень числа, оканчивающегося цифрой 1, тоже оканчивается цифрой 1. Поэтому разность 23021377 – 1 оканчивается на 0 и, следовательно, не является простым числом.
Найдите все простые числа, которые отличаются на 17.
Решение: такие числа имеют разную чётность.
Найдите все простые числа, которые равны сумме двух простых чисел и разности двух простых чисел.
Решение: указанное простое число p нечётно, поэтому в сумме и разности участвуют числа разной чётности. Итак, p = q + 2 = r – 2. Отсюда видно, что числа дают разные остатки при делении на 3, значит, одно из них кратно 3, а так как оно простое, то равно 3.
Найдите все простые числа, которые нельзя записать в виде суммы двух составных.
Решение: докажем, что любое простое число p > 11 представляется в виде суммы двух составных. Поскольку любое такое число нечётно, то число p – 9 чётно и, следовательно, составное. Поэтому p = (p – 9) + 9 – искомое представление.
С другой стороны, непосредственно проверяется, что числа 2, 3, 5, 7 и 11 не представимы в виде суммы двух составных.
Докажите, что при n > 2 числа 2n – 1 и 2n + 1 не могут быть простыми одновременно.
Решение: из трёх последовательных чисел 2n – 1, 2n, 2n + 1 одно делится на 3. Но 2n на 3 не делится. Значит, одно из двух оставшихся чисел кратно 3.
Почему мы не смогли получить достоверную модель простых чисел?
Простые числа в будущем: простые числа несут в себе много тайн и их интересно узнать; продолжить изучение способов нахождения простых чисел и изучение методов решения олимпиадных задач с простыми числами .
Что представляют собой простые и составные числа. Делитель простого и составного числа
Все натуральные числа (исключение составляет лишь единица) относятся к простым или составным. При этом, основным различием между двумя большими группами чисел является количество делителей. Делители, также, подразделяются на составные и простые. Чтобы само определение составных чисел было более понятным, можно предварительно просмотреть понятия делителей и кратных.
Простыми числам являются натуральные числа больше единицы, имеющие два положительных делителя – себя и 1. Например, делителем чисел 7, 11, 19, 131 выступает только единица и само число.
Составными числами являются натуральные числа больше единицы, но в отличие от простого, они имеет больше положительных делителей - оно делится на единицу, на само себя и, как минимум, на одно натуральное число. Например, разложение составных чисел на делители можно представить следующим образом - число 14 делиться на 1, 2, 7, 14, а число 24 делиться на 1,2, 3, 8, 12, 6, 4.
Так, число 2 является единственным первым наименьшим четным простым числом. Все остальные простые числа принадлежат к нечетной группе. А в числовом ряду составных чисел наименьшим первым числом выступает 4. В числовом ряду можно выделить первые составные и простые числа, но определить последние числовые значения невозможно.
Следует обратить внимание на число 1 – оно занимает особое место, поскольку не относится ни к составным, ни к простым числам. Наличие единственного простого делителя – единицы, является главным отличием от остальных натуральных чисел.
Любое натуральное число n больше единицы представляет простые или составные числа. Учитывая свойства делимости, можно подытожить, что единица и в всегда будут являться делителями любого числа в. То есть, любое число, кроме 1, будет иметь минимум два делителя - единицу и самого себя.
Учитывая все вышесказанное, можно дать следующие определения. Простыми являются числа, натуральное числовое значение, которое обладает только двумя положительными делителями. Составными являются числа – это натуральное числовое значение, которое обладает минимально тремя положительными делителями.
Так, любое число, которое не будет причислено к составным, можно отнести к простым числам. Исключение составляет лишь единица.
Таблица простых чисел
Часто, при выполнении различных заданий, оптимальным решением станет использование таблицы простых чисел. Так как простых чисел множество, таблицы обычно ограничиваются числовым значением 100, 1000 или 10 000. Так, на Рис.1 представлена Таблица простых чисел до 1000.
Рис. 1. Таблица простых чисел до 1000
Представить таблицу для всех существующих простых чисел не является возможным. Поэтому, когда числовой ряд достигает 10000 или 1000000000, следует использовать решето Эратосфена.
Самое время будет рассмотреть Теорему 1 и Теорему 2, которые объяснят последнее утверждение.
Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.
Для данной теоремы можно привести следующее доказательство. Допустим, что в – это отличный от единицы наименьший делитель для числа с. Необходимо привести доказательство, используя методику противного, что является простым числом.
Допустим, что является натуральным составным числом. Отсюда следует, что для натурального числа в есть простой делитель составного числа, который отличен как от в, так и от единицы. Данный делитель можно обозначить в1. Далее, требуется, чтобы выполнялось условие 1
(Рис.2).2 3 4 5 6 7 8 9 10 11 12 12 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
Далее выполняется последовательное зачеркивание всех чисел, кратных 2 (Рис.3).
Рис. 3 Зачеркивание чисел, кратных двум
Затем, необходимо поочередно вычеркнуть все числа, кратные 3 (Рис. 4).
Рис. 4. Зачеркивание чисел, кратных 3
Также, необходимо поступить с числами, которые кратны 5 (Рис. 5).
Рис. 5. Зачеркивание чисел, кратных 5
На последнем этапе зачеркиваются числа, кратные 7 и 11 (Рис. 6). В итоге будет получена окончательная таблица натуральных простых чисел от 2 до 50.
Рис. 6. Зачеркивание чисел, кратных 7 и 11
Далее стоит остановиться на формулировке Теоремы 3 и ее доказательстве.
Наименьший положительный и отличный от 1 делитель основного числа a не превосходит √a, где √a арифметическим корнем заданного числа.
Необходимо обозначить b наименьший делитель составного числа a. Существует такое целое число q, где a=b·q, причем имеем, что b≤q. Недопустимо неравенство вида b>q, так как происходит нарушение условия. Обе части неравенства b≤q следует умножить на любое положительное число b, не равное 1. Получаем, что b·b≤b·q, где b 2 ≤a и b≤√a
Доказанная теорема показывает, что при поочередном вычеркивании чисел из таблицы, необходимо начинать с числа, которое будет равно b² и должно соответствовать неравенству b² ≤ a. Если вычеркивание начнется с чисел, кратных 2, то в первую очередь будет вычеркнуто число 4, а если с кратных 3, то – число 9.
Используя методику Эратосфена при составлении простой числовой таблицы, можно обнаружить, что в процессе вычеркивания натуральных составных чисел, останутся лишь те простые числа, которые не будут превосходить значение квадратного корня из n.
Читайте также: