Простые и составные числа, свойства простых чисел — студенческий портал

Представим себе такую историю…

– Саша, давай с тобой сыграем в одну игру, – предложил другу Паша.

– Что за игра? – решил уточнить Саша.

– В общем, смотри: перед тобой таблица, в которой записан ряд натуральных чисел начиная с 2 и заканчивая 100, – начал Паша. – Тебе нужно взять число, а потом вычёркивать все числа, которые на него делятся. Вот, например, возьмём число 2, обведём его в кружочек, чтобы не потерять, и вычеркнем из этой таблицы все числа кратные двум.

– Понятно – прошептал Саша. – Значит, вычёркиваю все чётные числа.

– Хорошо! – продолжил Паша. — Следующее незачёркнутое число – 3. Обведём его в кружок. А теперь из оставшихся чисел тебе нужно вычеркнуть все числа кратные 3.

– Так… – начал размышлять Саша. — Если сумма цифр числа делится нацело на 3, то и само число делится нацело на 3.

И Саша принялся вычёркивать числа.

– Молодец! – поддержал друга Паша. – Следующее незачёркнутое число – 5. Значит, из оставшихся чисел тебе нужно вычеркнуть все числа кратные 5.

– Ага! Если запись натурального числа оканчивается цифрой 0 или 5, то это число делится нацело на 5 – сказал Саша. И занялся вычёркиванием чисел.

– Отлично! – сказал Паша. – Перейдём к следующему незачёркнутому числу. И это 7. То есть теперь ты должен вычеркнуть из оставшихся чисел все числа кратные 7.

– Ну, признака делимости на 7 мы ещё не знаем, – задумался Саша, – значит, буду просто вычёркивать все числа, которые делятся на 7.

И Саша принялся вычёркивать числа.

– Ну вот и всё! – сказал Паша. – Наша игра окончена. Посмотри, в таблице у тебя остались только числа, которые делятся на 1 и сами на себя.

– И точно! – заметил Саша.

– То, что мы сейчас с тобой делали, называют «решето Эратосфена», – продолжил Паша.

– А почему решето? – спросил Саша. – Разве эта таблица с дырочками?

– Название «решето» метод получил потому, что, согласно легенде, Эратосфен (это древнегреческий математик) писал числа на дощечке, покрытой воском, и прокалывал дырочки в тех местах, где были написаны числа, имеющие больше двух делителей. Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все числа, имеющие больше двух делителей, а оставались только простые числа. Эратосфен дал таблицу простых чисел до 1000.

– А что это за простые числа? – спросил Саша.

– Давай спросим у Мудряша, – предложил Паша. – Он точно сможет нам помочь.

– Ребята, прежде чем я вас познакомлю с простыми числами, давайте немного разомнёмся и выполним устные задания, – предложил Мудряш.

 – Давайте сверимся! – сказал Мудряш. — Посмотрите, что у вас должно было получиться!

– Ну а теперь вернёмся к вашему вопросу, – начал Мудряш. — Как вы уже знаете, все натуральные числа имеют делители. И вы, кстати, уже научились их находить с помощью свойств и признаков делимости. Меньше всего делителей у числа 1. Единственным его делителем является само это число. А вот любое другое натуральное число а имеет по крайней мере два делителя – 1 и само число а.

– А ведь действительно, – сказали мальчишки, – если число а разделить на 1, то получится а, а если число а разделить на а, то получится 1.

– Некоторые натуральные числа имеют ровно два делителя, – продолжил Мудряш. – Например, число 13 делится только на 1 и на 13. Другие же числа могут иметь больше двух делителей. Например, числа 6 и 18. Число 6 имеет четыре делителя: 1, 2, 3 и 6. А вот число 18 – шесть делителей: 1, 2, 3, 6, 9 и 18.

– Запомните! – сказал Мудряш. – Натуральное число называют простым, если оно имеет только два натуральных делителя: единицу и само это число.Натуральное число называют составным, если оно имеет больше двух натуральных делителей.

– Может, вы сможете привести примеры простых и составных чисел? – спросил Мудряш у ребят.

– Простыми числами являются, – начали мальчишки, – 2, 3, 5, 7, 11, 13, 17, 19 и так далее. А составными числами будут: 8, 12, 16 и так далее.

– Молодцы! – похвалил ребят Мудряш. — Обратите внимание: число 2 – это наименьшее простое число. Кстати, это единственное чётное простое число. Потому что любое другое чётное число имеет по крайней мере три делителя: число 1, число 2 и само число. Простых чисел бесконечно много. Наибольшего простого числа не существует.

– Таким образом, – продолжил Мудряш, – все натуральные числа, в зависимости от количества делителей, можно разбить на три группы: 1 (один делитель), простые числа (два делителя) и составные числа (три и более делителей).

– А как узнать, глядя на число, простое оно или составное? – спросили мальчишки.

– Хороший вопрос! – обрадовался Мудряш. – Если число небольшое, то можно перебрать одно за другим все числа, которые могут быть его делителями. Например, возьмём число 11.

Его делители могут встретиться лишь среди чисел от 1 до 11. Понятно, что 1 и 11 – делители числа 11. А перебирая одно за другим числа от 2 до 10, мы убедимся, что ни на одно из них число 11 не делится.

Так что у числа 1 только два делителя. Значит, оно простое.

– А если число большое? – решили уточнить мальчишки.

– Если число большое, то понятно, что перебирать числа в поисках его делителей придётся слишком долго, – начал Мудряш.  – А чтобы не тратить время на эту однообразную работу, пользуются таблицей простых чисел. На экране вы как раз и видите её.

