← Маршрут ЕГЭ
Тема 59 из 72 · Теория чисел

Диофантовы уравнения

Линейные и нелинейные диофантовы уравнения в целых числах

ТГ-каналПодписывайся · там же запись на вводный урок t.me/algo_math ↗
Содержание 16 разделов
  1. 1. Что такое диофантово уравнение
  2. 2. Когда уравнение имеет решение (условие разрешимости)
  3. 3. Общее решение линейного диофантова уравнения
  4. 4. Основные методы решения
  5. Метод 1. Подбор частного решения
  6. Метод 2. Выделение целой части
  7. Метод 3. Разложение на множители
  8. Метод 4. Метод сравнений по модулю
  9. 5. Реальные задачи из ЕГЭ с разбором
  10. Задача 1 (ЕГЭ 2022, прототип)
  11. Задача 2 (Разность квадратов)
  12. Задача 3 (Система с двумя диофантовыми уравнениями)
  13. 6. Нелинейные диофантовы уравнения
  14. Пифагоровы тройки
  15. Уравнение $x^2 - y^2 = n$
  16. 7. Типичные ошибки

1. Что такое диофантово уравнение

Диофантово уравнение — это уравнение, решение которого ищется в целых (или натуральных) числах. Название происходит от имени древнегреческого математика Диофанта Александрийского, который исследовал такие уравнения ещё до нашей эры .

В задании №20 ЕГЭ чаще всего встречаются линейные диофантовы уравнения с двумя неизвестными:

$$ax + by = c$$

где $a$, $b$, $c$ — целые числа, $x$ и $y$ — неизвестные, которые нужно найти в целых числах.

Пример из жизни

Задача: купить яблоки по 3 рубля и груши по 5 рублей на 23 рубля.

Уравнение: $3a + 5b = 23$, где $a$ — число яблок, $b$ — число груш.

Решения: $a=1, b=4$ (1 яблоко и 4 груши) или $a=6, b=1$ (6 яблок и 1 груша) .

2. Когда уравнение имеет решение (условие разрешимости)

Линейное диофантово уравнение $ax + by = c$ имеет решение в целых числах тогда и только тогда, когда $\text{НОД}(a,b)$ делит $c$ .

$$ax + by = c \text{ разрешимо в целых числах } \iff \text{НОД}(a,b) \mid c$$

Пример 1: $3x + 5y = 7$. $\text{НОД}(3,5) = 1$, $1 \mid 7$ → решения есть.

Пример 2: $6x + 9y = 3$. $\text{НОД}(6,9) = 3$, $3 \mid 3$ → решения есть .

Пример 3: $6x + 9y = 2$. $\text{НОД}(6,9) = 3$, $3 \nmid 2$ → решений нет.

Важно

Если $\text{НОД}(a,b)$ не делит $c$, уравнение не имеет решений в целых числах. Это первый шаг в решении любой диофантовой задачи!

3. Общее решение линейного диофантова уравнения

Если уравнение $ax + by = c$ разрешимо, и мы нашли одно частное решение $(x_0, y_0)$, то все решения имеют вид :

$$x = x_0 + \frac{b}{d} \cdot t, \qquad y = y_0 - \frac{a}{d} \cdot t$$

где $d = \text{НОД}(a,b)$, $t \in \mathbb{Z}$ — произвольное целое число.

Пример

Решите уравнение $3x + 5y = 7$.

  1. Находим частное решение: подбором $x_0 = 4$, $y_0 = -1$ (проверка: $3\cdot4 + 5\cdot(-1) = 12 - 5 = 7$).
  2. $d = \text{НОД}(3,5) = 1$.
  3. Общее решение: $x = 4 + 5t$, $y = -1 - 3t$, $t \in \mathbb{Z}$.

Ответ: $(4 + 5t;\, -1 - 3t)$, $t \in \mathbb{Z}$.

4. Основные методы решения

Метод 1. Подбор частного решения

Подходит для уравнений с небольшими коэффициентами .

Пример

