Наибольший общий делитель натуральных чисел-алгоритм

Запомните!

Если натуральное число делится только на 1 и на само себя, то оно называется простым.

Любое натуральное число всегда делится на 1 и на само себя.

Число 2 — наименьшее простое число. Это единственное чётное простое число, остальные простые числа — нечётные.

Простых чисел много, и первое среди них — число 2. Однако нет последнего простого числа. В разделе «Для учёбы» вы можете скачать таблицу простых чисел до 997.

Но многие натуральные числа делятся нацело ещё и на другие натуральные числа.

Например:

число 12 делится на 1, на 2, на 3, на 4, на 6, на 12;
число 36 делится на 1, на 2, на 3, на 4, на 6, на 12, на 18, на 36.

Числа, на которые число делится нацело (для 12 это 1, 2, 3, 4, 6 и 12) называются делителями числа.Запомните!

Делитель натурального числа a — это такое натуральное число, которое делит данное число «a» без остатка.

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

Обратите внимание, что числа 12 и 36 имеют общие делители. Это числа: 1, 2, 3, 4, 6, 12. Наибольший из делителей этих чисел — 12.

Общий делитель двух данных чисел «a» и «b» — это число, на которое делятся без остатка оба данных числа «a» и «b».Запомните!

Наибольший общий делитель (НОД) двух данных чисел «a» и «b» — это наибольшее число, на которое оба числа «a» и «b» делятся без остатка.

Кратко наибольший общий делитель чисел «a» и «b» записывают так:

НОД (a; b).

Пример: НОД (12; 36) = 12.

Делители чисел в записи решения обозначают большой буквой «Д».

Пример.Д (7) = {1, 7}

Д (9) = {1, 9}

НОД (7; 9) = 1

Числа 7 и 9 имеют только один общий делитель — число 1. Такие числа называют взаимно простыми числами.Запомните!

Взаимно простые числа — это натуральные числа, которые имеют только один общий делитель — число 1. Их НОД равен 1.

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

Чтобы найти НОД двух или более натуральных чисел нужно:

разложить делители чисел на простые множители;

Вычисления удобно записывать с помощью вертикальной черты. Слева от черты сначала записываем делимое, справа — делитель. Далее в левом столбце записываем значения частных.

Поясним сразу на примере. Разложим на простые множители числа 28 и 64.

Подчёркиваем одинаковые простые множители в обоих числах.
28 = 2 · 2 · 7

64 = 2 · 2 · 2 · 2 · 2 · 2
Находим произведение одинаковых простых множителей и записать ответ;
НОД (28; 64) = 2 · 2 = 4

Ответ: НОД (28; 64) = 4

Оформить нахождение НОД можно двумя способами: в столбик (как делали выше) или «в строчку».