– А как пользоваться этой таблицей? – спросили ребята.

– Здесь нет ничего сложного, – ответил Мудряш. — Вы должны просто посмотреть, есть в таблице интересующее вас число или нет. Если его в таблице нет – значит, оно составное. Конечно, учить эту таблицу наизусть не стоит. Но если вы запомните хотя бы все однозначные и двузначные простые числа, то это значительно упростит вычисления по многим темам школьной программы.

– Интересно, что последовательность простых чисел имеет много необычных свойств и тайн. Так, например, учёные Древней Эллады отметили, что среди простых чисел много таких, разность которых равна двум, например: 3 и 5, 5 и 7, 11 и 13, 17 и 19 и так далее. Подобные пары чисел называют простыми числами близнецами.

– А для чего вообще нужны простые числа? – спросили ребята.

– Простые числа помогают в поиске делителей, – начал Мудряш. — Так, например, возьмём число 510. Понятно, что оно составное, то есть имеет более двух делителей. Если мы представим это число в виде суммы разрядных слагаемых, то заметим, что оно не делится на 7. А значит, уже не нужно проверять его делимость ни на 14, ни на 21, ни на 28 и так далее.

– Запомните! – сказал Мудряш. – Любое составное число можно представить в виде произведения простых чисел, то есть разложить на простые множители.

– А как это делают? – спросили ребята.

– Число 110 можно разложить в произведение чисел не равных единице. Например, 110 равно произведению 10 и 11. В свою очередь, число 10 тоже составное число. Значит, его тоже можно разложить в произведение, то есть .

А тогда число 110 можно представить в виде произведения 2, 5 и 11. Обратите внимание: в правой части равенства все множители – простые числа. То есть мы с вами сейчас записали число 110 в виде произведения простых чисел.

Говорят, что число 110 разложили на простые множители.

– Запомните! Разложить натуральное число на простые множители – значит представить его в виде произведения простых множителей.

– При разложении числа на простые множители удобно пользоваться схемой, – продолжил Мудряш. — Давайте я вам покажу эту схему на примере разложения числа 2940.

– Итак, 2940 — чётное число, значит, оно делится на 2. При делении получим 1470. Число 1470 также чётное. Значит, можем поделить его на 2. Получим 735. Заметим, что сумма цифр числа 735 равна 15.

Значит, это число делится на 3. Разделим его. Получим 245. Число 245 оканчивается цифрой 5. Значит, оно делится на 5. Разделим. Получим 49. В свою очередь, число 49 делится на 7. Число 7 также делится на 7.

И в результате получим 1.

– Обратите внимание: числа, расположенные друг под другом слева от вертикальной черты, получаются при последовательном делении на простые числа, записанные справа от черты.

– Теперь можем записать число 2940 в виде произведения простых множителей. . Заметим, что в разложении числа присутствуют одинаковые множители — это две 2 и две 7. Как правило, одинаковые множители заменяют их степенями. Тогда .

– А все составные числа можно разложить на простые множители или есть исключения? – спросили мальчишки.

– Любое составное число можно разложить на простые множители, – ответил Мудряш. – При этом каждое число имеет своё, единственное разложение на простые множители, если не учитывать, в каком порядке они записаны. Утверждение о единственности разложения на простые множители называют основной теоремой арифметики.

А теперь, ребята, давайте посмотрим, как вы всё поняли, и выполним задание.

Итак, заполните таблицу. Если значение выражения — простое число, то во втором столбце таблицы поставьте знак «галочка», если составное – то в третьем столбце.

Решение: первое числовое выражение — сумма двух частных: 14 и 2, и 32 и 8. Первое частное равно 7, второе – 4. Тогда сумма равна 11. Число 11 – это простое число.

Следующее выражение: разность числа 25 и суммы частного чисел 6 и 2, и произведения 2 и 5. Частное равно 3, произведение – 10. Тогда сумма равна 13. Осталось вычислить разность. 25 минус 13 равно 12. Число 12 составное.

И последнее выражение: произведение суммы чисел 45 и 28, и разности числа 22 и произведения 3 и 7. Сумма равна 73. Произведение 3 и 7 равно 21. А разность 22 и 21 равна 1. Тогда произведение 73 и 1 равно 73. Число 73 простое.

Источник: https://videouroki.net/video/04-prostye-i-sostavnye-chisla.html

Простые числа — свойства, последовательность и примеры

Простые числа – это натуральные числа, их можно разделить только на два значения: единицу и себя. К натуральным относят те, которые используются во время счета, поэтому должно выполняться требование, чтобы они были положительными и целыми. Делители также не должны быть отрицательными и дробными.

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

Кроме того, используются на системах, защищающих транспортные средства от угонщиков, создают преграду для атак вирусов и взломов компьютерных сайтов. При попытке продолжить разложение простых чисел или определить закономерность появления, возникают новые способы математических расчетов.

Простые и составные числа — что это такое

Математика предлагает начинать знакомиться с данными понятиями в средней школе, в 5 или в 6 классе. 

Проверка на принадлежность к определенному множеству достаточно простая:

1. Простые числа можно делить только на 1 и на такое же число. Например 3 и 7 — простые числа, 3 делится на 1 и на 3, 7 делится на 1 и на 7.

2. Составные числа можно делить не только на себя и единицу. При этом не должно получаться остатка. Они делятся на одно или несколько значений. Например, 8 и 6 относят к составным. Восьмерка делится на 1, 2, 4, 8; шестерка – на 1, 2, 3 и 6.

Определение простых чисел позволяет исключить из их ряда единицу. Она характеризуется наличием только одного делителя, не являющегося отрицательным значением. Получить ее можно, используя только один способ, умножив саму на себя.

