Наибольший общий делитель

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

Наибольший общий делитель также называют наибольшим общим множителем. Оба термина означают одно и то же. В этом разделе будем использовать стандартное сокращение GCF (greatest common factor).

Навык нахождения GCF важен во многих типах задач Quant. Сначала разберем, что это такое и как его находить, а затем — где и зачем он применяется.

Что такое наибольший общий делитель

Рассмотрим простой пример.

Каков GCF чисел 24 и 40?

Можно рассуждать так:

• выписать все делители 24
  
  
• выписать все делители 40
  
  
• найти те, которые встречаются в обоих списках
  
  

Общие делители 24 и 40:
1, 2, 4, 8

Наибольший из них — 8, значит:

• GCF(24, 40) = 8
  
  

Формальное определение

Наибольший общий делитель двух чисел — это наибольший положительный целый делитель, который делит оба числа без остатка.

Почему простой перебор не работает

Для небольших чисел метод выписывания делителей допустим.
Но если числа большие (сотни и тысячи), такой подход:

• слишком медленный
  
  
• непрактичен для экзамена
  
  

Поэтому на GMAT и GRE почти всегда используется метод через разложение на простые множители.

Метод нахождения GCF через простые множители

Пример: GCF чисел 360 и 800

Шаг 1. Найти разложения на простые множители

• 360 = 36 × 10 = 6 × 6 × 10
  → 360 = 2 в третьей степени × 3 в квадрате × 5
  
  
• 800 = 8 × 100 = 8 × 10 × 10
  → 800 = 2 в пятой степени × 5 в квадрате
  
  

Шаг 2. Найти наибольшие общие степени каждого простого множителя

• Для 2:
  степени — 3 и 5 → общая степень = 3
  
  
• Для 3:
  одно число содержит 3 в квадрате, другое — не содержит 3
  → общая степень = 0
  
  
• Для 5:
  степени — 1 и 2 → общая степень = 1
  
  

Шаг 3. Собрать GCF

GCF = 2 в третьей степени × 5
= 8 × 5
= 40

Ответ: GCF(360, 800) = 40

Еще один пример (GMAT-style)

Найти GCF чисел 720 и 1200

Шаг 1. Разложения на простые множители

• 720 = 2 в четвертой степени × 3 в квадрате × 5
  
  
• 1200 = 2 в четвертой степени × 3 × 5 в квадрате
  
  

Шаг 2. Общие степени простых множителей

• Для 2: min(4, 4) = 4
  
  
• Для 3: min(2, 1) = 1
  
  
• Для 5: min(1, 2) = 1
  
  

Шаг 3. Собираем GCF

GCF = 2 в четвертой степени × 3 × 5

Для удобства вычислений:

• 2 × 5 = 10
  
  
• остается 2 в третьей степени × 3 × 10
  
  

Вычисляем:

• 2 в третьей степени = 8
  
  
• 8 × 3 = 24
  
  
• 24 × 10 = 240
  
  

Ответ: GCF(720, 1200) = 240

Универсальное правило

Чтобы найти GCF двух (или более) чисел:

1. Найти разложения чисел на простые множители
   
   
2. Для каждого простого множителя взять наименьшую степень, встречающуюся у всех чисел
   
   
3. Перемножить полученные множители
   
   

Результат — наибольший общий делитель.

Почему этот метод работает

Любой общий делитель:

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

Причем:

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

Именно поэтому мы:

• берем пересечение простых множителей
  
  
• выбираем минимальные степени
  
  

Итоги

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

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

В следующей главе мы разберем самое важное применение GCF —
нахождение наименьшего общего кратного (LCM).