Решить линейные диофантовы уравнения, то есть найти все целые решения уравнений

Предмет: Математика
Раздел: Теория чисел — Диофантовы уравнения (уравнения с целыми решениями)

Рассмотрим упражнения 82 (а, б) и 84 (а, б).
Задача — решить линейные диофантовы уравнения, то есть найти все целые решения уравнений вида:

ax + by = c

где a, b, c — целые числа, а x, y — переменные, принимающие целые значения.

Упражнение 82

а) 5x - 7y = 1

Шаг 1: Найдём НОД(5, 7) = 1. Так как 1 делит правую часть, уравнение имеет решения.

Используем расширенный алгоритм Евклида:

7 = 1·5 + 2  
5 = 2·2 + 1  
2 = 2·1 + 0

Теперь обратный ход:

1 = 5 - 2·2  
  = 5 - 2·(7 - 1·5) = 5 - 2·7 + 2·5 = 3·5 - 2·7

Значит, частное решение:

x₀ = 3, y₀ = 2

Общее решение:

 x = 3 + 7t \ y = 2 + 5t,\quad t \in \mathbb{Z} 

б) 12x + 17y = 2

Проверим НОД(12, 17) = 1, 1 делит 2 ⇒ решение существует.

Используем расширенный алгоритм Евклида:

17 = 1·12 + 5  
12 = 2·5 + 2  
5 = 2·2 + 1  
2 = 2·1 + 0

Обратный ход:

1 = 5 - 2·2  
  = 5 - 2·(12 - 2·5) = 5·5 - 2·12  
  = (17 - 12)·5 - 2·12 = 5·17 - 7·12

То есть:

1 = 5·17 - 7·12
Умножим обе части на 2:

2 = 10·17 - 14·12

Приведем к виду:

2 = -14·12 + 10·17 ⇒ x₀ = -14, y₀ = 10

Общее решение:

 x = -14 + 17t \ y = 10 - 12t,\quad t \in \mathbb{Z} 

Упражнение 84

а) 15x + 21y = 2

Найдем НОД(15, 21) = 3. Так как 3 не делит 2, уравнение не имеет решений.

Ответ: Нет решений.

б) 31x - 16y = 9

Проверим НОД(31, 16) = 1. 1 делит 9 ⇒ решение существует.

Расширенный алгоритм Евклида:

31 = 1·16 + 15  
16 = 1·15 + 1  
15 = 15·1 + 0

Обратный ход:

1 = 16 - 1·15  
  = 16 - 1·(31 - 1·16) = 2·16 - 1·31

Умножим на 9:

9 = 18·16 - 9·31

Преобразуем к виду:

9 = -9·31 + 18·16

Значит:

x₀ = -9, y₀ = -18

Общее решение:

 x = -9 + 16t \ y = -18 + 31t,\quad t \in \mathbb{Z} 

Теперь найдём такие x, что 33 \leq x \leq 77:

 -9 + 16t \geq 33 \Rightarrow 16t \geq 42 \Rightarrow t \geq 3 \ -9 + 16t \leq 77 \Rightarrow 16t \leq 86 \Rightarrow t \leq 5 

Возможные значения t = 3, 4, 5

Подставим:

• t = 3: x = -9 + 48 = 39, y = -18 + 93 = 75
• t = 4: x = 55, y = 106
• t = 5: x = 71, y = 137

Ответ:
Общее решение:
 x = -9 + 16t \ y = -18 + 31t 

Частные решения при 33 \leq x \leq 77:

 (x, y) = (39, 75), (55, 106), (71, 137) 

Если нужно, могу продолжить с другими пунктами.