Простые двузначные числа определяются по внешнему виду:

1. Если оканчиваются четной цифрой, то точно являются составными. То же касается и значений, имеющих больше двух знаков.

2. Если на конце находится цифра 5, то она входит в число делителей.

Такие простые способы помогают легко классифицировать многозначные показатели.

Некоторые двузначные вводят в заблуждение с первого взгляда, если оканчиваются на единицу. Кажется, что разложить на множители их невозможно. Но есть исключения, например: 21, 81. Чем дальше, тем больше отклонений от этой закономерности.

Последовательность простых чисел

• Есть целые алгоритмы, помогающие получать новое, ранее неизвестное значение. 
• Существуют таблицы, в которых собраны найденные числа, имеющие не больше двух делителей, например, до 200, 1000 или больше. 

Последовательность можно продолжать бесконечно, начинается она так: 2, 3, 5, 7, 11, 13, 17, 19 и т. д.

Наименьшее и наибольшее простое число

Самым меньшим значением, делящимся на себя и 1, является 2. Это единственное простое значение, являющееся четным. Остальные всегда делятся на два, то есть получают третий делитель. 

Простых чисел много и их количество стремится к бесконечности, потому узнать самое большое невозможно.

Нескончаемость ряда была доказана еще до нашей эры Евклидом. Он предложил перемножить все известные исследуемые значения и прибавить к ним единицу. 

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

В настоящее время известно значение, имеющее около 25 миллионов знаков. Оно относится к наибольшему из открытых наукой, это 282 589 933

Множество простых чисел

Множествами называются совокупности элементов, объединенных в одно целое общими свойствами. 

Для изучаемых объектов к ним относятся:

• принадлежность к натуральным;
• наличие максимум двух делителей.

Простые числа можно определить, используя решето Эратосфена. Нужно выписать в ряд все значения, с которыми предстоит работать. Выбрать самое маленькое и вычеркнуть его, затем продолжать действие, убирая кратные ему. 

Например, в ряду от 1 до 100 первым таким объектом будет 2. Поэтому и вычеркивать нужно значения, кратные двойке, то есть те, которые делятся на нее. 

По окончании из оставшихся выбрать новое простое, искать кратные ему и также убирать. Повторять, пока это представляется возможным. 

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

Эратосфен использовал свое открытие следующим образом. Он брал папирус, записывал на нем необходимые значения, при отборе прокалывал неподходящие острым предметом (отсюда название «решето Эратосфена»). Поэтому они как будто просеивались через сито, и в списке оставались видимыми только необходимые.

Некоторые свойства простых чисел

Выделяют свойства, объединенные в теоремы, постулаты. Многие являются основой математических правил, используемых в настоящее время. 

1. Изучением занимается теория чисел, при использовании формул простые числа обозначаются буквой n.
2. Известны следующие правила:

1. Если рассматривать два простых числа (n), одно из которых делится на другое, то можно утверждать, что они равны.

2. Все являются нечетными, за исключением двойки.

3. Можно выделить пары, разница между которым равна 2. При их сложении получается значение, кратное трем. Их так и называют парными или близнецами. Исключение составляют две первые цифры в ряду, 3 и 5, так как сумму, полученную при их сложении, нельзя разделить на 3.

4. Для каждого натурального значения (N), большего единицы, существует n, превышающее его. При этом удвоенное натуральное будет больше n.

5. Если одно из двух N делится на n, то их произведение также будет делиться на него.

6. Любое N, за исключением единицы, можно отнести к n или представить в виде их произведения.

7. Если взять составное число и разложить его на множители n, то среди них окажется один, квадрат которого будет меньше первоначального составного.

8. Некоторые n имеют пары, которые можно найти, перевернув n наоборот. Например, 13 и 31, 37 и 73. То же самое касается трехзначных n: 107 и 701, 709 и 907.

9. Если N возвести в степень, представленную n, а затем вычесть N, то полученное значение будет делиться на используемое n. Это правило представляет собой малую теорему Ферма.

Действия с простыми числами

Можно использовать разные арифметические действия, складывать, умножать, вычитать, делить. Простые числа могут являться основанием и показателем степени. 

Извлечь корень из них невозможно.

Таблица простых чисел до 1000

Таблица простых числе до 10000

Источник: https://nauka.club/matematika/prostye-chisla.html

math4school.ru

Немного теории

Простое число – это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. Все остальные натуральные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы разбиваются на простые и составные. Изучением свойств простых чисел занимается теория чисел.

Перечень первых 1229-ти простых чисел приведён в таблице простых и парных простых чисел, не превосходящих 10000.

Приведём некоторые свойства простых чисел.

• Основная теорема арифметики. Каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей.
• Простых чисел бесконечно много.
• В натуральном ряде чисел можно найти последовательности не содержащие простых чисел любой длины.
• Если p – простое, и p делит a·b, то p делит a или b.
• Mалая теорема Ферма. Если p – простое, a – натуральное, то ap – a делится на p.
• Теорема Вильсона. Натуральное p > 1 является простым тогда и только тогда, когда (p – 1)! + 1 делится на p.
• Постулат Бертрана. Если n > 1 – натуральное, то существует простое p, такое, что n < p < 2n.
• Теорема Дирихле о простых числах в арифметической прогрессии. Любая арифметическая прогрессия вида a, a + q, a + 2q, a + 3q, … , где a, q > 1 – целые взаимно простые числа, содержит бесконечно много простых чисел.
• Теорема Ферма. Каждое простое число вида 4k + 1 есть сумма двух квадратов натуральных чисел.
• Всякое простое число, большее 3, представимо в виде 6k + 1 или 6k – 1, где k – некоторое натуральное число.
• Число, следующее за простым, не может быть квадратом или более высокой степенью с основанием, большим 2.
• Число, предшествующее простому, не может быть кубом или более высокой нечётной степенью с основанием, большим 1.

