НОД 522 и 126

Задача: найти НОД(522, 126).

Решение (Евклидов алгоритм):

• Шаг 1: Разложим 522 на делители 126. 522 = 4 * 126 + 18 Остаток равен 18.
• Шаг 2: Теперь ищем НОД(126, 18): 126 = 7 * 18 + 0 Остаток стал 0, значит НОД равен последнему ненулевому остатку — 18.

Проверка:

• 522 ÷ 18 = 29, остаток 0.
• 126 ÷ 18 = 7, остаток 0. Итак, 18 делит оба числа, и это наибольшее такое число.

Альтернативный способ (разложение на простые множители):

• 522 = 2 × 3^2 × 29
• 126 = 2 × 3^2 × 7 Общие простые множители: 2 и 3^2, значит НОД = 2 × 3^2 = 18.

Ответ: 18.