Все формулы РФ

Математика / Арифметика и теория чисел

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

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

Опубликовано: Обновлено:

Школьная программаФормулы по математике за 6 классАрифметикаТеория чиселКалькуляторЕсть историческая справка

Формула

$$\gcd(a,b)=\prod p_i^{\min(\alpha_i,\beta_i)}$$

Обозначения

a, b
натуральные числа, числа
$p_i$
общие простые множители, простые числа
$α_i, β_i$
показатели одного простого множителя в разложениях a и b, степени

Условия применения

  • Числа натуральные и не равны одновременно нулю.
  • Для способа через простые множители оба числа разложены на простые множители.
  • Ищется наибольшее число, на которое оба исходных числа делятся без остатка.

Ограничения

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

Подробное объяснение

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

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

В 6 классе НОД особенно важен для дробей. Чтобы сократить дробь максимально, нужно разделить числитель и знаменатель на их НОД. Также НОД встречается в задачах на разбиение предметов на одинаковые наборы: если есть 24 карандаша и 36 тетрадей, НОД показывает наибольшее число одинаковых комплектов без остатка.

Как пользоваться формулой

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

Историческая справка

Задачи на общий делитель возникали в практической арифметике: нужно было делить предметы на равные группы, сокращать отношения и сравнивать меры. Один из древнейших системных методов нахождения НОД - алгоритм Евклида, описанный в античной математике. Он позволяет находить НОД без полного разложения чисел на простые множители.

В 6 классе чаще начинают со способа через простые множители, потому что он наглядно связан с делимостью и сокращением дробей. Исторически оба подхода описывают одну идею: найти максимальную общую меру двух чисел. Эта идея оказалась настолько фундаментальной, что используется не только в школьной арифметике, но и в алгебре, теории чисел и информатике.

Историческая линия формулы

Понятие НОД относится к древней арифметике, а классический алгоритм нахождения НОД связан с Евклидом. Школьная формула через простые множители является современным учебным способом той же идеи общей меры для чисел и отношений.

Пример

Найдем НОД чисел 84 и 126. Разложим числа: 84 = 2^2 · 3 · 7, 126 = 2 · 3^2 · 7. Общие простые множители: 2, 3 и 7. Берем меньшие степени: для 2 это 2^1, для 3 это 3^1, для 7 это 7^1. Получаем НОД = 2 · 3 · 7 = 42. Проверка: 84 : 42 = 2, 126 : 42 = 3, значит 42 действительно общий делитель. Большего общего делителя быть не может, потому что все общие простые множители уже взяты в максимально возможных общих степенях. Это же число можно использовать для максимального сокращения дроби 84/126 до 2/3.

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

Частая ошибка - брать все множители из обоих разложений, что дает НОК, а не НОД. Вторая ошибка - выбирать большие степени общих простых множителей вместо меньших. Третья ошибка - забывать, что если общий простой множитель есть только в одном числе, он не входит в НОД. Еще одна ошибка - считать, что НОД взаимно простых чисел равен 0; на самом деле он равен 1.

Практика

Задачи с решением

НОД через разложение

Условие. Найдите НОД чисел 72 и 90.

Решение. 72 = 2^3 · 3^2, 90 = 2 · 3^2 · 5. Общие множители в меньших степенях: 2 · 3^2 = 18.

Ответ. 18

Одинаковые наборы

Условие. Есть 30 яблок и 45 груш. На какое наибольшее число одинаковых наборов можно разложить фрукты без остатка?

Решение. Нужно найти НОД(30,45). 30 = 2 · 3 · 5, 45 = 3^2 · 5. НОД = 3 · 5 = 15.

Ответ. 15 наборов

Калькулятор

Посчитать по формуле

Введите значения и нажмите «Рассчитать».

Дополнительные источники

  • OpenStax Prealgebra 2e: Greatest common factor

Связанные формулы

Математика

Разложение числа на простые множители

$n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$

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

Математика

Наименьшее общее кратное

$\operatorname{lcm}(a,b)=\prod p_i^{\max(\alpha_i,\beta_i)}$

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

Математика

Сокращение дроби по НОД

$\frac{a}{b}=\frac{a:d}{b:d},\quad d=\gcd(a,b)$

Чтобы сократить дробь максимально, числитель и знаменатель делят на их наибольший общий делитель, сохраняя значение дроби и получая несократимую запись.