НОК и НОД

Уравнения в целых числах – уравнения с двумя и более неизвестными переменными и целыми коэффициентами. Решениями таких уравнений являются целые числа. Также такие уравнения называются диофантовыми, в честь древнегреческого математика Диофанта Александрийского, который изучал такие уравнения еще до нашей эры.
При решении уравнений в целых и натуральных числах можно выделить следующие способы.

1 способ. Метод перебора вариантов.

Ответ: (3; 1), (6; -2), (1; -7), (-2; -4), (4; -1), (0; -5).

Ответ: решений нет.

Ответ: (2−4n;3=5n),где n ∈ Z.

2 способ. Алгоритм Евклида

Пусть нужно решить уравнение в целых числах: 5x+7y=6.
Сделаем это с помощью Алгоритма Евклида. Ищем НОД чисел 5 и 7 с помощью него:
НОД (5, 7) = НОД (5, 7-5) = НОД (5, 2) = НОД (5 - 2∙2, 2) = НОД (1, 2) = 1

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

Разложить на множители и выразить переменную мы здесь не можем. Воспользуемся методом перебора остатков.
Если левая часть уравнения в целых числах кратна какому-то числу, то и другая обязательно должна быть кратна этому же числу. Отсюда следует, что и остатки от деления обеих частей уравнения на одно и то же число будут давать одинаковые остатки.
Будем делать выводы о делимости одной части уравнения на какое-либо число (или смотреть, какой остаток от деления при этом получается) и проверять, при каких значениях переменных вторая часть уравнения также делится на это число (либо даёт такой же остаток).
Левая часть кратна 5. И остатки от деления на 5 у обеих частей также будут равны.
Про пятёрку уже сказали, что правая часть делится на неё без остатка, значит и левая тоже должна делиться.

Рассмотрим остатки от деления на 4.

Видим простую закономерность, что 5 в любой степени при делении на 4 будет давать остаток 1.
Теперь левая часть: будет делиться на 4 без остатка.

Рассмотрим остатки от деления на 4 числа 3x

И так далее. Закономерность: при чётных х остаток 1, при нечётных остаток 3.
Отсюда делаем вывод, что х - число чётное, значит, мы можем представить его как х = 2n.

Теперь рассмотрим остатки при делении обеих частей на 3.
Правая часть:

И так далее. Видим закономерность, что при чётных z остаток равен 1, при нечетных z остаток равен 2.

Рассмотрим левую часть. Число 3x даёт остаток 0 при делении на 3.

Рассмотрим остатки от деления на 3 числа 4y

Получается, что левая часть при делении на 3 может давать только остаток 1. Значит, и правая тоже. Это происходит при чётных z.