СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ

Благодаря готовым учебным материалам для работы в классе и дистанционно

Скидки до 50 % на комплекты
только до

Готовые ключевые этапы урока всегда будут у вас под рукой

Организационный момент

Проверка знаний

Объяснение материала

Закрепление изученного

Итоги урока

Линейные диофантовы уравнения

Категория: Математика

Нажмите, чтобы узнать подробности

Линейные диофантовы уравнения и методы их решения в школьном курсе математики не изучаются. Их можно встретить, в основном, лишь в олимпиадных заданиях. В данной работе рассматриваются следующие способы решения линейных диофантовых уравнений: алгоритм Евклида, метод перебора,  метод спуска,  метод рассмотрения остатков от деления, а также приведены примеры решения линейных диофантовых уравнений с тремя неизвестными.

Просмотр содержимого документа
«Линейные диофантовы уравнения»

Линейные диофантовы уравнения  Исследовательская работа по алгебре ученика 9 класса МОУ «Упшинская ООШ» Антонова Юрия  «Если вы хотите научиться плавать, то  смело входите в воду, а если хотите  научиться решать задачи, то решайте их.»  Д.Пойя  Руководитель – Софронова Н.А .

Линейные диофантовы уравнения

Исследовательская работа по алгебре

ученика 9 класса МОУ «Упшинская ООШ»

Антонова Юрия

«Если вы хотите научиться плавать, то

смело входите в воду, а если хотите

научиться решать задачи, то решайте их.»

Д.Пойя

Руководитель – Софронова Н.А .

 Задача   Для настилки пола шириной в 3 метра имеются доски шириной в 11 см и 13 см. Сколько нужно взять досок того и другого размера?  Если х – число досок шириной в 11 см, а у – число досок шириной в 13 см, то нам надо решить уравнение:  11 х + 13 у = 300

Задача

Для настилки пола шириной в 3 метра имеются доски шириной в 11 см и 13 см. Сколько нужно взять досок того и другого размера?

Если х – число досок шириной в 11 см, а у – число досок шириной в 13 см, то нам надо решить уравнение:

11 х + 13 у = 300

Особенности уравнения 11 х + 13 у = 300:   ▪ Коэффициенты 11, 13, 300 – целые числа.  ▪ Число неизвестных превышает число уравнений.  ▪ Решения данного уравнения х и у должны быть целыми  положительными числам  Алгебраические уравнения или системы алгебраических уравнений с целыми коэффициентами, в которых число неизвестных превышает число уравнений и для которых надо найти целые решения, называют неопределенными или диофантовыми, по имени греческого математика Диофанта .

Особенности уравнения 11 х + 13 у = 300:Коэффициенты 11, 13, 300 – целые числа. Число неизвестных превышает число уравнений. Решения данного уравнения х и у должны быть целыми положительными числам

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

Примеры диофантовых уравнений 1 . Найдите все пары целых чисел  x , y , для которых верно  равенство  2 . Покажите, что уравнение  имеет бесконечное множество решений  целых числах

Примеры диофантовых уравнений

1 . Найдите все пары целых чисел

x , y , для которых верно равенство

2 . Покажите, что уравнение

имеет бесконечное множество решений

целых числах

 Цель работы:   Выяснить: Всегда ли можно найти для конкретного неопределенного уравнения все целые решения или доказать отсутствие таковых? Какие методы с уществуют для решения диофантовых уравнений?

Цель работы:

Выяснить:

  • Всегда ли можно найти для конкретного неопределенного уравнения все целые решения или доказать отсутствие таковых?
  • Какие методы с уществуют для решения диофантовых уравнений?

Задачи: Найти и и зучить методы решения линейных диофантовых уравнений с двумя переменными. Рассмотреть возможности теории линейных диофантовых уравнений.

Задачи:

  • Найти и и зучить методы решения линейных диофантовых уравнений с двумя переменными.
  • Рассмотреть возможности теории линейных диофантовых уравнений.

Пифагоровы тройки Неопределенные уравнения в целых числах решались еще до Диофанта. Большой интерес вызывало, например, алгебраическое уравнение x 2 + y 2 = z 2 , связывающее стороны x , у , z прямоугольного треугольника. Натуральные числа x , y и z , являющиеся решениями этого уравнения, называются

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

  • Неопределенные уравнения в целых числах решались еще до Диофанта. Большой интерес вызывало, например, алгебраическое уравнение x 2 + y 2 = z 2 , связывающее стороны x , у , z прямоугольного треугольника. Натуральные числа x , y и z , являющиеся решениями этого уравнения, называются "пифагоровыми тройками" .
