Тренировка · 5–6 класс
Наибольший общий делитель: задачи с решением
Алгоритм Евклида заменяет пару чисел делителем и остатком, пока остаток не станет нулём.
На что обратить внимание
Последний ненулевой остаток является НОД; нулевой остаток не является ответом.
Как решать: разобранный пример
Найдите НОД чисел 1926 и 7857 алгоритмом Евклида.
- 7857 = 1926 · 4 + 153. Общие делители пары сохраняются.
- 1926 = 153 · 12 + 90. Общие делители пары сохраняются.
- 153 = 90 · 1 + 63. Общие делители пары сохраняются.
- 90 = 63 · 1 + 27. Общие делители пары сохраняются.
- 63 = 27 · 2 + 9. Общие делители пары сохраняются.
- 27 = 9 · 3 + 0. Общие делители пары сохраняются.
- Последний ненулевой делитель равен 9. Это НОД(1926; 7857).
- Проверка: 1926 = 9 · 214, 7857 = 9 · 873; частные взаимно просты.
Ответ: 9.
Попробуйте самостоятельно
- 1
Найдите НОД чисел 1926 и 7857 алгоритмом Евклида.
Решить и разобрать - 2
Найдите НОД чисел 1117 и 4234 алгоритмом Евклида.
Решить и разобрать - 3
Найдите НОД чисел 1566 и 2847 алгоритмом Евклида.
Решить и разобрать - 4
Найдите НОД чисел 710 и 5789 алгоритмом Евклида.
Решить и разобрать - 5
Найдите НОД чисел 6357 и 5216 алгоритмом Евклида.
Решить и разобрать - 6
Найдите НОД чисел 6974 и 7779 алгоритмом Евклида.
Решить и разобрать - 7
Найдите НОД чисел 2189 и 4491 алгоритмом Евклида.
Решить и разобрать - 8
Найдите НОД чисел 4166 и 1339 алгоритмом Евклида.
Решить и разобрать - 9
Найдите НОД чисел 2141 и 7458 алгоритмом Евклида.
Решить и разобрать - 10
Найдите НОД чисел 564 и 1536 алгоритмом Евклида.
Решить и разобрать - 11
Найдите НОД чисел 4321 и 518 алгоритмом Евклида.
Решить и разобрать - 12
Найдите НОД чисел 7727 и 1940 алгоритмом Евклида.
Решить и разобрать - 13
Найдите НОД чисел 3951 и 1764 алгоритмом Евклида.
Решить и разобрать - 14
Найдите НОД чисел 6270 и 932 алгоритмом Евклида.
Решить и разобрать - 15
Найдите НОД чисел 2395 и 4764 алгоритмом Евклида.
Решить и разобрать - 16
Найдите НОД чисел 4493 и 138 алгоритмом Евклида.
Решить и разобрать - 17
Найдите НОД чисел 5218 и 316 алгоритмом Евклида.
Решить и разобрать - 18
Найдите НОД чисел 1344 и 1204 алгоритмом Евклида.
Решить и разобрать - 19
Найдите НОД чисел 7685 и 6335 алгоритмом Евклида.
Решить и разобрать - 20
Найдите НОД чисел 3277 и 3195 алгоритмом Евклида.
Решить и разобрать - 21
Найдите НОД чисел 3713 и 3190 алгоритмом Евклида.
Решить и разобрать - 22
Найдите НОД чисел 4980 и 6501 алгоритмом Евклида.
Решить и разобрать - 23
Найдите НОД чисел 3247 и 3370 алгоритмом Евклида.
Решить и разобрать - 24
Найдите НОД чисел 2088 и 17 алгоритмом Евклида.
Решить и разобрать
Частые вопросы
Когда НОД двух положительных чисел равен меньшему из них?
Так бывает, если меньшее число делит большее без остатка. В общем случае НОД не превышает меньшего числа. Эта граница позволяет сразу отвергнуть результат, который не может быть общим делителем.
Как проверить НОД через разложение на простые множители?
Для небольшой пары независимо разложите оба числа и возьмите общие простые множители в меньших степенях. Полученное произведение сравните с ответом алгоритма. Одной проверки делимости недостаточно: общий делитель может оказаться не наибольшим.
Методика и условия составлены для проекта; варианты проверены расчётной моделью. Объяснения по предмету.