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

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

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

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