Уравнение Ферма К работам Диофанта имеют непосредственное отношение и математические исследования французского математика Пьера Ферма. Считается, что именно с работ Ферма началась новая волна в развитии теории чисел. И одна из его задач - это знаменитое уравнение Ферма х n + y n = z n

Уравнение Ферма

  • К работам Диофанта имеют непосредственное отношение и математические исследования французского математика Пьера Ферма. Считается, что именно с работ Ферма началась новая волна в развитии теории чисел. И одна из его задач - это знаменитое уравнение Ферма

х n + y n = z n

 Ни один крупный математик не прошел мимо теории диофантовых уравнений.  Ферма, Эйлер, Лагранж, Гаусс, Чебышев оставили неизгладимый след в этой интересной теории.

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

Ферма, Эйлер, Лагранж, Гаусс, Чебышев оставили неизгладимый след в этой интересной теории.

1, ( Каталана); ах 2 + bxy + су 2 + dx + еу + f = 0 , где а , b , с , d , е , f — целые числа, т. е. общее неоднородное уравнение второй степени с двумя неизвестными (П.Ферма, Дж. Валлис, Л. Эйлер, Ж. Лагранж и К.Гаусс) " width="640"

Примеры неопределенных уравнений решаемых великими математиками 19-го и 20-го столетий: x 2 ny 2 = 1 , где n не является точным квадратом (Ферма, Пелля); x z y t = 1 , где z , t 1, ( Каталана); ах 2 + bxy + су 2 + dx + еу + f = 0 , где а , b , с , d , е , f — целые числа, т. е. общее неоднородное уравнение второй степени с двумя неизвестными (П.Ферма, Дж. Валлис, Л. Эйлер, Ж. Лагранж и К.Гаусс)

Диофантовы уравнения  в 20 веке  1900 год. Международный математический конгресс. 10-я проблема Гильберта  Задано Диофантово уравнение с некоторым числом неизвестных и рациональными целыми коэффициентами. Необходимо придумать процедуру, которая могла определить за конечное число операций – является ли уравнение разрешимым в рациональных целых числах.  Русский математик Юрий Матиясевич доказал : 10-ая проблема Гильберта неразрешима - требуемого в ней алгоритма не существует.

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

1900 год. Международный математический конгресс.

10-я проблема Гильберта

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

Русский математик Юрий Матиясевич доказал :

10-ая проблема Гильберта неразрешима - требуемого в ней алгоритма не существует.

Всегда ли можно найти для конкретного неопределенного уравнения все целые решения или доказать отсутствие таковых? Проблема решения уравнений в целых числах решена до конца только для уравнений первой степени с двумя или тремя неизвестными. ДУ второй степени с двумя неизвестными решаются уже с большим трудом. ДУ второй степени с числом неизвестных больше двух решены лишь в отдельных частных случаях, например уравнение x 2 + y 2 = z 2 .  ДУ степени выше второй имеют, как правило, лишь конечное число решений (в целых числах). Для уравнений выше второй степени с двумя или более неизвестными достаточно трудной является даже задача существования целочисленных решений. Например, неизвестно, имеет ли уравнение  x 3 + y 3 + z 3 = 30 хотя бы одно целочисленное решение.  Для решения отдельных ДУ, а иногда и для конкретных уравнений, приходится изобретать новые методы. Очевидно, что алгоритма, который позволял бы находить решения произвольных ДУ не существует.

Всегда ли можно найти для конкретного неопределенного уравнения все целые решения или доказать отсутствие таковых?

  • Проблема решения уравнений в целых числах решена до конца только для уравнений первой степени с двумя или тремя неизвестными.
  • ДУ второй степени с двумя неизвестными решаются уже с большим трудом.
  • ДУ второй степени с числом неизвестных больше двух решены лишь в отдельных частных случаях, например уравнение x 2 + y 2 = z 2 .
  • ДУ степени выше второй имеют, как правило, лишь конечное число решений (в целых числах).
  • Для уравнений выше второй степени с двумя или более неизвестными достаточно трудной является даже задача существования целочисленных решений. Например, неизвестно, имеет ли уравнение

x 3 + y 3 + z 3 = 30 хотя бы одно целочисленное решение.

  • Для решения отдельных ДУ, а иногда и для конкретных уравнений, приходится изобретать новые методы. Очевидно, что алгоритма, который позволял бы находить решения произвольных ДУ не существует.
Линейные диофантовы уравнения Общий вид:   ЛДУ с двумя переменными: a х + by = c   ЛДУ с тремя переменными: a х + by + cz = d