Задачи с решениями

1. Три простых числа, каждое из которых больше 10, образуют арифметическую прогрессию. Докажите, что разность прогрессии делится на 6.

Решение

Все данные простые числа нечётные, поэтому их разность делится на 2. Покажем, что она делится и на 3. Пусть данные числа a, a + d, a + 2d. Ни одно из них не делится на 3, поэтому при делении на 3 даёт остаток или 1, или 2.

Следовательно, по крайней мере, два из этих чисел дают при делении на 3 одинаковые остатки. Разность этих чисел, равная d или 2d, делится на 3. Поскольку 2 на 3 не делится, то d делится на 3.

2. Докажите, что для произвольного натурального числа n найдётся натуральное m такое, что nm + 1 – составное число.

Решение

• Можно выбрать m = n + 2, тогда
• nm + 1 = n(n + 2) + 1 = n2 + 2n + 1 = (n + 1)2
• является составным числом.
• Или , например, определить m так: если n = 1, то m = 3, в противном случае m = n2.  

3. Найдите все целые числа n, для которых модуль значения трёхчлена n2 – 7n + 10 будет простым числом.

Решение

Так как

|n2 – 7n + 10| = |n –2| · |n – 5|,

то следует искать такие n при которых один из множителей последнего произведения равен 1, а второй является простым числом. Этому требованию удовлетворяют n = 3 и n = 4.

Ответ: n = 3, n = 4.

1. 4. Докажите, что если числа
2. а) m и m2 + 2 простые, то число m3 + 2 тоже простое;
3. б) р, р – 10, р + 10 простые, то число р – 2 тоже простое.

Решение

• а) Любое простое число m, отличное от 3, можно представить в виде 3n+1 или в виде 3n–1, где n – некоторое натуральное число. В первом случае можно записать
• m2 + 2 = 9n2 + 6n +3,
• во втором –
• m2 + 2 = 9n2 – 6n +3,

Так как m > 2, то в любом случае число m2+2 больше 3 и делится на 3, а значит является составным. Следовательно, число m2+2 может быть простым, только если m = 3. В этом случае m2+2 = 11 – простое число, m3+2 = 29 – тоже простое число, что и требовалось доказать.

б) Так как р – 10 = (р – 1) – 9 и р + 10 = (р + 1) + 9, то числа р – 10 и р – 1 при делении на 3 имеют одинаковые остатки, и числа р + 10 и р + 1 при делении на 3 имеют одинаковые остатки.

Из трёх последовательных чисел р – 1, р, р + 1 одно и только одно делится на 3. С учётом выше сказанного, то же утверждение верно для чисел р – 10, р, р + 10. Так как эти числа простые, то р – 10 = 3 и р = 13, поэтому р – 2 = 11 – простое число, что и требовалось доказать.

5. Сколько раз входит двойка в разложение на простые множители произведения

(n + 1) · (n + 2) · (n + 3) · . . . · (2n – 1) · 2n ?

Решение

Ответ на поставленный вопрос получим из следующих преобразований:

Ответ: n раз.

6. Найдите все простые p такие, что число p2 + 11 имеет ровно 6 различных делителей (включая единицу и само число).

Решение

Заметим, что p2 + 11 = p2 –1 + 12 = (p – 1)(p + 1) + 12 .

Если p > 5 и простое, то числа p – 1 и p + 1 оба четные, и одно из них кратно трем. Поэтому произведение (p – 1)(p + 1) делится на 12, следовательно, p2 + 11 также делится на 12, а значит, имеет не менее семи делителей (6 делителей числа 12 и само число p2 + 11 > 12 ). Осталось проверить p = 2 и p = 3.

1. Если p = 2, то p2 + 11 = 22 + 11 = 15 имеет 4 делителя (1, 3, 5, 15).
2. Если p = 3, то p2 + 11 = 32 + 11 = 20 имеет 6 делителей (1, 2, 4, 5, 10, 20).
3. Ответ: p = 3.

• 7. Найти все натуральные числа n, для которых каждое из шести чисел
• n + 1, n + 3, n + 7, n + 9, n + 13 и n + 15
• является простым.

Решение

Рассмотрим варианты. Для n = 1 число n + 3 = 4 составное.

1. Для n = 2 число n + 7 = 9 составное.
2. Для n = 3 число n + 1 = 4 составное.
3. Для n > 4 все наши числа больше 5 и по крайней мере одно из них делится на 5, так как числа 1, 3, 7, 9, 13 и 15 при делении на 5 дают соответственно остатки 1, 3, 2, 4, 3 и 0, то есть все возможные остатки, откуда следует, что и числа
4. n + 1, n + 3, n + 7, n + 9, n + 13 и n + 15
5. при делении на 5 дают все возможные остатки и, следовательно, хотя бы одно из них делится на 5 и как число, большее пяти (так как n > 4), является составным.
6. Но для n = 4 мы получаем простые числа 5, 7, 11, 13, 17 и 19.
7. Ответ: n = 4.

8. Доказать, что каждое простое число вида 4k + 1 является длиной гипотенузы прямоугольного треугольника, стороны которого выражаются натуральными числами.

Решение

Согласно известной теореме Ферма каждое простое число вида 4k + 1 есть сумма двух квадратов натуральных чисел.

