Применение НОД и НОК. Алгоритм Евклида

• Алгоритм Евклида — это алгоритм, основная функция которого заключается в поиске наибольшего общего делителя (НОД) для двух целых неотрицательных чисел.

• Суть алгоритма Евклида для чисел a и b ($𝑎>𝑏$) методом деления:

  • большее число делят на меньшее с остатком: $𝑎=𝑏\cdot {𝑞}_1+{𝑟}_1$, $0<{𝑟}_1<𝑏$;

  • затем меньшее на первый остаток: $𝑏={𝑟}_1\cdot {𝑞}_2+{𝑟}_2$, $0<{𝑟}_2<{𝑟}_1$;

  • затем первый остаток – на второй остаток и так далее, пока не получится 0:

${𝑟}_1={𝑟}_2\cdot {𝑞}_3+{𝑟}_3$, $0<{𝑟}_3<{𝑟}_2$;

${𝑟}_2={𝑟}_3\cdot {𝑞}_4+{𝑟}_4$, $0<{𝑟}_4<{𝑟}_3$;

…

${𝑟}_{𝑘-1}={𝑟}_{𝑘}\cdot {𝑞}_{𝑘+1}$, ${𝑟}_{𝑘+1}=0$;

• последний остаток – это НОД: ${𝑟}_{𝑘}=НОД (𝑎;𝑏)$.

Суть метода вычитания состоит в том, что необходимо из большего числа вычитать меньшее, если результат вычитания не равен нулю, тогда уменьшаемое заменяем на получившуюся разность, если разность равна нулю, то НОД равен предыдущему значению разности.