Question

1. Знайди за алгоритмом Евкліда найбільший спільний дільник 56і98(Просто Нсд это понятно,а за алгоритмом Евклида нифига)
Помогите плз дам макс баллов❤️

Answer 1

Ответ:

14

про алгоритм Евкліда :

Найбільший спільний дільник двох чисел це найбільше число, що ділить обидва дані числа без остачі. Алгоритм Евкліда заснований на тому, що НСД не змінюється, якщо від більшого числа відняти менше. Наприклад, 21 є НСД чисел 252 та 105 (252 = 21 × 12; 105 = 21 × 5); оскільки 252 − 105 = 147, НСД 147 та 105 також 21. Оскільки більше з двох чисел постійно зменшується, повторне виконання цього кроку дає все менші числа, поки одне з них не дорівнюватиме нулю. Коли одне з чисел дорівнюватиме нулю, те, що залишилось, і є НСД. Обертаючи кроки алгоритму Евкліда у зворотний порядок, НСД можна виразити як лінійну комбінацію даних чисел помножених на цілі коефіцієнти, наприклад 21 = 5 × 105 + (−2) × 252. Ця важлива властивість відома як рівняння Безу.