Найти: а) НОД и НОК чисел a и b; б) линейное представление НОД чисел a и b, используя расширенный алгоритм Евклида. Число a "47850" Число b "4335"

Нам дано два числа: a = 47850 и b = 4335.

Условие задания:

1. Найти наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) чисел a и b.
   
2. Найти линейное представление НОД чисел a и b, то есть найти такие целые числа x и y, что НОД(a, b) = a·x + b·y, используя расширенный алгоритм Евклида.
   
   Решение:
   
   

1. Вычисляем НОД(47850, 4335) с помощью алгоритма Евклида.
   
   Шаг 1. Делим 47850 на 4335:
     47850 = 4335 · 11 + 165
   Остаток r1 = 165.
   
   Шаг 2. Делим 4335 на 165:
     4335 = 165 · 26 + 45
   Остато...