Кратко: пусть $a,b,c\in \mathbb{Z}$. Обозначим $d=\gcd (a,b)$. Уравнение имеет целочисленные решения тогда и только тогда, когда $d\mid c$. Если решение есть, все они даются параметрически через частное решение, полученное расширенным алгоритмом Евклида.
Алгоритм и объяснение:
1. Вычислите $d=\gcd (a,b)$ (обычным алгоритмом Евклида).
2. Проверка существования:
- Если $d\nmid c$, то целых решений нет.
- Если $d\mid c$, перейдите далее.
3. Найдите целые $u,v$ такими, чтобы $au+bv=d$ (расширенный алгоритм Евклида обеспечивает такие $u,v$).
4. Домножьте на $c/d$: частное решение
$$x_0=u\cdot \frac{c}{d},y_0=v\cdot \frac{c}{d}.$$ Это действительно: $a{x}_0+b{y}_0=c$.
5. Общая формула всех целых решений:
$$x=x_0+\frac{b}{d}t,y=y_0-\frac{a}{d}t,t\in \mathbb{Z}.$$ (Здесь $\frac{b}{d}$ и $\frac{a}{d}$ — целые числа, так как $d\mid a,b$.)
Тонкости и частные случаи:
- Если $d\nmid c$ — никаких целых решений; можно говорить только о рациональных решениях.
- Если $a=0$ и $b=0$: если $c=0$ — все пары $(x,y)\in {\mathbb{Z}}^2$ — решения; если $c\ne 0$ — решений нет.
- Если $a=0$, $b\ne 0$: требуется $b\mid c$; тогда $y=c/b$ и $x$ — произвольное целое.
Аналогично при $b=0$.
- Знак $d$ обычно берут положительным; расширенный алгоритм может дать отрицательные $u,v$ — это нормально.
- Если нужны неотрицательные решения, подставьте общее решение и получите неравенства
$$x_0+\frac{b}{d}t\ge 0,y_0-\frac{a}{d}t\ge 0$$ и найдите целочисленный интервал для $t$ (используя $\lceil \cdot \rceil$ и $\lfloor \cdot \rfloor$), учитывая знаки $\frac{b}{d}$ и $\frac{a}{d}$.
Примечание по реализации: расширенный алгоритм Евклида даёт $u,v$ эффективно за $O(\log \min (|a|,|b|))$ шагов; затем формулы выше дают все решения параметрически.