Поэтому для такого р верно, что р = а2 + b2, где а и b – некоторые натуральные числа и притом различные (так как р – нечетное), например, а > b.

Отсюда р2 = (а2 – b2)2 + (2ab)2, то есть р является гипотенузой прямоугольного треугольника, катетами которого являются натуральные числа а2 – b2 и 2ab.

Так, например,

52 = 32 + 42, 132 = 52 + 122, 172 = 152 + 82, 292 = 212 + 202.

Замечание. Другие примеры подобных троек можно найти в таблице пифагоровых чисел с наибольшим числом не превосходящим 110 и в таблице примитивных пифагоровых чисел со средними числами, не превосходящими 256.

9. Сколькими способами можно раскрасить круг, разбитый на р равных секторов с помощью n красок, если р – простое число и каждый сектор раскрашиваем одной краской? Две раскраски, совпадающие при повороте круга, считаем одинаковыми.

Решение

Каждый сектор можно раскрасить в любой из n цветов, поэтому для круга с р секторами получим np раскрасок, среди которых (np – n) не одноцветных. Каждая из этих раскрасок поворотами переходит в (р – 1) одинаковую с ней, значит, существенно различных не одноцветных раскрасок будет (np – n)/p, откуда общее число раскрасок равно n + (np – n)/p.

10. Доказать, что для любого простого числа p > 5 уравнение х4 + 4x = p в целых числах не имеет решений.

Решение

• Докажем, что если для некоторого целого значения х число
• f(x) = х4 + 4x
• является целым, то это число либо не превосходит пяти, либо является составным.
• Действительно, если х < 0, то число f(x) не целое.
• Далее, при х = 0 и х = 1
• f(0) = 04 + 40 < 5, f(1) = 14 + 41 = 5.
• Если x = 2k (k – натуральное число), то число
• f(x) = 24k4 + 42k = 24( k4 + 42(k–1))
• является составным.
• Наконец, если x = 2k + 1 (k – натуральное число), то число
• f(x) = x4 + 4·42k = (x4 + 4×2(2k)2 + 4(2k)4) – 4×2(2k)2 =
• = (x2 + 2(2k)2)2 – (2·x·2k)2 =
• = (x2 + 2·x·2k + 2(2k)2)·( x2 – 2·x·2k + 2(2k)2) =
• = ((x + 2k)2 + 22k)·((x – 2k)2 + 22k)
• так же является составным, поскольку каждый из двух сомножителей последнего произведения больше 1 (ибо 22k > 1 при k > 0).
• Таким образом, если число p > 5 простое, то равенство х4 + 4x = p не выполняется ни при каких целых значениях х.

Задачи без решений

1. Известно, что р, р + 10, р + 14 – простые числа. Найдите число р.

1. 2. Докажите, что число
2. а) 210 + 512;
3. б) n4 + 64;
4. в) 4545 + 5454;
5. является составным.

3. Найдите все простые р для которых число р2 + 14 так же будет простым числом.

4. Докажите, что уравнение х2 + х + 1 = р·у имеет решение в целых числах (х, у) для бесконечного числа простых р.

5. Введём обозначение для суммы первых n простых чисел через Sn:

Sn = 2 + 3 + 5 + . . . + рn.

Докажите, что между числами Sn и Sn+1 всегда существует число, являющееся полным квадратом.

Источник: http://math4school.ru/prostie_i_sostavnye_chisla.html

Урок 4 Получить доступ за 50 баллов Простые и составные числа

На этом уроке мы познакомимся с двумя видами чисел. Они будут различаться количеством делителей.

Также узнаем, как можно разложить составное число на простые числа, изучим основную теорему арифметики и увидим решето Эратосфена.

Давайте же начнём!

• Если мы попытаемся разделить число 11 на какие-нибудь числа без остатка, то у нас получится это сделать, только если мы будем делить на 1 или на 11.
• Получается, что число 11 имеет только два делителя: 1 и 11.
• Если мы поступим так же с числами 9 и 18, то узнаем, что у числа 9 три делителя: 1, 3 и 9, а число 18 имеет шесть делителей: 1, 2, 3, 6, 9 и 18

Первое число, у которого всего два делителя, — это простое число. А вот такие числа, как 9 и 18, называют составными числами.

Натуральное число простое, если оно имеет делителями только единицу и само себя.

Если натуральное число имеет больше двух делителей, то оно называется составным.

Есть число, которое не относится ни к первым, ни ко вторым. Это число 1. Оно имеет всего один делитель — само это число.

Таким образом, числа, которые мы используем при счете, в итоге можно разделить на три разные группы по количеству делителей:

• простые имеют всегда пару делителей: единицу и само себя, например: 2, 3, 5, 7, 11, 17, 19, 23 и т.д.
• составные имеют всегда три или больше делителей, например: 4, 6, 8,10,15, 22 и т.д.
• единица (1) со своим единственным делителем

Пример 1

Даны числа: 1, 7, 10, 12, 13, 24. Найдите все делители для каждого из чисел. Выпишите числа, имеющие:

1. А) один делитель
2. Б) два делителя
3. В) больше двух делителей
4. Решение:
5. Число 1 имеет один делитель: 1
6. Число 7 имеет два делителя: 1, 7
7. Число 10 имеет четыре делителя: 1, 2, 5, 10
8. Число 12 имеет шесть делителей: 1, 2, 3, 4, 6, 12
9. Число 13 имеет два делителя: 1, 13
10. Число 24 имеет восемь делителей: 1, 2, 3, 4, 6, 8, 12, 24
11. Ответ: 
12. А) один делитель- 1
13. Б) два делителя- 7, 13
14. В) больше двух делителей- 10, 12, 24
15. Таким образом, числа 7 и 13 являются простыми, потому что имеют по два делителя.
16. Числа 10, 12, 24 являются составными, потому что имеют больше двух делителей.
17. Пример 2

