Практикум по решению линейных диофантовых уравнений

Практикум по решению линейных  диофантовых  уравнений.

Цели:

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

Развивающие:  формирование умений обобщать, сравнивать, оценивать, анализировать,  делать выводы;  развитие познавательных возможностей, творческих способностей, креативности личностных качеств.

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

Решение уравнений в целых числах – один из самых красивых разделов математики. Долгое время надеялись найти общий способ решения диофантовых уравнений. Однако в 1970г. ленинградский математик  Матиясевич  доказал, что такого общего способа быть не может.  Диофантовы  уравнения относятся к арифметическим. Поскольку они сводятся к уравнениям с целыми коэффициентами, где решения требуется найти только целые, часто  натуральные. Для выделения таких решений из всего бесконечного их множества приходится пользоваться свойствами целых чисел, а это относится к области арифметики.

  Диофантовым уравнением 1-й степени с n неизвестными называется уравнение вида а₁х + а₂х₂ + а₃х₃ +…+аᵣхᵣ= в (1), где все коэффициенты и неизвестные – целые числа и хотя бы одно а ≠ 0.

Теорема 1. При взаимно простых коэффициентах и при b=1 диофантово уравнение (1) имеет решение в целых числах.

Теорема 2.  Если в уравнении ах +ву = 1 (2) НОД(а;в) = 1, то уравнение (2) имеет, по крайней мере, одно целое решение.

Теорема 3. Если пара целых чисел х₀, у₀ удовлетворяет уравнению 

ах + ву = с (3) , где а, в, с - целые числа, отличные от нуля и НОД(а;в) = 1, то

х = х₀ + вn,  у = у₀ - аn,  (3).

где n – произвольное целое число, является общим решением этого уравнения в целых числах.

В частности, линейное диофантово уравнение с двумя неизвестными имеет вид: ах + ву = с. Формулой у = с/в – ах/в задается линейная функция. Ее графиком является прямая.  Следовательно,  все точки прямой у = с/в – ах/в являются решениями уравнения  ах + ву = с и таких решений  бесконечно много.

Рассмотрим неопределенное уравнение первой степени:  2х + 3у = 5. Если требуется найти натуральные решения уравнения, то пара чисел (1;1) - единственное натуральное решение данного уравнения. Если требуется назвать любое целочисленное решение данного уравнения, то достаточно назвать любую пару, удовлетворяющую уравнению, например: (4;-1). Если требуется найти все целочисленные решения, то

х = 1+3n; у = 1 – 2n, где  n – целое число.

Решить в целых числах (х;у) уравнение:  5х - 8у = 19.

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

Первый способ. Нахождение частного решения методом подбора и запись общего решения.

НОД(5;8) =1,т. к 5 и 8  взаимно - простые числа, то уравнение  5х - 8у = 19 имеет решение в целых числах. Методом подбора находим частное решение х=7;  у= 2. Итак пара чисел (7;2) - частное решение уравнения  5х - 8у = 19. Значит, выполняется равенство:  5∙7 - 8∙2 = 19. Как, имея одно решение записать все остальные?  Вычтем из уравнения  5х - 8у = 19  равенство 5∙7 - 8∙2 = 19  и получим:  5(х-7) – 8(у-2) = 0. Отсюда,  х-7 = 8(у-2)/5.  (х-7) будет целым тогда и только тогда, когда (у-2) делится на 5, т. е. у-2 = 5n, где  n – целое число. Итак,  у = 2+5n, тогда  х = 7+8n,  где n-целое число.

Второй  способ.  Решение уравнения относительно одного неизвестного.

Решаем уравнение относительно того неизвестного, при котором наименьший (по модулю) коэффициент. Например,  5х - 8у = 19 ,

х = (8у+19)/5. Остатки при делении на 5: 0,1, 2, 3, 4.

Подставим  вместо  у  эти числа. Если у = 0, то х = 19/5;  если  у = 1,то х = 27/5;  если у = 2, то х = 7- целое число;  если  у = 3, то х = 43/5;  если у = 4, то х = 51/5. Итак, пара(7;2) - частное решение уравнения  5х - 8у = 19. Тогда общее решение уравнения  5х - 8у = 9:  х = 7+8n,

у= 2+5n, где n –целое число.

Если с = 0, то уравнение  ах + ву = 0 – однородное и множество решений записывается: (вn; - аn), где n - целое число.

Уравнение 3х +4у = 0 – однородное, график - прямая, проходящая через начало координат. Уравнение имеет бесконечно много решений вида (4n; 3n), где n – целое число. Запишем несколько частных решений в виде таблицы:

n	х	у
0	0	0
1	4	-3
-1	-4	3

5х – 6у = 0 – однородное уравнение имеет бесконечно много решений вида (-6n; - 5n), где n – целое число.

Запишем несколько частных решений в виде таблицы:

n	х	у
0	0	0
1	-6	-5

ах + ву = с – неоднородное уравнение, если с ≠ 0. Может иметь целочисленные решения, а может не иметь.

1. Решить в целых числах  уравнение: 2х-4у=9, 2(х-2у)=9.  Левая часть уравнения кратна 2, а правая часть нет, следовательно, данное уравнение в целых числах решений не имеет.  График уравнения – прямая, все точки этой прямой являются решением этого уравнения. Пара (1/2; -2)- решение уравнения, но не целое число.

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

2. Решить в натуральных числах уравнение: 3х+ 6у = 10.

3(х+2у) = 10. Левая часть уравнения кратна 3, а правая часть нет, следовательно, данное уравнение в натуральных числах решений не имеет.

Ответ: данное уравнение в натуральных  числах решений не имеет.

3. Найти целые решения уравнения: 2х + 3у = 5. (1;1) - частное решение уравнения.