Линейные диофантовы уравнения

Общий вид:

ЛДУ с двумя переменными:

a х + by = c

ЛДУ с тремя переменными:

a х + by + cz = d

ЛДУ с двумя неизвестными  ЛДУ с двумя переменными: a х + by = c  Решения: x = х 0 - bt у = у 0 + at  Однородные: a х + by = 0  Решения: x = - bt у = at

ЛДУ с двумя неизвестными

ЛДУ с двумя переменными:

a х + by = c

Решения:

x = х 0 - bt

у = у 0 + at

Однородные:

a х + by = 0

Решения:

x = - bt

у = at

Поиск частного решения Методы решения: Метод кратных. Применение алгоритма Евклида. Метод перебора. Метод спуска. Метод рассмотрения остатков от деления Метод рассмотрения остатков от деления

Поиск частного решения

Методы решения:

  • Метод кратных.
  • Применение алгоритма Евклида.
  • Метод перебора.
  • Метод спуска.
  • Метод рассмотрения остатков от деления
  • Метод рассмотрения остатков от деления

Метод кратных Решить уравнение 11 х + 2 у = 69      Ищем сумму, равную 69: 55 + 14 = 69 Частное решение уравнения х 0 = 5, у 0 = 7 n кр.11 1 11 2 кр.2 3 2 22 33 4 4 5 44 6 55 6 8 10 7 66 77 12 8 14 9 88 99 16 18

Метод кратных

Решить уравнение 11 х + 2 у = 69

Ищем сумму, равную 69: 55 + 14 = 69 Частное решение уравнения

х 0 = 5, у 0 = 7

n

кр.11

1

11

2

кр.2

3

2

22

33

4

4

5

44

6

55

6

8

10

7

66

77

12

8

14

9

88

99

16

18

Применение алгоритма Евклида Решить уравнение 4 х + 7 у = 16  Найдем НОД чисел 4 и 7 по алгоритму Евклида : НОД(4,7) = 1  Выразим число 1 через коэффициенты а = 4 и b  =7, используя теорему о линейном разложении НОД:  НОД ( а, b ) = au + bv .  Получим: 1 = 4 ∙ 2 + 7 ∙ (-1) u = 2, v = -1  Частное решение уравнения : х 0 = 2 ∙ 16 = 32,  у 0 = -1 ∙ 16 = -16

Применение алгоритма Евклида

Решить уравнение 4 х + 7 у = 16

  • Найдем НОД чисел 4 и 7 по алгоритму Евклида : НОД(4,7) = 1

  • Выразим число 1 через коэффициенты а = 4 и b =7, используя теорему о линейном разложении НОД:

НОД ( а, b ) = au + bv .

  • Получим: 1 = 4 ∙ 2 + 7 ∙ (-1) u = 2, v = -1

  • Частное решение уравнения : х 0 = 2 ∙ 16 = 32,

у 0 = -1 ∙ 16 = -16

Метод перебора  Решить уравнение 7 х + 12 у = 100  7х + 12у = 100 7х = 100 – 12у 100 – 12у кратно 7       Частное решение уравнения : х 0 = 4, у 0 = 6   у 100-12у 0 х 0 1 2 88 3 76 64 4 5 52 6 40 7 28 16 4 8 4

Метод перебора

Решить уравнение 7 х + 12 у = 100

  • 7х + 12у = 100
  • 7х = 100 – 12у
  • 100 – 12у кратно 7

Частное решение уравнения : х 0 = 4, у 0 = 6

у

100-12у

0

х

0

1

2

88

3

76

64

4

5

52

6

40

7

28

16

4

8

4

Метод спуска: 3х+8у=60  Выразим переменную х  через у      Выразим переменную х  через t  Ответ:   Проверка:

Метод спуска: 3х+8у=60

Выразим

переменную х

через у

Выразим

переменную х

через t

Ответ:

Проверка:

Метод рассмотрения остатков от деления Решить в целых числах уравнение 3х – 4у = 1 3 х = 4 у + 1 Левая часть уравнения делится на 3, значит и правая должна делиться на 3. При делении на 3 могут получиться остатки 0, 1, и 2. Рассмотрим 3 случая.   1 y = 3p 2 3 x = 4 ∙ 3p + 1 = 12 p + 1 3 y = 3p + 1  Не делится на 3 3 x = 4 ∙ (3p + 1) +1 = 12 p + 3 y = 3p + 2  Не делится на 3 3 x = 4 ∙ (3p + 2) +1 = 12 p + 9 3 x = 3 (4 p + 3) x = 4 p + 3 Ответ: Делится на 3  x = 4 p + 3 ; y = 3p + 2

