🐴Из жизниЗадача Л. Эйлера: чиновник купил лошадей и быков ровно на $1770$ талеров, лошадь стоит $31$ талер, бык — $21$. Сколько купили лошадей и быков? Уравнение $31x+21y=1770$ содержит два неизвестных, но ответ должен состоять из целых неотрицательных чисел — купить «$2{,}7$ лошади» нельзя. Такие уравнения называют диофантовыми (по имени древнегреческого математика Диофанта).
Простейшее диофантово уравнение
Уравнение вида $ax+by=c$, где $a,b$ — целые, отличные от нуля. Если $c=0$ — решение $(0;0)$ очевидно. Если уравнение имеет решение, то $c$ обязано делиться на $d=(a,b)$ — наибольший общий делитель $a$ и $b$; иначе решений нет вовсе. Например, $3x+6y=5$ решений не имеет, так как $5$ не делится на $(3,6)=3$.
🔑Общее решениеЕсли $(a,b)=1$ и найдено какое-то одно решение $(x_0,y_0)$, то все целые решения задаются формулами $x=x_0+bn$, $y=y_0-an$, где $n$ — любое целое число.
Геометрический смысл
Уравнение $ax+by=c$ задаёт на координатной плоскости прямую. Целые решения — это в точности точки прямой с целыми координатами: они расположены на ней через равные промежутки. На интерактиве справа настрой $a$, $b$, $c$ — прямая нарисуется на целочисленной сетке, а точки с целыми координатами на ней подсветятся.
Приёмы решения
Общих методов решения диофантовых уравнений произвольной степени нет, но есть частные приёмы:
Разложение на множители. Например, $x^2-4y^2=5$ переписывают как $(x-2y)(x+2y)=5$ и перебирают все способы разложить $5$ в произведение двух целых множителей.
Выделение полного квадрата. Например, $x^2+y^2-10x+2y+22=0$ приводится к $(x-5)^2+(y+1)^2=4$, и остаётся перебрать представления числа $4$ в виде суммы двух квадратов.
⚠️Известный фактУравнение Пифагора $x^2+y^2=z^2$ имеет бесконечно много натуральных решений (стороны прямоугольных треугольников с целыми сторонами). А вот уравнение Ферма $x^n+y^n=z^n$ при $n\ge3$ не имеет ни одного решения в натуральных числах — это Великая теорема Ферма, сформулированная более $300$ лет назад и доказанная лишь в $1993$ году.
Запомни
🧠Целочисленные уравнения
$ax+by=c$ имеет решения тогда и только тогда, когда $c$ делится на $(a,b)$;
при $(a,b)=1$ все решения: $x=x_0+bn$, $y=y_0-an$, $n\in\mathbb{Z}$;
частые приёмы — разложение на множители и выделение полного квадрата;
геометрически целые решения — точки прямой $ax+by=c$ с целыми координатами.