$5x - 8y = 19$.

  1. Подбираем: $x_0 = 7$, $y_0 = 2$ (проверка: $5\cdot7 - 8\cdot2 = 35 - 16 = 19$).
  2. $\text{НОД}(5,8) = 1$.
  3. Общее решение: $x = 7 + 8t$, $y = 2 + 5t$, $t \in \mathbb{Z}$ .

Метод 2. Выделение целой части

Выражаем одну переменную через другую и выделяем целую часть дроби .

Пример

$11x + 19y = 260$ (из ЕГЭ).

  1. Выражаем $x = \dfrac{260 - 19y}{11} = 23 - y + \dfrac{7 - 8y}{11}$.
  2. Дробь $\dfrac{7 - 8y}{11}$ должна быть целой.
  3. Проверяем остатки $y$ при делении на 11: подходит $y \equiv 5 \pmod{11}$.
  4. $y = 5 + 11k$, тогда $x = 15 - 19k$.
  5. При условии $x, y \ge 0$ подходит только $k = 0$ → $x = 15$, $y = 5$ .

Метод 3. Разложение на множители

Применяется, когда уравнение можно привести к виду $A \cdot B = C$ .

Пример

Решите уравнение $xy + 3x - 5y = -3$.

  1. Перепишем: $x(y+3) - 5(y+3) = -3 - 15$ → $(x-5)(y+3) = -18$.
  2. Пусть $a = x-5$, $b = y+3$, тогда $ab = -18$.
  3. Выписываем все делители $-18$ и получаем все пары $(x, y)$.

Метод 4. Метод сравнений по модулю

Рассматриваем сравнение $ax \equiv c \pmod b$ .

Пример

$3a + 5b = 23$.

  1. $23 - 3a \equiv 0 \pmod 5$ → $3a \equiv 3 \pmod 5$ → $a \equiv 1 \pmod 5$.
  2. $a = 1 + 5k$. Подставляем: $3(1+5k) + 5b = 23$ → $5b = 20 - 15k$ → $b = 4 - 3k$.
  3. При $a, b \ge 0$: $k = 0$ → $(1, 4)$; $k = 1$ → $(6, 1)$.

5. Реальные задачи из ЕГЭ с разбором

Задача 1 (ЕГЭ 2022, прототип)

Задача 1

Фирма продавала чай в центре города по 7 рублей, а кофе по 10 рублей за стакан; на вокзале — по 4 рубля и 9 рублей соответственно. Всего было продано за час 20 стаканов чая и 20 стаканов кофе, при этом выручка в центре и на вокзале оказалась одинаковой. Сколько стаканов кофе было продано в центре?

Решение.

  1. Пусть $x$ — число стаканов чая в центре, $y$ — число стаканов кофе в центре.
  2. Тогда на вокзале продано $(20-x)$ стаканов чая и $(20-y)$ стаканов кофе.
  3. Выручка в центре: $7x + 10y$.
  4. Выручка на вокзале: $4(20-x) + 9(20-y)$.
  5. По условию выручки равны: $7x + 10y = 4(20-x) + 9(20-y)$.
  6. Раскрываем скобки: $7x + 10y = 80 - 4x + 180 - 9y$ → $11x + 19y = 260$.
  7. Находим частное решение подбором: $x_0 = 15$, $y_0 = 5$ (проверка: $11\cdot15 + 19\cdot5 = 165 + 95 = 260$).
  8. Общее решение: $x = 15 + 19t$, $y = 5 - 11t$, $t \in \mathbb{Z}$ .
  9. Так как $x, y$ — количество стаканов, они должны быть от $0$ до $20$.
  10. При $t = 0$: $x = 15$, $y = 5$ — подходит.
  11. При $t = 1$: $x = 34 > 20$ — не подходит.
  12. При $t = -1$: $y = 16$, но $x = -4 < 0$ — не подходит.

Ответ: 5 стаканов кофе.

Задача 2 (Разность квадратов)

Задача 2

Найдите все пары натуральных чисел $(x, y)$, удовлетворяющих уравнению $x^2 - y^2 = 33$ .