Если (х₀,у₀) - какое либо решение уравнения  ах + ву = с, то все решения задаются формулами  х = х₀ + вn;  у = у₀ - аn,  где n –целое число(3).

(1;1)- частное решение уравнения. Зная формулу(3), по которой находятся все решения, запишем:  х = 1+3n, у = 1-2n, где n – целое число.

Ответ: (1+3n; 1- 2n), n –целое число.

4. Найти целые решения уравнений: а) 2х+3у = 7.

(2;1) - частное решение уравнения, тогда общее решение данного уравнения имеет вид:  х = 2+3n, у = 1-2n, где n – целое число;

б) 5х+4у=1. (1;-1) - частное решение уравнения, тогда общее решение данного уравнения:  х = 1+4n, у = -1-5n, где n – целое число.

5.  Найти целые решения уравнения:  4х - 6у = 18 , сократим обе части уравнения на  2. Получим:  2х-3у = 9,  х = (9+3у):2, 9 = 8+1,3 = 2+1,

х = (8+1+2у+у):2,  х = 4+у+(у+1):2,  пусть (у+1):2 = n, у+1 = 2n,

у = 2n-1,тогда х = 4+2n-1+n, х = 3n+3.

Ответ: (3n+3; 2n-1), где n-целое число.

6. Решить в целых числах уравнение: 10х-3у = 19.

Выразим у =  3х – 6 + (х-1):3, пусть (х -1):3 = n,  х – 1 = 3n,  х = 3n + 1,

у = 3(3n+1) - 6 + n,  у= 10 n – 3.

Ответ: (3n + 1; 10 n – 3), где n - целое число.

7. Решить в целых числах уравнение: 7х - 19у = 145.

Выразим неизвестное с наименьшим (по модулю) коэффициентом:

х = (145+19у):7,  х = 20+2у+(5+5у):7. При делении на 7 получаются остатки: 0,1,2,3,4,5,6. Переберем остатки от 0 до 6, при которых  (5+5у):7  -  целое число. Например, подходит 6, тогда, если  у=6, то  х=37.  Значит, пара (37;6) – частное решение, следовательно, зная формулу(3), по которой находятся все решения, запишем: х = 37-19n,  у = 6- 7n.

Ответ: (37-19n;  6- 7n), где n - целое число.

8. Решить в целых числах уравнение: 21х-48у = 6,  7х+16у = 2, 

пара (-2;1) - частное решение, Зная формулу(3), по которой находятся все решения, запишем: х = -2+16n, у = 1-7n, где n-целое число.

Ответ: (2+16n;1-7n), где n-целое число.

9. Решить в целых числах уравнение: 3х-5у=19.

3х = 19+5у,  х = (19+5у):3,  х= 6+2у +(1-у):3, 

Пусть (1-у):3 = n, тогда  1-у = 3n, отсюда,  у = 1-3n, 

х = 6+2(1-3n) + (1-1+3n):3,  х = -5n + 8, где  n-целое число.

Ответ: (-5n + 8; 1-3n),  где n-целое число.

10. Сколько натуральных решений имеет уравнение: 2х+3у = 5?

Ответ: одно;(1;1).

11. Сколько решений в целых числах имеет уравнение: 2х+3у= 9?

Левая часть уравнения не кратна 3, а правая часть кратна 3.  Пара (0;3) - частное решение уравнения. Зная формулу(3), по которой находятся все решения, запишем: х = 3+3n, у = 1-2n, где  n-целое число.

Ответ: бесконечное множество.

12.Сколько целых решений имеет уравнение: 4х – 8у = 10?

Сократим обе части уравнения на 2, получим: 2х – 4у = 5. Левая часть уравнения кратна 2, а правая нет, следовательно, данное уравнение целых решений не имеет.

Ответ: 0.

13. Решить в целых числах уравнение: 5х – 3у = 2. Выразим неизвестное с наименьшим (по модулю) коэффициентом: 3у = 5х – 2,

у = (5х – 2):3. Выделим целую часть:  у = 1 + (2х – 2):3, при делении на 3 остатки: 0,1,2. Переберем  остатки от 0 до 2, при которых (2х - 2):3 – целое число. Например, подходит  1. Проверим,  (2∙1 – 2):3 = 0- верно, тогда  у = 1, пара  (1;1) – частное решение данного уравнения. Зная формулу(3), по которой находятся все решения, запишем:  х = 1 + 3n, у = 1 – 5n, где  n-целое число.

Ответ: (1 + 3n; 1 – 5n), где  n-целое число.

14. Решить в целых числах уравнение: 3х + 5у = 7.

Пара (- 1;2) – частное решение данного уравнения. Зная формулу(3), по которой находятся все решения, запишем: х = -1 +5n, у = 2 – 3n, где  n-целое число.

Ответ: (-1 +5n; 2 – 3n) , где  n-целое число.

Для самостоятельного решения.

1.Сколько решений имеет уравнение 2х + 3у =8? Ответ: бесконечное множество.

2. Сколько решений в целых числах имеет уравнение: 5х + 15у =16? Ответ: 0.

3. Решите уравнения в целых числах: а) 4х + 3у = 2. Ответ: х = 2 – 3n, у = - 2 +4n, где  n-целое число;

б) 2х – 5у = 1. Ответ: х = -2 +5n, у = - 1 + 2n, где  n-целое число;

в) 7х + 5у = 10. Ответ: х = - 20 + 5n, у = 30 - 7n, где  n-целое число;

г) 3х – 11у = -4. Ответ: х = - 16 - 11n, у = - 4 - 3n, где  n-целое число;

д) 20х +3у = 10. Ответ: х = - 10 + 3n, у = 70 – 20n, где  n-целое число;