§ 5. Решение уравнений в целых числах

Определения и обозначения

Уравнение в целых числах — уравнение, в котором требуется найти только целые значения неизвестных. Целые числа — это натуральные числа, противоположные им числа и ноль. Такое ограничение меняет задачу: значение, подходящее в обычном вычислении, может оказаться дробным и потому не подойти. Определение помогает сразу понять, какие ответы нужно искать.

Целочисленное решение — набор целых чисел, обращающий уравнение в верное равенство. Если неизвестных две, решением служит пара чисел, например (x, y) = (2, −1). Недостаточно получить подходящие значения из преобразованного выражения: их нужно проверить в исходном уравнении. Это понятие задаёт критерий правильного ответа.

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

Линейное диофантово уравнение — уравнение вида ax + by = c, для которого исследуется существование и вид целочисленных решений. Здесь a, b и c — целые числа, а x и y нужно найти целыми. Сначала проверяют, возможно ли решение вообще, а затем находят одно решение и описывают остальные. Эта запись позволяет применять НОД и алгоритм Евклида.

Как это устроено

В действительных числах между целыми есть дробные значения, а при решении в целых их использовать запрещено. Поэтому задача не сводится к обычному нахождению корней: нужно дополнительно выяснить, какие из них целые, и не пропустить другие целочисленные варианты. Например, равенство может иметь бесконечно много действительных решений, но ни одного целого. Ограничение области поиска делает важными делимость и остатки.

Для ax + by = c любое значение ax + by делится на НОД(a, b), поскольку НОД делит и ax, и by, а значит, их сумму. Поэтому если этот НОД не делит c, равенство невозможно для целых x и y. Если делимость выполняется, алгоритм Евклида помогает представить НОД как целую линейную комбинацию a и b; умножив её на c/НОД(a, b), получаем решение. Из одного решения выводят все остальные, меняя переменные на взаимно компенсирующие шаги.

Если после преобразования получается произведение двух целых выражений, равное постоянному числу, каждый множитель обязан быть целым делителем этого числа. Причина проста: если ab = N, то a делит N, а b = N/a. Вместо поиска среди бесконечного множества чисел мы перебираем конечный набор делителей и проверяем, дают ли они целые значения неизвестных. Отрицательные делители тоже нужны, поскольку произведение двух отрицательных чисел положительно.

Чётность и сравнения по модулю позволяют заметить ограничения, незаметные при обычных преобразованиях. Сравнение по модулю m означает сравнение остатков при делении на m; например, квадрат целого числа при делении на 4 даёт только остаток 0 или 1. Если возможные остатки левой части не совпадают с остатком правой, решений нет. Такой способ особенно полезен, когда перебор делителей неудобен или невозможно заранее ограничить неизвестные.

Оценка, чётность или сравнение обычно сначала оставляют несколько кандидатов, а не дают готовое полное решение. Найденные значения следует подставить в исходное равенство: преобразования могли ввести ограничения или допустить лишний вариант. Отдельно нужно доказать полноту: объяснить, почему не пропущены другие делители, остатки или значения в установленных границах. Без этого верная найденная пара ещё не является полным ответом на вопрос «найти все решения».

Основные методы решения уравнений в целых числах

Сначала определите, к какому типу ближе задача, и выберите приём, который сокращает множество кандидатов. Затем проверьте ключевое условие метода и используйте полученные ограничения. В конце обоснуйте, что перебраны все возможные варианты.

Разбор задач

Уравнение x² − y² = 15

Нужно найти все целые пары, поэтому полезно заменить разность квадратов произведением. Произведение позволит использовать конечный список делителей 15, а не перебирать любые x и y. После подбора пар множителей восстановим неизвестные и проверим ответ.

1. Разложим левую часть: (x − y)(x + y) = 15. Обозначим a = x − y и b = x + y; тогда ab = 15.
2. Поскольку a и b — делители нечётного числа, оба множителя нечётные. Их упорядоченные пары: (1, 15), (3, 5), (5, 3), (15, 1) и пары с противоположными знаками (−1, −15), (−3, −5), (−5, −3), (−15, −1).
3. Из равенств a = x − y и b = x + y получаем x = (a + b)/2, y = (b − a)/2. Подставляя пары множителей, получаем (8, 7), (4, 1), (4, −1), (8, −7), (−8, −7), (−4, −1), (−4, 1), (−8, 7).
4. В каждой паре x² − y² равно 15, поскольку произведение соответствующих множителей равно 15. Других вариантов нет: все целые пары a, b с ab = 15 перечислены.

