Найти НОД 2 способами 428 и 54, 232 и 728, 411 и 25, 29 и 78

Для вычисления наибольшего общего делителя, двух и более, положительных целых чисел существует несколько способов.

Один из них: вычисление НОД по алгоритму Евклида.

Воспользуемся и покажем на примере, как пользоваться алгоритмом Евклида.

а) НОД (428; 54).

Шаг 1. Делим 428 на 5 4, получаем 428 / 5 4 = 7 (ост. 50), что можно записать в виде равенства 428 = 54 * 7 + 50.

Шаг 2. Делим 54 делим на остаток от деления - 50, получаем 5 4 / 50 = 50 * 1 + 4.

Следующий шаг: 50 / 4 = 1 * 12 + 2.

Опять делаем шаг: 4 / 2 = 1 * 2 + 0.

В остатке имеем 0, значить 2 является искомым наибольшим общим делителем чисел 428 и 5 4.

б) Вычислим НОД (411; 25).

Шаг 1. 411 / 25 = 1 * 16 + 11.

Шаг 2. 25 / 11 = 2 * 11 + 3.

Шаг 3. 11 / 3 = 3 * 3 + 2.

Шаг 4. 3 / 2 = 1 * 1 + 1.

Шаг 5. 1 / 1. Числа взаимно простые. Общий делитель равен 1.

в) Вычислим НОД (78; 29).

Шаг 1. 78 / 29 = 2 * 29 + 20.

Шаг 2. 29 / 20 = 1 * 20 + 9.

Шаг 3. 20 / 9 = 3 * 9 + 2.

Шаг 4. 9 / 2 = 4 * 2 + 1.

Шаг 5. 2 / 1 → числа взаимно простые. Общий делитель - 1.

Второй способ основан на разложении чисел на простые множители.

Рассмотрим один из них, остальные можно выполнить по образцу.

НОД (428; 54) Разложим 428 и 54 на простые множители: 428 = 2 * 2 * 107,

54 = 2 * 27 * 3 * 3 * 3.

Видно, что в разложении чисел, общим является число 2.

Ответ: 2 - наибольший общий делитель.