Наибольший общий делитель (НОД)

Определение наибольшего общего делителя (НОД)

 

Наибольшим общим делителем нескольких чисел называется число, которое является делителем каждого из них. То есть это наибольшее число, на которое оба числа a и b делятся без остатка.

Например:

Найдем НОД (21, 14, 42) = 7. Каждое из чисел 21, 14, 42 делится на 7 без остатка и это наибольший общий делитель.

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

 

Рассмотрим, как найти НОД на примере.

Чтобы найти НОД нескольких чисел надо (найти НОД (180, 150)):

 

Шаг 1

Представить каждое число в виде простых множителей:

Шаг 2

Записать степени всех простых множителей.

 

Шаг 3

Выписать все общие делители (множители) этих чисел.

Шаг 4

Выбрать наименьшую степень каждого из них, встретившуюся во всех произведениях.

Наименьшая степень общих делителей 2, 3 и 5.

 

Шаг 5

Перемножить эти степени.

Перемножим 2, 3 и 5:

Итак,

то есть на 30 можно разделить каждое число:

Пример 1

 

Найти наибольший общий делитель (НОД) чисел 252, 30, 1512.

 

Шаг 1

Представим каждое число в виде простых множителей:

Шаг 2

Где возможно, запишем степени полученных множителей:

Шаг 3

Выпишем все общие делители:

Шаг 4

Выберем наименьшую степень каждого из них: это 2¹ и 3¹.

Шаг 5

Перемножим эти степени:

Итак, мы нашли наибольший общий делитель:

То есть на 6 можно разделить каждое число без остатка:

Пример 2

 

Найдем НОД чисел 1050, 630, 2205.

 

Шаг 1

Разложим каждое число на множители:

Шаг 2

Где возможно, запишем степени полученных множителей:

Шаг 3

Выпишем все общие делители:

Шаг 4

Выберем наименьшую степень каждого из них: это 3¹, 5¹ и 7¹.

Шаг 5

Перемножим их:

Итак, мы нашли наибольший общий делитель:

НОД (1050, 630, 2205) = 105, то есть на 105 можно разделить каждое число без остатка.

Делимость целых чисел. Понятие делимости

Свойства делимости

Кратные числа и делители числа

Совершенное число

Дружественные числа

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

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

Свойства взаимно простых чисел

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

Алгоритм Евклида, чтобы найти НОД

Как найти НОД трех и более чисел

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

Теорема о разложении на множители. Основная теорема арифметики