Разложение на простые множители (GMAT / GRE Quant)

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

Разложение на простые множители — одна из самых важных тем во всем разделе Integer Properties. Без уверенного владения этой темой невозможно эффективно решать задачи GMAT и GRE, связанные с делимостью, факторами и кратными.

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

Ниже приведены первые 17 простых чисел — все простые числа от 2 и до чисел меньше 60.
Первые восемь из них являются обязательными для мгновенного узнавания. Остальные также крайне желательно знать без раздумий.

В предыдущей главе мы говорили, что простые числа — это «строительные блоки» всех положительных целых чисел. Теперь разберем, что именно это означает.

Фундаментальная теорема арифметики (идея)

Существует важная математическая идея, известная как фундаментальная теорема арифметики.
Название и история происхождения знать не нужно, но саму идею — обязательно.

Формулировка:

Каждое положительное целое число больше 1:

• либо является простым числом,
  
  
• либо может быть единственным образом представлено в виде произведения простых чисел.
  
  

Это произведение простых чисел называется разложением на простые множители (prime factorization).

Примеры разложения на простые множители

Рассмотрим несколько простых примеров:

• 9 = 3 × 3
  
  
• 10 = 2 × 5
  
  
• 15 = 3 × 5
  
  

Число 12:

• 12 = 4 × 3
  
  
• 4 не является простым числом, поэтому
  
  
• 4 = 2 × 2
  
  

Итог:

• 12 = 2 × 2 × 3
  
  

Число 24:

• 24 = 8 × 3
  
  
• 8 = 2 × 2 × 2
  
  

Итог:

• 24 = 2 × 2 × 2 × 3
  
  
• или в компактной форме: 2 в третьей степени × 3
  
  

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

Еще примеры

• 100 = 10 × 10
  
  
• 10 = 2 × 5
  
  

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

• 100 = 2 в квадрате × 5 в квадрате
  
  

В дальнейшем мы будем часто использовать такую форму записи.

Как найти разложение на простые множители

Рассмотрим пример более подробно.

Пример: разложить число 96

Разложим пошагово:

1. 96 делится на 2
   96 = 2 × 48
   
   
2. 48 = 6 × 8
   
   
3. 6 = 2 × 3
   
   
4. 8 = 2 × 2 × 2
   
   

Объединяем все множители:

• 96 = 2 × 2 × 2 × 2 × 2 × 3
  
  
• 96 = 2 в пятой степени × 3
  
  

Это и есть разложение 96 на простые множители.

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

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

Для числа 96:

• степени двойки: 2, 4, 8, 16
  
  
• умножая их на 3: 6, 12, 24, 48
  
  

Все эти числа являются делителями 96.

Почему 96 не делится на 15?

• 15 = 3 × 5
  
  
• в разложении 96 нет множителя 5
  
  

Почему 96 не делится на 18?

• 18 = 2 × 3 × 3
  
  
• требуется два множителя 3,
  
  
• в разложении 96 есть только один множитель 3
  
  

Следовательно, деление невозможно.

Ключевая идея

Разложение на простые множители — это как ДНК числа.
Оно показывает все «составляющие» числа.

Важное следствие:

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

Связь с факторами и кратными

Ранее мы установили эквивалентность следующих утверждений:

• r — фактор Q
  
  
• r — делитель Q
  
  
• Q делится на r
  
  
• Q — кратное r
  
  

Теперь можно добавить пятое эквивалентное утверждение:

• все простые множители r входят в разложение Q на простые множители
  
  

Экзаменационный пример (GMAT-style)

Пусть разложение числа 4680 на простые множители задано.

Определим, какие из следующих чисел являются его делителями.

25

• 25 = 5 × 5
  
  
• требуется два множителя 5
  
  
• в разложении есть только один 5
  
  

Не является делителем

45

• 45 = 5 × 3 × 3
  
  
• в разложении есть 5 и два множителя 3
  
  

Является делителем

65

• 65 = 5 × 13
  
  
• оба множителя присутствуют
  
  

Является делителем

85

• 85 = 5 × 17
  
  
• множителя 17 нет
  
  

Не является делителем

120

• 120 = 3 × 5 × 8
  
  
• 8 = 2 × 2 × 2
  
  
• все необходимые множители присутствуют
  
  

Является делителем

180

• 180 = 2 × 2 × 3 × 3 × 5
  
  
• все множители присутствуют в нужных степенях
  
  

Является делителем

Почему это важно

Разложение на простые множители позволяет:

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

Это самый важный навык во всем разделе Integer Properties.

Итоги

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

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

Далее рассмотрим подсчет количества делителей больших чисел.