Метод рассмотрения остатков от деления

  • Решить в целых числах уравнение 3х – 4у = 1
  • 3 х = 4 у + 1
  • Левая часть уравнения делится на 3, значит и правая должна делиться на 3. При делении на 3 могут получиться остатки 0, 1, и 2.
  • Рассмотрим 3 случая.

1

y = 3p

2

3 x = 4 ∙ 3p + 1 = 12 p + 1

3

y = 3p + 1

Не делится на 3

3 x = 4 ∙ (3p + 1) +1 = 12 p + 3

y = 3p + 2

Не делится на 3

3 x = 4 ∙ (3p + 2) +1 = 12 p + 9

3 x = 3 (4 p + 3)

x = 4 p + 3

Ответ:

Делится на 3

x = 4 p + 3 ; y = 3p + 2

Возможности теории ЛДУ  Найти все целочисленные решения уравнения  х 2 + 5y 2 + 34z 2 + 2ху - 10xz - 22уz =0

Возможности теории ЛДУ Найти все целочисленные решения уравнения х 2 + 5y 2 + 34z 2 + 2ху - 10xz - 22уz =0

Что дала мне работа над проектом? Получил представление о работе над исследовательским проектом. Познакомился с историей развития диофантовых уравнений и биографией Диофанта. Изучил методы решения ЛДУ с двумя и тремя неизвестными. решил группу задач, которые носят практический характер, а также встречаются на олимпиадах, экзаменах за курс основной школы Приобрел навыки решения нестандартных задач.   Думаю, что в последующем я продолжу изучение диофантовых уравнений второй степени и методов их решения.

Что дала мне работа над проектом?

  • Получил представление о работе над исследовательским проектом.
  • Познакомился с историей развития диофантовых уравнений и биографией Диофанта.
  • Изучил методы решения ЛДУ с двумя и тремя неизвестными.
  • решил группу задач, которые носят практический характер, а также встречаются на олимпиадах, экзаменах за курс основной школы
  • Приобрел навыки решения нестандартных задач.

Думаю, что в последующем я продолжу изучение диофантовых уравнений второй степени и методов их решения.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

  • Математика в понятиях, определениях и терминах. Ч.1. Пособие для учителей. Под ред. Л.В.Сабинина. М., «Просвещение», 1978. -320 с. (Библиотека учителя математики.) На обороте тит.л.авт.: О.В.Мантуров, Ю.К.Солнцев, Ю.И.Сорокин, Н.Г.Федин.
  • Нагибин Ф.Ф., Канин Е.С. Математическая шкатулка: Пособие для учащихся. – 4-е изд., перераб. и доп. - М.: Просвещение, 1984. – 160с., ил.
  • Н.П.Тучнин. Как задать вопрос? (О математическом творчестве школьников): Книга для учащихся. – М.: Просвещение, 1993. – 192с., ил.
  • С.Н.Олехник, Ю.В.Нестеренко, М.К.Потапов Старинные занимательные задачи. –М.: Дрофа, 2002. -176с., ил.
  • Я.И.Перельман. Занимательная алгебра. – М.: Наука, 1975г. – 200с., ил.
  • Электорнный ресурс: http :// www.yugzone.ru /x/ diofant-i-diofantovy-uravneniya / И.Г.Башмакова «Диофант и диофантовы уравнения».
  • Электорнный ресурс: http :// www.goldenmuseum.com /1612Hilbert_rus.html 10-я проблема Гильберта: история математического открытия (Диофант, Ферма, Гильберт, Джулия Робинзон, Николай Воробьев, Юрий Матиясевич).
  • Электорнный ресурс: http://ru.wikipedia.org/wiki/ Диофантовы уравнения.
  • Электорнный ресурс: http :// revolution.allbest.ru / mathematics /d00013924.html Белов Денис Владимирович Линейные диофантовы уравнения.
  • Электорнный ресурс: http :// revolution.allbest.ru / mathematics /d00063111.html Линейные диофантовы уравнении
  • Электорнный ресурс: http ://portfolio.1september.ru/work.php?id=570768 Зюрюкина Ольга. Неопределенные уравнения в целых числах или диофантовы уравнения.
  • Электорнный ресурс: http ://portfolio.1september.ru/work.php?id=561773 Арапов Александр. Диофант и его уравнения.
  • Электорнный ресурс: http :// ru.wikipedia.org / wiki / Алгоритм Евклида.