Наибольший общий делитель двух чисел

Наибольшим общим делителем двух натуральных чисел называют:

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

Наибольший общий делитель часто обозначают НОД.

Как найти наибольший общий делитель двух чисел?

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

Наибольший общий делитель двух натуральных чисел 3 и 12

Число 12 нацело делится на 3. Отсюда следует, что число 3 есть наибольший общий делитель двух чисел 3 и 12.

Наибольший общий делитель двух целых чисел 42 и 140

Разложим числа 42 и 140 на множители, потом определим наибольший общий делитель двух чисел 42 и 140.

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

Найдем наибольший общий делитель 42 и 140 по шагам (алгоритм нод).

1. Разложим на множители число 140:

140  2 * 5
 14 7
  2 2
  1 

Число 140 разлагаем на множители так:

140 = 2 * 2 * 5 * 7

2. Разложим на множители число 42:

42  2
21  3
 7  7
 1 

Число 42 разлагаем на множители так:

42 = 2 * 3 * 7

3. Найдем общие множители в разложениях чисел 42 и 140:

140 –> (2, 2, 5, 7)
42 –> (2, 3, 7)
Совпадают (2, 7)

4. Произведение общих множителей есть наибольший общий делитель двух чисел 42 и 140:

2 * 7 = 14

5. Ответ: НОД чисел 42 и 140 есть число 14:

НОД(140, 42) = 14