Решение.

  1. Раскладываем левую часть: $(x-y)(x+y) = 33$.
  2. Так как $x$ и $y$ — натуральные, то $x+y > x-y > 0$.
  3. Делители 33: $1, 3, 11, 33$.
  4. Рассматриваем системы:
    • $\begin{cases} x-y = 1 \\ x+y = 33 \end{cases}$ → $x = 17$, $y = 16$.
    • $\begin{cases} x-y = 3 \\ x+y = 11 \end{cases}$ → $x = 7$, $y = 4$.
  5. Проверяем: обе пары — натуральные числа .

Ответ: $(17;16)$, $(7;4)$.

Задача 3 (Система с двумя диофантовыми уравнениями)

Задача 3

Найти все пары целых чисел $(x, y)$, удовлетворяющих уравнению $2x^2 + 5 = 3y^2 + 5xy$ .

Решение.

  1. Преобразуем уравнение: $2x^2 + 5 = 3y^2 + 5xy$ → $3y^2 + 5xy - 2x^2 = 5$.
  2. Раскладываем левую часть на множители: $(3y - x)(y + 2x) = 5$.
  3. Получаем системы уравнений:
    • $\begin{cases} 3y - x = 5 \\ y + 2x = 1 \end{cases}$ — нет решений в целых числах.
    • $\begin{cases} 3y - x = -5 \\ y + 2x = -1 \end{cases}$ — нет решений.
    • $\begin{cases} 3y - x = 1 \\ y + 2x = 5 \end{cases}$ → решаем: из второго $y = 5 - 2x$, подставляем: $3(5-2x) - x = 1$ → $15 - 6x - x = 1$ → $-7x = -14$ → $x = 2$, $y = 1$.
    • $\begin{cases} 3y - x = -1 \\ y + 2x = -5 \end{cases}$ → решаем: $y = -5 - 2x$, подставляем: $3(-5-2x) - x = -1$ → $-15 - 6x - x = -1$ → $-7x = 14$ → $x = -2$, $y = -1$.
  4. Получаем две пары: $(2;1)$ и $(-2;-1)$ .

Ответ: $(2;1)$, $(-2;-1)$.

6. Нелинейные диофантовы уравнения

Пифагоровы тройки

Уравнение $x^2 + y^2 = z^2$ имеет бесконечно много решений в натуральных числах. Общий вид:

$$x = m^2 - n^2, \qquad y = 2mn, \qquad z = m^2 + n^2 \quad (m > n > 0)$$

Примеры пифагоровых троек: $(3,4,5)$, $(5,12,13)$, $(8,15,17)$, $(7,24,25)$.

Уравнение $x^2 - y^2 = n$

Сводится к разложению: $(x-y)(x+y) = n$. Нужно перебрать все пары делителей $n$ одной чётности .

Пример

$x^2 - y^2 = 91$.

  1. $(x-y)(x+y) = 91 = 1 \cdot 91 = 7 \cdot 13$.
  2. Системы:
    • $\begin{cases} x-y = 1 \\ x+y = 91 \end{cases}$ → $x = 46$, $y = 45$.
    • $\begin{cases} x-y = 7 \\ x+y = 13 \end{cases}$ → $x = 10$, $y = 3$ .

Ответ: $(46;45)$, $(10;3)$.

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

Ошибка Как правильно
Забыть проверить условие $\text{НОД}(a,b) \mid c$ Если условие не выполнено — решений нет!
Потерять знак $«-»$ при подстановке Внимательно проверяйте знаки в формулах общего решения.
Не учитывать ограничения (натуральность, неотрицательность) Всегда проверяйте, что решения удовлетворяют условию задачи.
Путать целые и натуральные числа Натуральные: $1,2,3,\dots$; целые: $\dots,-2,-1,0,1,2,\dots$ .
Забыть отрицательные делители При разложении на множители учитывайте все делители, включая отрицательные .
← 58. Остатки. Сравнения. Модулярная арифмети…