Многие задачи приводят к уравнениям с двумя неизвестными, у которых по смыслу нужны целые решения: число мешков, монет, лет. Уравнения с целыми коэффициентами, которые надо решить в целых числах, называют диофантовыми — по имени древнегреческого математика Диофанта (III век).
Задача. Если к возрасту бабушки прибавить обе цифры этого числа, получится 83. Пусть x — цифра десятков, y — единиц: 10x + y + x + y = 83, 11x + 2y = 83. Число 2y чётное, 83 нечётное, значит, 11x нечётно и x нечётно. Так как 0 ≤ y ≤ 9, то 65 ≤ 11x ≤ 83, x ∈ {6; 7}, а значит, x = 7, y = 3: бабушке 73 года.
Метод перебора для ax + by = c: 1) найти, какие значения могут принимать переменные; 2) с помощью свойств делимости найти все возможные значения одной из них; 3) вычислить соответствующие значения другой; 4) отобрать решения, подходящие по условию. Например, 80x + 60y = 1000 ⇔ 4x + 3y = 50: x ≤ 12 и 4x при делении на 3 даёт остаток 2, поэтому x ∈ {2; 5; 8; 11}, y ∈ {14; 10; 6; 2}.
Теорема 1. Уравнение ax + by = c (a, b, c ∈ Z) имеет целые решения, если c делится на d = НОД(|a|; |b|).
Теорема 2. Если c не делится на d, целых решений нет: левая часть d(a₁x + b₁y) делится на d, а правая — нет. Так, 4x + 6y = 9 не имеет целых решений.
Способ Диофанта. Найдём одно решение уравнения 5x - 7y = -11: x₀ = 2, y₀ = 3. Тогда 5x - 7y = 5 · 2 - 7 · 3, то есть 5(x - 2) = 7(y - 3). Так как НОД(5; 7) = 1, число x - 2 кратно 7, а y - 3 кратно 5: (x - 2)/7 = (y - 3)/5 = k, k ∈ Z. Все решения: x = 7k + 2, y = 5k + 3. Если на x и y есть ограничения, из них находят возможные k.
Алгоритм: 1) найти d = НОД(|a|; |b|); 2) если c не делится на d — решений нет; 3) иначе разделить уравнение на d; 4) найти одно решение x₀, y₀; 5)–7) записать a₁(x - x₀) = -b₁(y - y₀) и выразить x = -b₁k + x₀, y = a₁k + y₀; 8)–10) учесть ограничения и записать ответ.