Ответ: (x, y) = (8, 7), (4, 1), (4, −1), (8, −7), (−8, −7), (−4, −1), (−4, 1), (−8, 7).

Уравнение 3x + 5y = 7

Здесь уравнение линейное, поэтому сначала проверим делимость на НОД коэффициентов. Если условие выполняется, найдём одну пару, а затем запишем формулу всех решений. Это важно, потому что один удачный подбор не гарантирует, что решение единственное.

1. НОД(3, 5) = 1, а 1 делит 7. Значит, целочисленные решения существуют.
2. Подберём частное решение: при x = 4 и y = −1 получаем 3 · 4 + 5 · (−1) = 7.
3. Изменение x на 5t увеличивает 3x на 15t, а изменение y на −3t уменьшает 5y на 15t. Поэтому сумма сохраняется, и все решения имеют вид x = 4 + 5t, y = −1 − 3t, где t ∈ Z.
4. Подстановка этих выражений даёт 3(4 + 5t) + 5(−1 − 3t) = 7 при любом целом t. Общая формула для линейного уравнения показывает, что иных решений нет.

Ответ: x = 4 + 5t, y = −1 − 3t, где t ∈ Z.

Уравнение x² + y² = 3

Нужно доказать, что целых решений нет, поэтому искать пары перебором не требуется. Проверим, какие остатки могут иметь квадраты целых чисел при делении на 4. Если сумма таких остатков не может равняться остатку числа 3, получится противоречие.

1. Любое целое число чётно или нечётно. Квадрат чётного числа делится на 4 и имеет остаток 0.
2. Нечётное число можно записать как 2k + 1. Его квадрат равен 4k² + 4k + 1, поэтому при делении на 4 он имеет остаток 1.
3. Значит, сумма двух квадратов может иметь по модулю 4 только остаток 0, 1 или 2. Но число 3 имеет остаток 3.
4. Получили противоречие: равенство x² + y² = 3 невозможно для целых x и y.

Ответ: целых решений нет.

Типичные ошибки

Первая ошибка — решать уравнение среди всех действительных чисел и считать найденные корни ответом. Так можно получить дробные значения, которые не удовлетворяют требованию задачи. Ошибку допускают, когда забывают про область допустимых значений. Проверяйте каждую пару: оба числа должны быть целыми и удовлетворять исходному равенству.

Вторая ошибка — объявить найденное решение линейного уравнения единственным. Например, уравнение 3x + 5y = 7 имеет не одну целочисленную пару, а бесконечное семейство. Это происходит, когда находят подбором только один вариант и не исследуют изменение переменных. Проверьте условие через НОД и запишите общий ответ с целым параметром.

Третья ошибка при разложении на множители — рассматривать только положительные делители или одну последовательность множителей. Тогда теряются пары с отрицательными значениями или другим порядком, хотя они могут приводить к новым решениям. Часто это случается из-за привычки работать только с натуральными числами. Для произведения N выпишите все целые делители, включая отрицательные, и проверьте каждый порядок множителей.

Четвёртая ошибка — считать совпадение остатков по модулю доказательством существования решения. Сравнение по модулю обычно показывает лишь необходимое условие: подходящие остатки ещё не гарантируют целых x и y. Эту ошибку допускают, принимая отсутствие противоречия за готовое доказательство. Используйте сравнение, чтобы исключить невозможные случаи, а существование подтверждайте найденным решением и подстановкой.

Связь с другими темами

Для решения таких задач нужны знания о делимости, простых и составных числах, НОД и алгоритме Евклида. Они помогают проверять линейные уравнения и составлять список возможных множителей. Навыки преобразования выражений, решения линейных и квадратных уравнений позволяют получать удобную форму для дальнейшего анализа. Умение работать с системами ограничений пригодится при проверке целочисленных значений.

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

Что запомнить

• В уравнениях в целых числах допустимы только целые значения неизвестных.
• Уравнение ax + by = c имеет целочисленные решения тогда и только тогда, когда НОД(a, b) делит c.
• Все решения линейного диофантова уравнения можно записать через один целочисленный параметр.
• При разложении на множители нужно рассматривать все целые делители, включая отрицательные.
• Чётность и сравнения по модулю помогают доказать невозможность целочисленных решений.
• Окончательный ответ необходимо проверить в исходном уравнении и обосновать полноту найденных решений.