Даны числа: 2, 4, 17, 21, 28, 30, 42, 55, 127. Какие из них простые, а какие составные?

• Найдите все делители для составных чисел.
• Решение:
• Простые: 2, 17, 127
• Составные: 4, 21, 28, 30, 42, 55
• Число 4 имеет три делителя: 1, 2, 4
• Число 21 имеет четыре делителя: 1, 3, 7, 21
• Число 28 имеет шесть делителей: 1, 2, 4, 7, 14, 28
• Число 30 имеет восемь делителей: 1, 2, 3, 5, 6, 10, 15, 30
• Число 42 имеет восемь делителей: 1, 2, 3, 6, 7, 14, 21, 42
• Число 55 имеет четыре делителя: 1, 5, 11, 55

1. Натуральное число можно представить в виде произведения простых чисел.
2. Такое разложение будет единственным и может отличаться только порядком множителей.
3. Это понятие носит название основной теоремы арифметики и используется очень часто.
4. Посмотрим на примерах, как всё тут работает.
5. Разложить 6 можно двумя способами, расположив по-разному простые множители: 3 умножить на 2 или 2 умножить на 3
6. (mathbf{6 = 3cdot2 = 2cdot3})
7. Если попытаемся разложить число 48 на простые множители, то  получим:
8. (mathbf{48 = 2cdot24 = 2cdot2cdot12 = 2cdot2cdot2cdot6= 2cdot2cdot2cdot2cdot3})
9. Чтобы всё сделать правильно при разложении, нужно выделить простой множитель, с оставшимся числом поступить так же и повторять действия, пока не получатся все простые множители.
10. Посмотрим еще один пример и возьмем 122.

Это число делится без остатка на два, так как оно чётное, получаем 61. Шестьдесят один — это простое число.

• Таким образом, разложение числа 122 на простые множители выглядит так:
• (mathbf{122 = 2cdot61})
• Возьмем еще большее число, к примеру, 462. При разложении на простые множители получим:
• (mathbf{462 = 2cdot3cdot7cdot11})

Бывают такие случаи, когда в числовом ряду простые числа стоят через одно составное. Рядом они стоять не могут, ведь каждое второе число будет чётным, значит, оно уже не будет являться простым.

Если простые числа стоят через одно составное, например, 3 и 5 или 71 и 73, или 461 и 463, то они называются «близнецами».

С развитием вычислительной техники было доказано, что простые числа с увеличением располагаются всё дальше друг от друга. Это создаёт проблему при поиске каждого нового простого числа.

1. Пример 1
2. Используя основную теорему арифметики, разложите на простые множители числа 72, 228, 896, 994, 105, 98
3. Решение:
4. $$mathbf{72 = 8cdot9=4cdot2cdot3cdot3=2cdot2cdot2cdot3cdot3}$$
5. $$mathbf{228= 12cdot19 = 4cdot3cdot19=2cdot2cdot3cdot19}$$
6. $$mathbf{896 = 64cdot14 = 4cdot16cdot2cdot7= 2cdot2cdot2cdot2cdot2cdot2cdot2cdot7}$$
7. $$mathbf{994 = 2cdot7cdot71}$$
8. $$mathbf{105= 3cdot5cdot7}$$
9. $$mathbf{98 = 2cdot14 =2cdot2cdot7}$$
10. Пример 2
11. Сколько делителей имеет каждое из чисел: 31, 25, 100, 189, 325, 558, 194?
12. Решение:
13. Число 31 имеет два делителя: 1, 31
14. Число 25 имеет три делителя: 1, 5, 25
15. Число 100 имеет девять делителей: 1, 2, 4, 5, 10, 20, 25, 50, 100
16. Число 189 имеет восемь делителей: 1, 3, 7, 9, 21, 27, 63, 189
17. Число 325 имеет шесть делителей: 1, 5, 13, 25, 65, 325
18. Число 558 имеет двенадцать делителей: 1, 2, 3, 6, 9, 18, 31, 62, 93, 186, 279, 558
19. Число 194 имеет четыре делителя: 1, 2, 97, 194
20. Пример 3
21. Какое из чисел 129, 565, 441, 70, 237, 816 имеет самое большое количество делителей?
22. Решение:
23. Число 129 имеет четыре делителя: 1, 3, 43, 129
24. Число 565 имеет четыре делителя: 1, 5, 113, 565
25. Число 441 имеет девять делителей: 1, 3, 7, 9, 21, 49, 63, 147, 441
26. Число 70 имеет восемь делителей: 1, 2, 5, 7, 10, 14, 35, 70
27. Число 237 имеет четыре делителя: 1, 3, 79, 237
28. Число 816 имеет двадцать делителей: 1, 2, 3, 4, 6, 8, 12, 16, 17, 24, 34, 48, 51, 68, 102, 136, 204, 272, 408, 816
29. Самое большое количество делителей имеет число 816

В глубокой древности началось изучение так называемых совершенных и дружественных чисел.

Некоторые из учёных пытались выражать на языке чисел всё, что наблюдали вокруг себя. Даже нематематические понятия дружбы, справедливости и совершенства переводились на язык чисел.

