izamorfix.ru
Введение Счёт, единица и число Устная нумерация Письменная нумерация Натуральные числа Количественный и порядковый счёт Разряды и классы Разрядные слагаемые Числовые и буквенные выражения Сравнение Арифметические действия Определение и знаки Действия первой и второй ступени Порядок действий Проценты Увеличение числа Уменьшение числа Сложение Слагаемые и сумма Сложение и вычитание с нулём Законы сложения Группировка слагаемых Округление при сложении Изменение суммы Прибавление суммы к числу и числа к сумме Сложение столбиком Нахождение неизвестного слагаемого Подобные слагаемые Таблица сложения Вычитание Уменьшаемое, вычитаемое и разность Вычитание столбиком Вычитание числа из суммы Вычитание суммы из числа Округление при вычитании Изменение разности Умножение Множимое, множитель и произведение Умножение на единицу и на ноль Законы умножения Умножение суммы на число Умножение числа на сумму Умножение числа на произведение Умножение двузначного числа на однозначное Изменение произведения Умножение столбиком Степень числа Таблица умножения Деление Делимое, делитель и частное Деление двузначного числа на однозначное Деление с остатком Свойства деления Признаки делимости Свойства делимости Изменение частного Деление столбиком Среднее арифметическое Делимость чисел Кратное и делитель Простые и составные числа Разложение числа на простые множители Нахождение всех делителей числа Наибольший общий делитель Как найти НОД Наименьшее общее кратное Меры и величины Измерение величин Единицы измерения Сложение и вычитание величин Обыкновенные дроби Обыкновенные дроби Числитель и знаменатель Правильные и неправильные дроби Основное свойство дроби Сокращение дробей Общий знаменатель Сравнение дробей Сложение Вычитание Умножение и деление Возведение в степень Взаимно обратные числа Смешанные числа Смешанные числа Перевод неправильной дроби в смешанное число Перевод смешанного числа в дробь Сравнение Сложение Вычитание Умножение и деление Возведение в степень Десятичные дроби Десятичные дроби Перевод дробей Сравнение Свойство Сложение десятичных дробей Перенос запятой Умножение и деление Округление чисел Отношения и пропорции Отношение чисел Пропорции Задачи и задания Системы счисления Определение Десятичная система Римская система Перевод из одной системы в другую Двоичная арифметика Решение задач На разностное сравнение На сложение и вычитание На умножение и деление На приведение к единице На кратное сравнение На части На уравнивание На дроби На совместную работу На цену, количество и стоимость На скорость, время и расстояние На нахождение по двум суммам неизвестного На нахождение по двум разностям неизвестного На встречное движение На противоположное движение На одно направление На движение по реке Приложение Таблица простых чисел Латинский алфавит Онлайн калькуляторы

Как найти НОД

Рассмотрим два способа нахождения наибольшего общего делителя.

Нахождение путём разложения на множители

Первый способ заключается в нахождении наибольшего общего делителя путём разложения данных чисел на простые множители.

Чтобы найти НОД нескольких чисел, достаточно, разложить их на простые множители и перемножить между собой те из них, которые являются общими для всех данных чисел.

Пример 1. Найдём НОД (84, 90).

Раскладываем числа  84  и  90  на простые множители:

Итак, мы подчеркнули все общие простые множители, осталось перемножить их между собой:

1 · 2 · 3 = 6.

Таким образом, НОД (84, 90) = 6.

Пример 2. Найдём НОД (15, 28).

Раскладываем  15  и  28  на простые множители:

Числа  15  и  28  являются взаимно простыми, так как их наибольший общий делитель — единица.

НОД (15, 28) = 1.

Алгоритм Евклида

Второй способ (иначе его называют способом Евклида) заключается в нахождении НОД путём последовательного деления.

Сначала мы рассмотрим этот способ в применении только к двум данным числам, а затем разберёмся в том, как его применять к трём и более числам.

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

Пример 1. Возьмём два числа  27  и  9.  Так как  27  делится на  9  и  9  делится на  9,  значит,  9  является общим делителем чисел  27  и  9.  Этот делитель является в тоже время и наибольшим, потому что  9  не может делиться ни на какое число, большее  9.  Следовательно:

НОД (27, 9) = 9.

В остальных случаях, чтобы найти наибольший общий делитель двух чисел используется следующий порядок действий:

  1. Из двух данных чисел большее число делят на меньшее.
  2. Затем, меньшее число делят на остаток, получившийся от деления большего числа на меньшее.
  3. Далее, первый остаток делят на второй остаток, который получился от деления меньшего числа на первый остаток.
  4. Второй остаток делят на третий, который получился от деления первого остатка на второй и т. д.
  5. Таким образом деление продолжается до тех пор, пока в остатке не получится нуль. Последний делитель как раз и будет наибольшим общим делителем.

Пример 2. Найдём наибольший общий делитель чисел  140  и  96:

1) 140 : 96 = 1 (остаток 44)

2) 96 : 44 = 2 (остаток 8)

3) 44 : 8 = 5 (остаток 4)

4) 8 : 4 = 2

Последний делитель равен  4  — это значит:

НОД (140, 96) = 4.

Последовательное деление так же можно записывать столбиком:

Чтобы найти наибольший общий делитель трёх и более данных чисел, используем следующий порядок действий:

  1. Сперва находим наибольший общий делитель любых двух чисел из нескольких данных.
  2. Затем находим НОД найденного делителя и какого-нибудь третьего данного числа.
  3. Затем находим НОД последнего найденного делителя и четвёртого данного числа и так далее.

Пример 3. Найдём наибольший общий делитель чисел  140,  96  и  48.  НОД чисел  140  и  96  мы уже нашли в предыдущем примере (это число  4).  Осталось найти наибольший общий делитель числа  4  и третьего данного числа —  48:

1) 48 : 4 = 12

48  делится на  4  без остатка. Таким образом:

НОД (140, 96, 48) = 4.