целые-числа - Решить уравнение $%13x-8y=1$%

Охарактеризуем сначала все решения в целых числах, а потом отберём из них те, где числа натуральные.

Для взаимно простых коэффициентов решение всегда существует (согласно известной и полезной лемме из теории чисел). Найти одно частное решение, если коэффициенты небольшие, проще всего подбором. А именно, берём числа вида $%13x-1$%, начиная с $%-1$%, и прибавляем по 13 до тех пор, пока не получим число, кратное 8. Имеем: -1, 12, 25, 38, 51, 64. Мы прибавляли 13 пять раз, поэтому $%x=5$%, и тогда $%y=8$%.

Теперь, когда построено частное решение $%(x_0;y_0)$%, рассмотрим общее решение $%(x;y)$%. У нас выполнены два равенства: $%13x-8y=1$% и $%13x_0-8y_0=1$%. Вычтем из одного равенства другое: $%13(x-x_0)=8(y-y_0)$%. Ввиду взаимной простоты чисел 13 и 8, $%x-x_0$% кратно $%8$%. Полагаем $%x-x_0=8t$%, где $%t$% целое. При этом $%y-y_0=13t$%.

Таким образом, общее решение представляется в виде $%(x;y)=(5+8t;8+13t)$%. Для того, чтобы числа были натуральными, требуется, чтобы $%t$% было целым неотрицательным. Получается бесконечная серия решений. Из частного решения $%(5;8)$% следующие решения получаются по простому принципу: к первому числу прибавляется 8, а ко второму 13. То есть дальше будет $%(13;21)$%, $%(21;34)$%, $%(29;47)$%, и так далее.