• Если число равно сумме всех возможных делителей без него самого, то оно называется совершенным.
• Например, самыми элементарными из них будут 6 и 28:
• 6 = 1 + 2 + 3,
• 28 = 1 + 2 + 4 + 7 + 14.
• Если сумма всех возможных делителей числа (кроме него самого) равна второму числу, а сумма всех возможных делителей второго (без него самого) равна первому, то это уже дружественные числа.
• Если верить историческим фактам, математик Пифагор считал, что его другом может быть «тот, кто является моим вторым Я, как числа 220 и 284»
• Список делителей для 220: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110, сумма делителей равна 284
• Список делителей для 284: 1, 2, 4, 71 и 142, сумма делителей равна 220.

Пару дружественных чисел 1184 и 1210 обнаружил в 1866г. итальянский школьник Никколо Паганини, полный тёзка великого скрипача.

Любопытно, что эту пару «проглядели» все великие математики.

• Видео
• Изображения
• Дополнительная информация
• Таблицы
• Тесты

Получить доступ

Источник: https://ladle.ru/education/matematika/6class/prostye-i-sostavnye

Простые и взаимно простые числа

Простое число – это положительное натуральное число, которое имеет только два положительных натуральных делителя: единицу и самого себя.

Противоположностью простых чисел являются составные числа. Составное число – это положительное натуральное число, которое имеет, по крайней мере, один положительный делитель, отличный от одного или самого себя.

Взаимно простые числа – числа A и B, не имеющие никаких общих делителей, за исключением единицы.

Примеры простых, составных и взаимно простых чисел

1. Число 2 является простым числом, т.к.

   имеет всего два делителя – 1 и 2:

2. Число 15 не является простым числом, потому имеет делители – 1, 3, 5, 15:
   • 15/1 = 15
   • 15/3 = 5
   • 15/5 = 3
   • 15/15 = 1
3. Число 13 является простым числом, т.к.

   имеет только два делителя – 1 и 13:

4. Числа 2 и 5 являются взаимно простыми, т.к. имеют только один общий делитель – число 1:
   1. 2/1 = 2
   2. 2/2 = 1
   3. 5/1 = 5
   4. 5/5 = 1

Таблица простых чисел

Ниже представлена таблица простых чисел от 2 до 997, которую можно распечатать, чтобы всегда иметь под рукой в случае необходимости.

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	109	113	127	131	137	139	149	151
157	163	167	173	179	181	191	193	197	199	211	223
227	229	233	239	241	251	257	263	269	271	277	281
283	293	307	311	313	317	331	337	347	349	353	359
367	373	379	383	389	397	401	409	419	421	431	433
439	443	449	457	461	463	467	479	487	491	499	503
509	521	523	541	547	557	563	569	571	577	587	593
599	601	607	613	617	619	631	641	643	647	653	659
661	673	677	683	691	701	709	719	727	733	739	743
751	757	761	769	773	787	797	809	811	821	823	827
829	839	853	857	859	863	877	881	883	887	907	911
919	929	937	941	947	953	967	971	977	983	991	997

microexcel.ru

Вопросы – ответы:

1. Является ли число 1 простым?
   Число 1 не является простым по определению – оно имеет только один делитель.
2. Является ли число 0 простым?
   Число 0 не является простым – оно не является положительным числом и имеет бесконечное количество делителей.

