2.1.2. Простые числа

Определения и обозначения

Делитель натурального числа — натуральное число, на которое данное число делится без остатка. Если b — делитель числа a, то a = b·k, где k — натуральное число. Например, 3 — делитель 12, потому что 12 = 3·4. Это понятие нужно, чтобы описывать, на какие числа можно разделить данное число поровну.

Простое число — натуральное число больше 1, у которого ровно два натуральных делителя: 1 и само число. Например, у числа 7 делители только 1 и 7. Определение помогает отличить числа, которые нельзя разделить на меньшие натуральные множители, кроме единицы, от остальных чисел.

Составное число — натуральное число больше 1, у которого больше двух натуральных делителей. Например, у числа 12 есть делители 1, 2, 3, 4, 6 и 12. Если число делится на что-то, кроме 1 и себя, оно составное; это удобно использовать при проверке чисел и разложении их на множители.

Число 1 — особый случай: у него только один натуральный делитель, само число 1. Поэтому оно не подходит ни под определение простого числа, где требуется два делителя, ни под определение составного, где их должно быть больше двух. Это уточнение нужно, чтобы не относить единицу к одному из этих двух видов.

Как это устроено

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

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

Если у числа n найден делитель d, отличный от 1 и n, то вместе с ним у числа есть и другой делитель: частное n ÷ d. Например, если 12 делится на 3, то оно также делится на 4. Значит, у 12 уже больше двух делителей и оно составное; так работает связь между делением без остатка и определением составного числа.

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

Признаки делимости помогают быстро отсеять некоторые возможные простые числа. Чётное число делится на 2, число, сумма цифр которого делится на 3, делится на 3, а число, оканчивающееся на 0 или 5, делится на 5. Если число больше соответствующего делителя, то найденный делитель показывает, что оно составное; если эти признаки не подошли, всё равно могут подойти другие делители.

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

Сначала проверь, больше ли число 1, а затем посмотри на его делители. Если нашёлся дополнительный делитель, число составное; если его нет и число больше 1, оно простое. Для числа 1 подходит отдельная строка таблицы.

Разбор задач

Задача 1. Определить, является ли число 13 простым или составным.

Нужно выяснить, есть ли у 13 делители, кроме 1 и 13. Проверять делимость на числа больше половины от 13 не требуется: если 13 = a·b и оба множителя больше 1, меньший из них не превосходит √13. Поэтому проверим делители 2 и 3.

1. 13 не делится на 2, потому что оно нечётное. Значит, делитель 2 не найден.
2. 13 не делится на 3: сумма цифр равна 4, а 4 не делится на 3. Других возможных делителей до √13 нет.

Ответ: 13 — простое число, его натуральные делители — 1 и 13.

Задача 2. Разделить числа 2, 9, 17, 25 и 1 на простые, составные и числа, не относящиеся ни к одному из этих видов.

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

1. У числа 2 есть только делители 1 и 2, поэтому оно простое. Число 9 делится на 3, а 25 — на 5, следовательно, оба числа составные.
2. Для 17 достаточно проверить делители до √17: это 2 и 3. На 2 число не делится, а сумма его цифр равна 8, поэтому оно не делится на 3; значит, 17 простое.
3. Число 1 имеет ровно один делитель. Оно не является ни простым, ни составным.

Ответ: простые — 2 и 17; составные — 9 и 25; ни к одному виду не относится 1.

Задача 3. Определить, является ли 53 простым числом, проверив возможные делители.

Если число составное, его можно представить произведением двух множителей больше 1. Хотя бы один множитель такого произведения не превосходит квадратного корня из числа, а √53 меньше 8. Поэтому достаточно проверить простые числа 2, 3, 5 и 7: составной делитель обязательно содержал бы один из этих простых множителей.

1. 53 не делится на 2, потому что оно нечётное, и не делится на 3, потому что сумма цифр равна 8. На 5 число тоже не делится: оно не оканчивается на 0 или 5.
2. Проверяем 7: 7·7 = 49, а 7·8 = 56, поэтому 53 не делится на 7 без остатка. Все простые делители, не превосходящие √53, проверены.

Ответ: 53 — простое число.

Типичные ошибки

Считать 1 простым числом — ошибка, потому что у неё один делитель, а по определению у простого их ровно два. Так путаются, если запомнить только то, что простые числа делятся на себя. Проверь себя: у числа 1 делители не образуют пару «1 и само число» из двух разных чисел.

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

Можно забыть, что составному числу необходим дополнительный делитель. Это происходит, когда рассуждают о возможности деления, не сверяясь с определением. Запиши известные делители и проверь, есть ли среди них число, отличное от 1 и самого числа; например, у 12 таким делителем будет 2.

Проверить только делимость на 2, 3 и 5 и сразу объявить число простым — недостаточно. Эти признаки помогают отсеять числа, делящиеся на 2, 3 или 5, но не исключают делимость на другие числа. Проверь возможные простые делители до квадратного корня из числа: например, для 53 нужно также проверить 7.

Связь с другими темами

Для работы с простыми числами нужно знать натуральные числа, деление с остатком и понятие делителя: без этого нельзя проверить, делится ли число на другое без остатка. Простые числа понадобятся при разложении составного числа на простые множители. Умение находить делители также помогает искать общие делители двух чисел, наибольший общий делитель (НОД) и наименьшее общее кратное (НОК).

Что запомнить

• Простое число больше 1 и имеет ровно два натуральных делителя.
• Составное число больше 1 и имеет больше двух натуральных делителей.
• Число 1 не является ни простым, ни составным.
• Если у числа больше 1 найден делитель, отличный от 1 и самого числа, оно составное.
• У простого числа единственные натуральные делители — 1 и само число.
• Число 2 — единственное чётное простое число.