Наибольший общий делитель двух чисел — это самое большое число, на которое оба числа делятся без остатка.
Делители 24: 1, 2, 3, 4, 6, 8, 12, 24. Делители 30: 1, 2, 3, 5, 6, 10, 15, 30.
Общие делители: 1, 2, 3 и 6. Самый большой из них — 6. Значит, НОД(24, 30) = 6.
24 = 2 × 2 × 2 × 3, а 30 = 2 × 3 × 5. Берём только те множители, которые есть в обоих разложениях: двойка и тройка. НОД = 2 × 3 = 6 — тот же ответ, без перебора всех делителей.
Если наибольший общий делитель двух чисел равен единице, такие числа называют взаимно простыми. Обратите внимание: сами по себе эти числа не обязаны быть простыми.
Делители 8: 1, 2, 4, 8. Делители 9: 1, 3, 9. Общий делитель только один — единица. Значит, НОД(8, 9) = 1, и числа 8 и 9 взаимно простые, хотя оба они составные.
Наименьшее общее кратное двух чисел — это самое маленькое число, которое делится и на первое, и на второе число одновременно.
Кратные 24: 24, 48, 72, 96, 120, ... Кратные 30: 30, 60, 90, 120, ...
Первое общее число в обоих списках — 120. Значит, НОК(24, 30) = 120.
24 = 2 × 2 × 2 × 3, а 30 = 2 × 3 × 5. Берём все множители первого числа (2, 2, 2, 3), а из разложения второго добавляем только те множители, которых ещё не было — это пятёрка (двойка и тройка уже учтены).
НОК = 2 × 2 × 2 × 3 × 5 = 120 — тот же ответ, что и при переборе.