(1

Источник: https://MicroExcel.ru/prostye-chisla/

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

• Как узнать, число простое или составное?

Натуральные числа, большие единицы, в зависимости от количества их делителей, подразделяются на простые и составные числа.

Простое число – это натуральное число, которое больше единицы и делится только на единицу и само на себя.

• Пример.
• 2, 5, 7, 11  – простые числа.
• 2  – делится на 1 и на 2.
• 5  – делится на 1 и на 5.
• 7  – делится на 1 и на 7.
• 11  – делится на 1 и на 11.

Составное число – это натуральное число, которое больше единицы, делится не только на единицу и само на себя, но и ещё хотя бы на одно натуральное число.

1. Пример.
2. 4, 6, 9, 10  – составные числа.
3. 4  – делится на 1, на 2 и на 4.
4. 6  – делится на 1, на 2, на 3 и на 6.
5. 9  – делится на 1, на 3 и на 9.
6. 10  – делится на 1, на 2, на 5 и на 10.

Наименьшее простое число – число 2 (оно же первое простое число). Это единственное чётное простое число. Все остальные простые числа нечётные.

Наименьшее составное число – число 4 (оно же первое составное число).

Простых и составных чисел бесконечно много, есть первое простое и составное число, но нет последнего простого и составного числа.

Единица имеет только один делитель – само число 1. Этим единица отличается от всех остальных натуральных чисел, поэтому условились считать, что единица не является ни простым, ни составным числом.

Не существует простых чисел, оканчивающихся на 4, 6, 8 или 0.

Среди простых чисел есть только одно число, оканчивающееся на 2 – само число 2, из оканчивающихся на 5 – тоже есть только одно число – само число 5.

Все остальные простые числа, кроме 2 и 5, оканчиваются на 1, 3, 7 или 9. Не все числа, оканчивающиеся на 1, 3, 7, 9, являются простыми, например числа 21, 27, 33, 39 и многие другие – составные.

Как узнать, число простое или составное?

Самый простой способ определить является число простым или составным – посмотреть таблицу простых чисел.

Если под рукой нет таблицы с выписанными простыми числами, то можно попробовать определить с помощью последовательного перебора всех возможных делителей данного числа. Если ни одно число не подойдёт в качестве делителя данного числа, то это число будет простым, в противном случае – составным.

Если данное число превосходит наибольшее число из имеющейся таблицы, то можно попробовать определить с помощью последовательного деления данного числа на простые числа, начиная с числа 2. Если ни одно простое число не подойдёт в качестве делителя данного числа, то это число – простое, в противном случае – составное.

Новое на сайте	|	contact@izamorfix.ru
2018 − 2020	©	izamorfix.ru

Источник: https://izamorfix.ru/matematika/arifmetika/prostye_i_sostavnye_chisla.html

Простые числа: история и факты

Свойства простых чисел впервые начали изучать математики Древней Греции. Математики пифагорейской школы (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 «Начал» Эвклид доказал, что простых чисел бесконечное количество.

Это, кстати, один из первых примеров использования доказательства от противного. Также он доказывает Основную теорему арифметики – каждое целое число можно представить единственным образом в виде произведения простых чисел.

Также он показал, что если число 2n-1 является простым, то число 2n-1 * (2n-1) будет совершенным.

В году 200 году до н.э. грек Эратосфен придумал алгоритм для поиска простых чисел под названием «Решето Эратосфена». А затем случился большой перерыв в истории исследования простых чисел, связанный со Средними веками. Следующие открытия были сделаны уже в начале 17-го века математиком Ферма. Он доказал гипотезу Альбера Жирара, что любое простое число вида 4n+1 можно записать уникальным образом в виде суммы двух квадратов, и также сформулировал теорему о том, что любое число можно представить в виде суммы четырёх квадратов.

Он разработал новый метод факторизации больших чисел, и продемонстрировал его на числе 2027651281 = 44021 × 46061. Также он доказал Малую теорему Ферма: если p – простое число, то для любого целого a будет верно ap = a modulo p.

Это утверждение доказывает половину того, что было известно как «китайская гипотеза», и датируется 2000 годами ранее: целое n является простым тогда и только тогда, если 2n-2 делится на n. Вторая часть гипотезы оказалась ложной – к примеру, 2341 — 2 делится на 341, хотя число 341 составное: 341 = 31 × 11.

Малая теорема Ферма послужила основой множества других результатов в теории чисел и методов проверки чисел на принадлежность к простым – многие из которых используются и по сей день.

Ферма много переписывался со своими современниками, в особенности с монахом по имени Марен Мерсенн. В одном из писем он высказал гипотезу о том, что числа вида 2n+1 всегда будут простыми, если n является степенью двойки.

Он проверил это для n = 1, 2, 4, 8 и 16, и был уверен, что в случае, когда n не является степенью двойки, число не обязательно получалось простым.

Эти числа называются числами Ферма, и лишь через 100 лет Эйлер показал, что следующее число, 232 + 1 = 4294967297 делится на 641, и следовательно, не является простым.

Числа вида 2n — 1 также служили предметом исследований, поскольку легко показать, что если n – составное, то и само число тоже составное. Эти числа называют числами Мерсенна, поскольку он активно их изучал.

Но не все числа вида 2n — 1, где n – простое, являются простыми. К примеру, 211 — 1 = 2047 = 23 * 89. Впервые это обнаружили в 1536 году.

Что число M19, было доказано Катальди в 1588 году, и в течение 200 лет было наибольшим известным простым числом, пока Эйлер не доказал, что M31 также простое.

Этот рекорд продержался ещё сто лет, а затем Люкас показал, что M127 — простое (а это уже число из 39 цифр), и после него исследования продолжились уже с появлением компьютеров.

В 1952 была доказана простота чисел M521, M607, M1279, M2203 и M2281.

К 2005 году найдено 42 простых чисел Мерсенна. Наибольшее из них, M25964951, состоит из 7816230 цифр.

Работа Эйлера оказала огромное влияние на теорию чисел, в том числе и простых. Он расширил Малую теорему Ферма и ввёл φ-функцию. Факторизовал 5-е число Ферма 232+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, можно представить в виде суммы двух простых чисел
• бесконечно ли количество простых чисел вида n2 + 1 ?
• всегда ли можно найти простое число между n2 and (n + 1) 2? (факт, что между n и 2n всегда есть простое число, было доказан Чебышёвым)
• бесконечно ли число простых чисел Ферма? есть ли вообще простые числа Ферма после 4-го?
• существует ли арифметическая прогрессия из последовательных простых чисел для любой заданной длины? например, для длины 4: 251, 257, 263, 269. Максимальная из найденных длина равна 26.
• бесконечно ли число наборов из трёх последовательных простых чисел в арифметической прогрессии?
• n2 — n + 41 – простое число для 0 ≤ n ≤ 40. Бесконечно ли количество таких простых чисел? Тот же вопрос для формулы n2 — 79 n + 1601. Эти числа простые для 0 ≤ n ≤ 79.
• бесконечно ли количество простых чисел вида n# + 1? (n# — результат перемножения всех простых чисел, меньших n)
• бесконечно ли количество простых чисел вида n# -1 ?
• бесконечно ли количество простых чисел вида n! + 1?
• бесконечно ли количество простых чисел вида n! – 1?
• если p – простое, всегда ли 2p-1 не содержит среди множителей квадратов простых чисел
• содержит ли последовательность Фибоначчи бесконечное количество простых чисел?

Текущие рекорды среди простых чисел

Самое большое простое число, вычисленное проектом GIMPS [Great Internet Mersenne Prime Search], можно посмотреть в таблице на официальной странице проекта. www.mersenne.org/primes

Самые большие близнецы среди простых чисел – это 2003663613 × 2195000 ± 1. Они состоят из 58711 цифр, и были найдены в 2007 году.

Самое большое факториальное простое число (вида n! ± 1) – это 147855! — 1. Оно состоит из 142891 цифр и было найдено в 2002.

Наибольшее праймориальное простое число (число вида n# ± 1) – это 1098133# + 1.

Источник: https://habr.com/post/276037/