В чем заключается принцип поиска общего делителя коэффициентов в математических уравнениях?

Принцип поиска общего делителя коэффициентов в математических уравнениях заключается в использовании алгоритма Евклида. genius.pstu.ru ru.wikipedia.org

Этот алгоритм применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и остатка от деления большего числа на меньшее. ru.wikipedia.org Процесс повторяется, пока числа не станут равными. ru.wikipedia.org Найденное число и есть наибольший общий делитель исходной пары. ru.wikipedia.org

Алгоритм решения неопределённого уравнения с помощью алгоритма Евклида: genius.pstu.ru

1. Найти наибольший общий делитель чисел a и b. genius.pstu.ru Если (a, b) = d > 1 и с не делится на d, то уравнение целых решений не имеет. genius.pstu.ru Если (a, b) = d > 1 и cMd, то уравнение имеет целые решения. genius.pstu.ru
2. Разделить почленно уравнение ax + by = c на d, получив при этом уравнение a1x + b1 y = c1, в котором (a1, b1) = 1. genius.pstu.ru
3. Найти целое решение (х0, у0) уравнения a1x + b1y = 1 путём представления 1 как линейной комбинации чисел a и b. genius.pstu.ru
4. Составить общую формулу целых решений данного уравнения. genius.pstu.ru