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

  • 4 мин чтения
  • Послушать — 3 мин
  • 9 карточек

Математика, 7 класс · Л. Г. Петерсон, Д. Л. Абраров, Е. В. Чуткова · § 1. Делимость на множестве натуральных чисел

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

Можно сократить проверку ещё сильнее. Если a — составное, то a = bc, где b, c > 1, и квадраты b и c не могут одновременно быть больше a (иначе bc > a). Значит, у составного числа всегда есть делитель, отличный от 1, квадрат которого не больше самого числа.

Алгоритм ответа на вопрос «Является ли число a простым?»

  1. Выписать все простые числа, квадраты которых не больше a.
  2. Если a делится хотя бы на одно из выписанных чисел, то a — составное.
  3. Если a не делится ни на одно из выписанных чисел, то a — простое.

Пример. 113: простые числа с квадратом не больше 113 — это 2, 3, 5, 7 (11² = 121 > 113). На них 113 не делится, значит, 113 — простое.

Простых чисел бесконечно много. Предположим, что их конечное число: 2, 3, 5, …, p. Число a = 2 · 3 · 5 · … · p + 1 больше каждого из них, значит, составное. Но при делении на любое из наших простых чисел оно даёт остаток 1 — противоречие.

Правило

1 / 9

Только простые делители

Если число не делится на простое число, то не делится и ни на одно его кратное.

Не делится на 2 — не делится и на 4, 6, 8, …

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

Свойство

2 / 9

Делитель с малым квадратом

Если a — составное, то a = bc, где b, c > 1.

Квадраты b и c не могут оба быть больше a: иначе bc > a.

Значит, у составного a есть делитель, отличный от 1, с квадратом не больше a: 91 = 7 · 13, 7² = 49.

Проверь себя

3 / 9

Нужна ли проверка?

Проверяем делимость только на простые числа.

Число a не делится на 2. Может ли оно делиться на 4?

данетиногда
Ответ и объяснение

4 vdots 2, поэтому любое число, кратное 4, делится на 2. Наше не делится — значит, и на 4 нет.

Правило

4 / 9

Алгоритм

Является ли число a простым?

  1. Выписать все простые числа, квадраты которых не больше a.
  2. Если a делится хотя бы на одно из них, то a — составное.
  3. Если a не делится ни на одно из них, то a — простое.

Разбор

5 / 9

Простое ли 113?

Узнай, является ли простым число 113.

  1. Список

    2² = 4, 3² = 9, 5² = 25, 7² = 49, а 11² = 121 > 113: проверяем 2, 3, 5, 7.

  2. Проверка

    113 нечётное; сумма цифр 5 — не делится на 3; не оканчивается на 0 или 5; 113 = 7 · 16 + 1.

  3. Ответ

    113 ни на одно не делится — оно простое.

Проверь себя

6 / 9

Проверять ли 11?

Проверяем простые p с p² ≤ a.

97 не делится на 2, 3, 5, 7. Нужно ли проверять 11?

данет
Ответ и объяснение

11² = 121 > 97, проверка окончена: 97 — простое.

Частая ошибка

7 / 9

Не больше, а не меньше

Ошибка: для 49 взять простые с квадратом меньше 49: 2, 3, 5. На них 49 не делится — «простое»?

Нет! 7² = 49 тоже не больше 49, и 49 = 7 · 7 — составное.

Разбор

8 / 9

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

Докажи, что простых чисел бесконечно много.

  1. Предположение

    Предположим противное: все простые числа — это 2, 3, 5, …, p.

  2. Число

    a = 2 · 3 · 5 · … · p + 1 больше каждого из них, значит, составное.

  3. Противоречие

    Но при делении на любое из наших простых a даёт остаток 1 — противоречие.

  4. Ответ

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

Главное

9 / 9

Главное

  • Делимость проверяем только на простые числа.
  • Достаточно простых p с p² ≤ a.
  • Делится хоть на одно — составное, ни на одно — простое.
  • 11² = 121 > 113: 113 — простое; 49 = 7² — составное.
  • Простых чисел бесконечно много.

Проверь себя: тест по теме

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

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест