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

Эта тема является частью раздела целочисленных свойств в Quant GMAT Focus.

В определённом смысле простые числа — самые важные положительные целые числа. Именно они являются «строительными блоками» всех остальных чисел. Прежде чем говорить о том, насколько мощна эта идея, необходимо чётко понять, что такое простое число.

Напоминание: факторы целых чисел

Ранее мы установили два фундаментальных факта:

1. Число 1 является фактором любого положительного целого числа.

    

2. Любое положительное целое число является фактором самого себя.

    

Например:

• 3 — фактор 3

   

• 7 — фактор 7

   

Следовательно, каждое положительное целое число имеет как минимум два фактора:
1 и само себя.

Многие числа имеют и другие факторы. В предыдущих главах мы даже рассматривали способы подсчёта количества факторов у больших чисел.

Определение простого числа

Простое число — это положительное целое число, которое имеет ровно два фактора:

• 1

   

• само это число

   

И никаких других факторов.

Иначе говоря, простое число:

• не делится ни на какое положительное целое число меньше себя, кроме 1

   

Это и есть базовое определение простого числа, которое используется в GMAT и GRE.

Простые числа меньше 20

Простые числа меньше 20:

2, 3, 5, 7, 11, 13, 17, 19

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

Простые числа от 20 до 60

Также крайне полезно уверенно знать простые числа в диапазоне от 20 до 60.

На экзамене нежелательно тратить время на размышления вида:

• «51 — простое число или нет?»

   

• «53 — простое число или нет?»

   

Гораздо эффективнее просто знать эти числа заранее.

Числа больше 60 проверяются на простоту реже. Если вы любите заучивание, можно запомнить простые числа вплоть до 100, но это не является обязательным требованием для GMAT / GRE.

Ключевые факты о простых числах

Факт 1: число 1 не является простым

Простые числа имеют два фактора, а у числа 1 есть только один фактор — оно само.

Некоторых это удивляет, но:

• это не случайность

   

• это не «искусственное исключение»

   

Существуют глубокие математические причины, по которым 1 не считается простым числом.

Для экзамена важно только одно:
1 — не простое число.

Факт 2: число 2 — единственное чётное простое число

• Все чётные числа, кроме 2, делятся на 2

   

• Следовательно, все чётные числа, кроме 2, не являются простыми

   

Отсюда сразу два вывода:

• 2 — наименьшее простое число

   

• 2 — единственное чётное простое число

   

Эти два факта чрезвычайно важны.
Более чем в половине задач GMAT, связанных с простыми числами, один из этих фактов скрыт в условии.

Как проверять, является ли число простым (меньше 100)

Чтобы проверить, является ли число меньше 100 простым, достаточно проверить, делится ли оно на простые числа меньше 10.

А именно:

• 2

   

• 3

   

• 5

   

• 7

   

Если число:

• не делится ни на одно из них

   

то оно обязательно простое.

Других проверок не требуется.

Практический пример (GMAT-style)

Вопрос:
Сколько простых чисел находится между 80 и 90?

Шаг 1. Исключаем чётные числа

Все чётные числа делятся на 2, значит не могут быть простыми.

Остаются только нечётные:
81, 83, 85, 87, 89

Шаг 2. Проверяем делимость на 5

• 85 оканчивается на 5 → делится на 5 → не простое

   

Шаг 3. Проверяем делимость на 3

• 81 = 9 × 9 → делится на 3 → не простое

   

• 87: 8 + 7 = 15 → делится на 3 → не простое

   

(Альтернативное рассуждение: 90 — кратное 3, значит 87 = 90 − 3 тоже кратно 3.)

Шаг 4. Проверяем делимость на 7

Остаются числа:
83 и 89

Рассмотрим кратные 7:

• 77

   

• 84

   

• 91

   

В диапазоне 80–90 кратное 7 — только 84, и это чётное число.

Следовательно:

• 83 не делится на 7

   

• 89 не делится на 7

   

Они также не делятся на 2, 3 или 5.

Ответ:

В этом диапазоне два простых числа: 83 и 89.

Итог

В этой главе мы разобрали:

• строгую дефиницию простого числа

   

• почему каждое число имеет минимум два фактора

   

• список простых чисел меньше 20 и важность их запоминания

   

• два критически важных факта:

   

  • 1 не является простым числом

     

  • 2 — единственное чётное простое число

     

• эффективный метод проверки простоты чисел меньше 100

   

• типичную экзаменационную задачу с пошаговым логическим разбором

   

Простые числа — фундаментальная тема Quant-раздела. Далее они будут активно использоваться при разложении чисел на множители и анализе делимости.