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

  • 7 мин чтения
  • Послушать — 4 мин
  • 14 карточек

Математика, 7 класс · Л. Г. Петерсон, Д. Л. Абраров, Е. В. Чуткова · § 1. Линейные уравнения

Многие задачи приводят к уравнениям с двумя неизвестными, у которых по смыслу нужны целые решения: число мешков, монет, лет. Уравнения с целыми коэффициентами, которые надо решить в целых числах, называют диофантовыми — по имени древнегреческого математика Диофанта (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) учесть ограничения и записать ответ.

Определение

1 / 14

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

Многие задачи приводят к уравнениям с двумя неизвестными, у которых по смыслу нужны целые решения: число мешков, монет, лет.

Уравнения с целыми коэффициентами, которые надо решить в целых числах, называют диофантовыми — по имени древнегреческого математика Диофанта (III век).

Разбор

2 / 14

Возраст бабушки

Если к возрасту бабушки прибавить обе цифры этого числа, получится 83. Сколько лет бабушке?

Пусть x — цифра десятков, y — единиц.

  1. Уравнение

    10x + y + x + y = 83, 11x + 2y = 83

  2. Чётность

    2y чётно, 83 нечётно ⇒ 11x нечётно, x нечётно

  3. Границы

    0 ≤ y ≤ 9: 65 ≤ 11x ≤ 83, x ∈ {6; 7}

  4. Ответ

    x = 7, y = 3: бабушке 73 года

Разбор

4 / 14

Перебор по остаткам

Решим в целых неотрицательных числах 80x + 60y = 1000.

  1. Границы

    4x + 3y = 50; 4x ≤ 50, x ≤ 12

  2. Делимость

    4x = 50 - 3y при делении на 3 даёт остаток 2: x ∈ {2; 5; 8; 11}

  3. Второе

    y = (50 - 4x)/3: y ∈ {14; 10; 6; 2}

  4. Ответ

    (2; 14), (5; 10), (8; 6), (11; 2)

Проверь себя

5 / 14

Чётность помогает

Слагаемое 2y всегда чётное.

3x + 2y = 17, x и y натуральные. Каким может быть x?

только нечётнымтолько чётнымлюбым
Ответ и объяснение

3x = 17 - 2y нечётно, значит, x нечётно: x ∈ {1; 3; 5}.

Формула

6 / 14

Когда решения есть

Теорема 1. Уравнение ax + by = c (a, b, c ∈ Z) имеет целые решения, если c делится на

d = НОД(|a|; |b|)

6x + 4y = 10: d = 2, 10 vdots 2 — целые решения есть, например x = 1, y = 1.

Свойство

7 / 14

Когда решений нет

Теорема 2. Если c не делится на d, целых решений нет:

ax + by = d(a₁x + b₁y) делится на d, а c — нет.

4x + 6y = 9: 4x + 6y = 2(2x + 3y) — чётное, а 9 нечётное.

Проверь себя

8 / 14

Есть ли решения

Найди d = НОД(|a|; |b|) и проверь, делится ли c на d.

Есть ли целые решения у 6x + 9y = 20?

нетда
Ответ и объяснение

d = 3, а 20 на 3 не делится — целых решений нет.

Разбор

9 / 14

Способ Диофанта

Найдём все целые решения уравнения 5x - 7y = -11.

  1. Одно решение

    x₀ = 2, y₀ = 3: 5 · 2 - 7 · 3 = -11

  2. Вычитаем

    5x - 7y = 5 · 2 - 7 · 3, 5(x - 2) = 7(y - 3)

  3. Делимость

    НОД(5; 7) = 1: (x - 2)/7 = (y - 3)/5 = k, k ∈ Z

  4. Ответ

    x = 7k + 2, y = 5k + 3, k ∈ Z

Правило

10 / 14

Алгоритм решения

  1. d = НОД(|a|; |b|); если c не делится на d — решений нет.
  1. Разделить уравнение на d: a₁x + b₁y = c₁.
  1. Найти одно решение x₀, y₀; записать a₁(x - x₀) = -b₁(y - y₀).
  1. x = -b₁k + x₀, y = a₁k + y₀, k ∈ Z; учесть ограничения.

Пример

11 / 14

Ограничения на k

Натуральные решения 5x - 7y = -11 с x < 20:

x = 7k + 2 < 20 — k ≤ 2; y = 5k + 3 > 0, x > 0 — k ≥ 0.

k ∈ {0; 1; 2}: (2; 3), (9; 8), (16; 13).

Частая ошибка

12 / 14

Одно решение — не все

Ошибка: нашли x = 2, y = 3 и записали ответ.

Но x = 9, y = 8 — тоже решение: 45 - 56 = -11.

Решений бесконечно много: x = 7k + 2, y = 5k + 3, k ∈ Z.

Проверь себя

13 / 14

Ещё одно решение

Подставь пару в 5x - 7y.

Какая пара — решение 5x - 7y = -11?

(9; 8)(9; 3)(7; 5)
Ответ и объяснение

5 · 9 - 7 · 8 = 45 - 56 = -11; это k = 1.

Главное

14 / 14

Главное

  • Перебор: границы, чётность, остатки
  • c vdots d, d = НОД(|a|; |b|) — целые решения есть, иначе нет
  • a₁(x - x₀) = -b₁(y - y₀)
  • x = -b₁k + x₀, y = a₁k + y₀, k ∈ Z

Проверь себя: тест по теме

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

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест