MindCube Академия - Простые и составные числа

Определение

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

Определение

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

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

Решето Эратосфена

Чтобы определить все простые числа, не превышающие заданное число $n$ , можно использовать следующий метод. Сначала выписываем по порядку все целые числа от $2$ до $n$ . Затем обводим число $2$ как первое простое, и вычёркиваем все кратные ему числа (то есть $4, 6, 8, \ldots$ ). После этого берём следующее невычеркнутое число, также считаем его простым и вычёркиваем все числа, делящиеся на него. Повторяем этот шаг до конца списка. В итоге все оставшиеся невычеркнутыми числа являются простыми.

Алгоритм проверки числа на простоту

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

Доказательство

Предположим, что число $n$ — составное, тогда оно представимо в виде $n=ab$ , где $a>1$ , $b>1$ . Предположим, что $a\leqslant b$ , то $n=ab\geqslant a^2$ , т.е. $a\leqslant \sqrt{n}$ . Следовательно, для любого простого делителя $p$ числа $a$ выполняется $p\leqslant a\leqslant \sqrt{n}$ . Значит, если число составное, то у него есть простой делитель не прeвосходящий $\sqrt{n}$ .

Пример

Найти все натуральные $p$ такие, что $p$ , $p + 2$ , $p + 4$ , — простые.

Решение

Заметим, что $p = 3$ подходит. Пусть есть другое решение. Тогда ни одно из чисел $p$ , $p + 2$ , $p + 4$ не делится на 3. Но если $p + 4$ не делится на 3, то и $p + 1$ не делится на 3. Откуда получаем, что $p$ , $p + 1$ и $p + 2$ не делятся на 3, чего быть не может, так как это три подряд идущих числа, а среди трех подряд идущих чисел всегда есть число делящееся на 3.

Ответ. 3

Теорема

Простых чисел бесконечно много.

Доказательство

Предположим, что простых чисел конечное число:

$2,\, 3,\, 5,\, 7,\, 11,\, \ldots,\, p,$

где $p$ — самое большое простое число.

Составим число $n$ :

$n=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot \ldots \cdot p + 1.$

Данное число не делится на $2$ , так как превышает его кратное всего на единицу. Точно так же оно не делится ни на $3$ , ни на $5$ , … ни на $p$ . Следовательно, число $n$ не делится ни на одно из известных простых чисел, что противоречит фундаментальной теореме арифметики: любое натуральное число больше $1$ можно разложить на произведение простых множителей. Это противоречие доказывает, что начальное предположение было неверным — следовательно, простых чисел существует бесконечно много.

Заметим, что у чисел может быть разное количество делителей. Например, у числа $1$ только один делитель — единица. А вот у числа $2$ два делителя: единица и двойка.

Подумайте, сколько делителей у чисел $3$ , $4$ , $5$ , $6$ ?

Узнать ответ

Делители числа $3$ : $1$ и $3$ .

Делители числа $4$ : $1$ , $2$ и $4$ .

Делители числа $5$ : $1$ и $5$ .

Делители числа $6$ : $1$ , $2$ , $3$ и $6$ .

Определение

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

Примеры простых чисел: $2, 3, 5, 7, 11, 13, 17$ и так далее.

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

Число $2$ является наименьшим и единственным чётным простым числом.

$\blacktriangleright$ Пример 1. Найдите наибольшее двузначное простое число.

Решение

Возьмём наибольшее двузначное число: $99$ . Видим, что оно делится, например, на $3$ , на $9$ , на $11$ . То есть у числа больше двух делителей, значит, оно не простое.

Перед ним в натуральном ряду стоит число $98$ , которое также не является простым — оно чётное. Значит, берём число ещё раньше: $97$ .

Для числа $97$ не подобрать других делителей кроме единицы и его самого. Значит, оно простое.

Ответ: $97$ .

Безусловно, определить, простое ли число, бывает непросто, ведь для этого нужно проверить делимость на множество других чисел. Чтобы быстро и точно узнать, является ли число простым, удобно воспользоваться таблицей простых чисел.

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

$\blacktriangleright$ Пример 2. Докажите, что число $21$ не является простым.

Решение

Видим, что делители числа $21$ следующие: $1$ , $3$ , $7$ , $21$ . Их больше двух, следовательно, число не простое.

Определение

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

Примеры составных чисел: $4, 6, 8, 9, 10, 12, 14, 15, 16$ и так далее.

$\blacktriangleright$ Пример 3. Выберите из ряда составные числа:

$16, 19, 21, 28, 33, 47, 55, 117, 140, 149, 198$ .

Решение

Используя признаки делимости, несложно определить числа, делящиеся на $2$ , $3$ , $5$ , $7$ и другие. Такие числа имеют более двух делителей, а значит — являются составными.

Ответ: $16, 21, 28, 33, 55, 117, 140, 198$ .

Любое составное число можно представить в виде произведения простых чисел. Например, $210=2\cdot 3\cdot 5\cdot 7$ .

Число $1$ имеет только один делитель, и поэтому не относится ни к простым, ни к составным числам.