НОД нескольких чисел

Как найти нод нескольких чисел? Как найти нод нескольких натуральных чисел?

Ответ на эти вопрос найдем на примере.

Наибольший общий делитель чисел 324, 111 и 432

Найти наибольший общий делитель чисел 324, 111 и 432 можно, разложив эти числа на множители.

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

Найдем наибольший общий делитель 324, 111 и 432.

Будем искать НОД по шагам (алгоритм нод).

1. Разложить на простые множители число 324:

324  3
108  3
 36  3
 12  3
  4  2
  2  2
  1 

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

324 = 2 * 2 * 3 * 3 * 3 * 3

2. Разложить на простые множители число 111:

111  3
 37  37
  1 

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

111 = 3 * 37

3. Разложить на простые множители число 432:

432  3
144  3
 48  3
 16  2
  8  2
  4  2
  2  2
  1 

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

432 = 2 * 2 * 2 * 2 * 3 * 3 * 3

4. Найдем общие множители в разложениях чисел 324, 111 и 432:

324 –> (2, 2, 3, 3, 3, 3)
111 –> (3, 37)
432 –> (2, 2, 2, 2, 3, 3, 3)
Совпадают
(3)

5. Произведение общих множителей есть наибольший общий делитель 3 чисел 324, 111 и 432.

Здесь только один общий множитель для трех чисел. Он и будет нод чисел 324, 111 и 432.

6. Ответ: НОД чисел 324 111 и 432 есть число 3:

НОД(324, 111, 432) = 3