НОД 20,30

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

Ответ: 10

Пошаговое решение с объяснениями

1. Метод Евклида

• gcd(20, 30) = gcd(30, 20) (потому что НОД не зависит от порядка чисел).
• 30 mod 20 = 10, значит gcd(30, 20) = gcd(20, 10).
• 20 mod 10 = 0, значит gcd(20, 10) = 10.
• Следовательно, НОД(20, 30) = 10.

2. Разложение на простые множители

• 20 = 2^2 * 5
• 30 = 2 * 3 * 5
• Общие простые множители: 2 и 5. Взяв минимальные степени: 2^1 и 5^1.
• gcd = 2 * 5 = 10.

Проверка

• 10 делит и 20, и 30.
• Большее число, которое делит оба, проверить нельзя (20 не делится на 30, и т.д.), значит 10 — максимальный общий делитель.

Итого: НОД(20, 30) = 10.