Решение уравнений вида ( ax + by = c ) в целых числах связано с понятием делимости и наибольшего общего делителя (НОД). Чтобы найти все целые решения этого уравнения, необходимо следовать следующему методу:

Шаг 1: Проверка существования решений

Сначала убедитесь, что уравнение имеет решения. Для этого нужно проверить, делится ли ( c ) на ( \text{НОД}(a, b) ). Если ( d = \text{НОД}(a, b) ), то условие для существования решений следующее:

[
d \mid c
]

Если ( d ) не делит ( c ), то у уравнения нет целых решений.

Шаг 2: Нахождение одного решения

Если условие выше выполняется, то можно находить одно конкретное целое решение ( (x_0, y_0) ). Для этого можно воспользоваться алгоритмом Евклида для нахождения НОД. Одновременно с нахождением НОД можно применить метод обратного хода (или расширенный алгоритм Евклида) для нахождения чисел ( x_0 ) и ( y_0 ) таких, что:

[
ax_0 + by_0 = d
]

Затем, делим всё уравнение на ( d ):

[
\frac{a}{d} x_0 + \frac{b}{d} y_0 = 1
]

и множим на ( k = \frac{c}{d} ):

[
\frac{a}{d} (kx_0) + \frac{b}{d} (ky_0) = k
]

Так мы получаем одно решение ( (x_0', y_0') = (kx_0, ky_0) ).

Шаг 3: Нахождение всех решений

Все целые решения ( (x, y) ) уравнения можно выразить через найденное частное решение ( (x_0', y_0') ):

[
x = x_0' + \frac{b}{d} t
]
[
y = y_0' - \frac{a}{d} t
]

где ( t ) — произвольное целое число. Это связано с тем, что любое решение ( (x, y) ) будет изменяться по целым шагам в зависимости от коэффициентов при ( t ).

Пример

Рассмотрим уравнение:

[
6x + 9y = 15
]

Сначала вычисляем НОД:

[
d = \text{НОД}(6, 9) = 3
]

Проверяем делимость:

[
3 \mid 15 \quad \text{(да)}
]

Находим одно решение. Применяем расширенный алгоритм Евклида:

[
6 \cdot (-1) + 9 \cdot 1 = 3
]

Теперь умножаем на ( 5 ) (так как ( 15/3 = 5 )):

[
6 \cdot (-5) + 9 \cdot 5 = 15
]

Теперь у нас есть одно решение ( (-5, 5) ).

Формируем все решения:

[
x = -5 + 3t
]
[
y = 5 - 2t
]

Таким образом, мы получили общее множество решений уравнения ( 6x + 9y = 15 ).