Практическое применение диофантовых уравнений в криптографии (4 видео)

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

Учебный год: 2009 / 2010

Материалы работы: 580318.zip * (23 кБ)

Содержание

Описание работы:
Исследовательская работа по математике по теме: “Диофантовы уравнения, типы и способы решения»
Основая часть.
1.Историческая справка.
3. Диофантовы уравнения в заданиях С5 ЕГЭ.
4.Практическое применение теории диофантовых уравнений.
Заключение.
Исследовательская работа ученицы 10 класса Кугультиновой Даяны по математике на тему : «Диафантовы уравнения»
🔍 Видео

Описание работы:

Самые разные задачи практического содержания часто приводят к уравнениям, в которых неизвестные по своему смыслу могут принимать только целочисленные значения. Уравнения в целых числах рассматривались ещё в глубокой древности. Особенно много ими занимался александрийский математик Диофант, имя которого и носят уравнения в целых числах. В данной работе разобраны примеры применения этих уравнений в разных жизненных ситуациях.

Видео:Классический способ решения Диофантовых уравнений ➜ Решите уравнение в целых числах ➜ 13x-7y=6Скачать

Исследовательская работа по математике по теме: “Диофантовы уравнения, типы и способы решения»

Международная научно-практическая конференция

«Первые шаги в науку»

Исследовательская работа по математике по теме:

“Диофантовы уравнения, типы и способы решения»

Предметная область: математика

Работу выполнила:Хомякова Ольга, ученица 10 класса

Учитель:, учитель математики

МБОУ средняя школа №4 с углубленным изучением отдельных предметов

2.Виды диофантовых уравнений и их классификация

3. Диофантовые уравнения в части С ЕГЭ-13

4. Практическое применение теории диофантовых ур-ний -16

В школьном курсе математики диофантовы уравнения практически не изучаются, но, например, в заданиях группы С6 в ЕГЭ встречаются уравнения 2-ой степени. Также с этими заданиями я сталкивалась в математических олимпиадах. Я заинтересовалась этой темой для того, чтобы успешно сдать Единый Государственный Экзамен и принимать участие в олимпиадах и конкурсах. Помимо этого, меня заинтересовала практическая направленность области этой темы.

Предметная областью моего исследования является математика.

Объект работы — диофантовы уравнения, типы и способы их решения.

1. Повысить уровень математической культуры ;

2. Развить в себе навыки исследовательской деятельности в области математики;

3. Научиться самой и научить других решать диофантовы уравнения эффективными методами;

4. Применять эти методы решения к задачам из повседневной жизни человека, а также к задачам, предлагаемым на вступительных экзаменах в ВУЗы и в олимпиадных заданиях;

5. Классифицировать методы решений дифференциальных уравнений;

6. Составить сборник задач с решениями в помощь ученикам нашей школы.

1. изучить исторические корни ;

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

3. исследовать методы решения задач, приводимых к уравнениям первой степени с двумя переменными, выбрав самые удобные и простые;

4. научиться решать задачи из повседневной жизни, вступительных экзаменов в ВУЗы экономического направления и олимпиадных заданий, применив изученные ранее методы;

5. разработать методическое пособие для всех интересующихся (подобрать или самим составить задачи с экономическим содержанием, приводящие к решению уравнений с двумя переменными).

Методы исследования : анализ, синтез, сравнение, противопоставление, ранжирование, прогнозирование, наблюдение.

Гипотеза: изучив типы, классифицировав диофантовы уравнения по способам решения можно успешно справиться с решением текстовых задач, задач с практическим содержанием и с частью заданий С6 ЕГЭ.

1. Изучение истории появления диофантовых уравнений, основной литературы по этой теме;

2. Изучение способов и методов решения диофантовых уравнений;

3. Попытка их классификации ;

4. Поиск практической значимости данной темы.

Видео:Как решать Диофантовы уравнения ★ 9x+13y=-1 ★ Решите уравнение в целых числахСкачать

Основая часть.

Видео:РЕШАЕМ ДИОФАНТОВОЕ УРАВНЕНИЕ | ПРОСТЫМИ СЛОВАМИСкачать

1.Историческая справка.

Диофант( вероятно 3 в. н. э. – древнегреческий математик из Александрии)

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

Эти уравнения названы по имени Диофанта ( вероятно 3 в. н. э. – древнегреческий математик из Александрии), изучавшего такие уравнения.

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

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

Диофантовы уравнения впервые обстоятельно исследовались в книге Диофанта “Арифметика”. Такие уравнения имеют некоторые особенности:

1. Они сводятся к уравнениям или системам уравнений с целочисленными коэффициентами.

2. Требуется найти только целые, часто натуральные решения.

2. Определение, виды диофантовых уравнений и способы их решений.

Итак, диофантовым уравнением для целочисленных переменных х 1 , х 2 , …, х n называется уравнение, которое может быть приведено к виду

Где Р — некоторый многочлен от указанных переменных с целыми коэффициентами.

Простейшим диофантовым уравнением является уравнение вида ax + by = c , где a и b – целые взаимно простые числа. Такое диофантово уравнение имеет бесконечное число решений: если x 0 и y 0 – одно решение, то числа x = x 0 + bn и y = y 0 — an ( где n — любое целое число ) также будут решениями, которыми исчерпывается вся совокупность решений.

Виды диофантовых уравнений:

Итак, я предлагаю рассмотреть решение следующего уравнения:

Так как 8 и 9 взаимно простые числа, т. е. наибольший общий делитель 8 и 9 равен 1 то решение существует. Одно из решений найдем подбором:

x 0 =2, y 0 =3. Остальные решения вычисляются по формулам:

x = x 0 + bn

Если наибольший общий делитель d коэффициентов а и b больше 1, а свободный член с не делится на d , то уравнение ах + by = c не имеет решений в целых числах.

А теперь рассмотрим линейное диофантово уравнение, которое не имеет целых решений:

Для доказательства того, что это уравнение не имеет целых решений, необходимо вынести за скобки общий множитель 5, получим 5( x +7 y )=17 . Тогда левая часть уравнения делится на 5, а правая часть на 5 не делится. Значит, уравнение не имеет решений в целых числах.

Любое уравнение ах + by = с , где НОД(а, b ) = 1, имеет хотя бы одно решение в целых числах.

К диофантовому уравнению приводит и такая задача:

На покупку нескольких открыток по 11 рублей и конвертов по 13 рублей потратили всего 61 рубль. Сколько купили открыток?

Давайте обозначим число открыток через х, а число конвертов через y , то задача сводится к уравнению 11 x +13 y =61 . Очевидно, что по условию задачи здесь пригодны лишь целые положительные числа. Методом подбора найдем такие числа. Данное уравнение имеет только одно такое решение: x =2, y =3 .

Еще в Древнем Вавилоне родилась задача о построении прямоугольного треугольника с попарно соизмеримыми сторонами. Соизмеримость сторон означает, что найдется такой масштаб, в котором катеты и гипотенуза будут выражаться натуральными числами x и y , но тогда:

Таким образом, вавилонская задача сводится к задаче построения всех троек натуральных чисел x , y , z удовлетворяющих предыдущему уравнению. Пифагорейцы нашли способ построения всех его решений. Но, возможно, этот способ был найден еще раньше в Вавилоне и Индии. Так или иначе, решения ( x , y , z ) уравнения x ^2+ y ^2= z ^2 принято называть пифагоровыми тройками: x =2 n +1; y =2 n ( n +1) ; z =2 n ^2+2 n +1 , n принадлежит Z . Примеры пифагорейских троек: 3, 4, 5; 6, 8, 10; 5, 12, 13.

Однако эти формулы не дают возможности найти все пифагорейские тройки чисел, имеющие выбранное исходное число. Формулы Пифагора и Платона и их различные модификации дают только частные решения. Приведем еще примеры пифагорейских троек чисел, которые нельзя получить по указанным формулам: 72, 65, 97; 72, 320, 328.

Эти и другие пифагорейские тройки чисел дает вавилонская клинописная табличка, относимая к эпохе гг. до н. э. Метод вавилонян дает возможность найти все пифагорейские тройки, содержащие выбранные исходные числа.

Известный в теории диофантовых уравнений является проблема Ферма ( Пьер Ферма ( ) – французский математик). Эта проблема носит название великой теоремы Ферма.

Она была сформулирована Ферма примерно в 1630 году на полях книги Диофанта “Арифметика”. Общее доказательство получил английский математик Уайлс в 1995 году.

2уравнения второй степени:

Я предлагаю вам решить 4 уравнения:

Итак, попробуем найти решение для первого уравнения:

Так как число 11 имеет делители только 1 и 11, то возможны следующие сочетания сомножителей:

1. x =1,

Тогда x=1, y=10.

Тогда x=11, y= -10

Тогда x= -1, y= -10

Тогда x= -11, y= 10

Ответ запишем в следующем виде: (1;10), (11;-10), (-1;-10), (-11;10).

Задачу №2 я предлагаю решить аналогичным способом, при помощи 4 систем.

1. х=2,

Тогда х=2, у=1/3 (т. е. система не имеет решения в целых числах).

2. х=1,

Тогда х=1, у=-1/3 (т. е. система не имеет решения в целых числах).

Тогда х=-1, у=1/3 (т. е. система не имеет решения в целых числах).

Тогда х=-2, у=-1/3 (т. е. система не имеет решения в целых числах).

Из этих пар чисел видно, что уравнение не имеет решений в целых числах.

Задачу № 3 тоже можно решить при помощи 4 систем. Решив системы, получим следующие пары чисел: ( 0;-1), (0;1), ( y =4/5), ( y = -4/5)

Последние две системы не имеют целых решений, следовательно, ответ: (0;-1),(0;1).

Последнее уравнение не похоже на 3 предыдущих.

Преобразуем заданное уравнение (вынесем за скобки y и вычтем и прибавим число 3):

В результате преобразований получаем уравнение:

Так как число 2 может быть представлено 4 способами в виде произведения целых чисел 2= (-2) * (-1); 2=( -1) * ( -2); 2=1 * 2; 2= 2*1, то возможны четыре системы. Из них получаем четыре пары чисел (1; -2), (2; -3), ( 4;1), (5;0). Ответом этого уравнения будут являться все 4 пары.

Запишем данное уравнение в виде (3 x – y ) * (3 x + y )=14 . Так как число 14 с учетом порядка следования множителей может быть представлено в виде произведения целых чисел следующим образом: 14=( -2) * (-7); 14=( -7) *(-2); 14=( -1) * ; 14= (-14) * (-1); 14= 2 * 7; 14= 7 * 2; 14= 1* 14; 14= 14* 1, то будет 8 случаев.

Решив все 8 систем, мы получаем дробные значения, а значит, что это уравнение не имеет решений в целых числах.

Разложим левую часть заданного уравнения на линейные множители: Уравнение примет вид: (3 x + 2 y )( x + y )=7

Так как 7 число простое, то оно равно произведению двух целых чисел в четырех случаях. Решив все 4 системы, получим пары чисел (-5;4), (5; -4), ( -13;20), ( 13;-20). Эти числа и будут ответом.

x^2 + y^2 – 2x + 4y=-5

В левой части уравнения выделим полный квадрат:

x^2 – 2x + 1 + y^2 + 4y + 4=0

Сумма квадратов равна 0 лишь в одном случае

( x – 1) ^ 2=0 ,

Решив систему, получим, что x = 1, y = -2

x^2 – 6x + y^2 + 6y + 18=0

Докажем, что это уравнение имеет единственное целочисленное решение.

В левой части уравнения выделим полные квадраты :

( x – 3 )^2 + ( y + 3 )^2=0

Данное уравнение имеет решение, когда

x – 3=0,

Теперь я предлагаю рассмотреть графический метод решения диофантовых уравнений.

Алгоритм построения графика уравнения ах + by + с = 0:

1. Придать переменной х конкретное значение х= х1; найти из уравнения ах1 + by + c = 0 соответствующее значение y = y 1.

2. Придать переменной х другое значение х=х2; найти из уравнения ах2 + by + c = 0 соответствующее значение y = y 2.

3. Построить на координатной плоскости х Oy две точки (х1;у1) и (х2;у2).

4. Провести через эти две точки прямую – она и будет графиком уравнения ах + by + с = 0.

Так, например, уравнение 5 x + 7 y =17 можно решить графическим методом, изобразив прямую 5 x + 7 y = 17, и определив на этой прямой точки, обе координаты которых будут в данном случае натуральными числами.

Целые решения: (2 ;1),( 9;-4), ( 16;-9),(-5;6),(-12;11)

Видео:Математика. Линейные диофантовы уравнения с двумя неизвестными. Центр онлайн-обучения «Фоксфорд»Скачать

3. Диофантовы уравнения в заданиях С5 ЕГЭ.

Необходимо найти все пары (х, у) целых чисел, удовлетворяющих системе неравенств:

x ^2 + y ^2 x – 20 y – 166, (1)

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

Получаем два случая:

1) Неравенство (1) путем выделения полных квадратов сводится к условию

Т. е. описывает внутренность круга с центром А(9; -10) и радиусом R 1=√15 .

2) Неравенство (2) сводится к виду

Т. е. описывает внутренность круга с центром В(16; -6) и радиусом R 2=√21 .

Единственной точкой, принадлежащей одновременно двум кругам, будет точка М( 12; -8). Это выясняется подстановкой в систему числовых значений координат всех узлов квадратной сетки, соседних с точкой М.

Найти наименьшее значение суммы тогда в области

Решением данного неравенства является область, ограниченная окружностью радиусом 2 с центром в точке O (1;-2)

Пусть искомое значение , тогда

Угловой коэффициент равен -1, – значение координаты y при x =0.

Треугольник ABC прямоугольный. Чтобы найти c , достаточно найти ординату точки B . Для этого найдем координаты точек A и B . Зная, что точки лежат на прямой с точкой O (1;-2), т. е. на прямой , и на окружности , решим систему

A ( ) C ( ; )

Согласно рисунку ;

B ( ; )

Ответ:

Видео:Линейные диофантовы уравненияСкачать

4.Практическое применение теории диофантовых уравнений.

Неожиданно, лет 20-30 назад, было осознано, что эту чисто абстрактную теорию можно использовать для построения алгоритмов, которые нужны для криптографии, чтобы зашифровывать и безопасно передавать секретные сообщения, а также снимать и класть деньги в банкоматах и т. п. Теория эта оказалась востребована на практике. Яркий пример: в девяностые годы, когда математикам есть было нечего, многие уехали за границу, но многие и остались здесь, и некоторые математики из провинциальных институтов успешно сотрудничали с банками. Банкиры обратились к ним с просьбой помочь в переводе денег из дальних регионов в Москву. В России есть целая Академия криптографии и научно-исследовательские организации, которые используют такие разработки.

Знаменитый мост Золотые Ворота был построен с применением диофантовых уравнений.

Мост Золотые Ворота

Видео:Решите уравнение в целых числах 3x^2+5y^2=345 ✱ Диофантовы уравнения ✱ Как решать?Скачать

Заключение.

В процессе исследования типов диофантовых уравнений мне удалось их классифицировать по способам решения, выработать алгоритм решения некоторых распространенных видов этих уравнений, научиться решать текстовые задачи, успешно справляться с заданиями части С ЕГЭ, о чем свидетельствует диплом 2 степени на всероссийской дистанционной олимпиаде по математике на сайте «Инфоурок. Ру.»

Данная исследовательская работа дала мне возможность совершенствовать навыки работы с научно-популярной литературой и освоить программы графопостроители.

Говоря о практическом использовании полученных результатов нельзя не вспомнить слова Алексея Николаевича Крылова: «Рано или поздно всякая правильная математическая идея находит применение в том или ином деле».

Видео:ПЕРЕЧНЕВЫЕ ОЛИМПИАДЫ. Диофантовы уравненияСкачать

Исследовательская работа ученицы 10 класса Кугультиновой Даяны по математике на тему : «Диафантовы уравнения»

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Научно — практическая конференция «Первые шаги в науку»

Название работы: Диофантовы уравнения

Автор работы: Кугультинова Даяна Витальевна

Место выполнения работы: РК, Яшалтинский р-н, с. Яшалта,

МБОУ «Яшалтинская СОШ имени В. А. Панченко»

Руководитель : Точка И. Г. , учитель математики.

Диофант и его труды __________________________________________5

Что такое диофантовы уравнения ________________________________6

Решение уравнений 1-й степени _________________________________8

Решение уравнений 2-й степени ________________________________15

Решение уравнений с 3 неизвестными ___________________________17

Решение практических задач с помощью диофантовых уравнений __ 19

Список литературы ___________________________________________ 25

Обоснование выбора темы: Моя бабушка-библиотекарь, и как-то летом я помогала наводить порядок в сельской библиотеке и наткнулась на довольно старый справочник школьника по математике. Математика всегда была одним из моих любимых предметов, и, увидев такую древнюю книжонку, которая служила помощником при выполнении домашних заданий моим родителям, а может и бабушкам, дедушкам, мне стало жутко интересно, есть ли в ней что-то такое, чего мы не проходили в школе. Открыв справочник на первой попавшейся странице, я увидела тогда еще непонятный мне заголовок «Диофантовы уравнения». Когда я пролистала всю книжку, я поняла, что это единственная тема – мне незнакомая, о которой я ничего ранее не слышала. Тогда я решила опросить своих одноклассников, учеников физико-математического класса, слышали ли они что-то про эти загадочные уравнения. Оказалось, что никто из них ранее не слышал о таком. Я решила разобраться и узнать, что же такое знали советские школьники и что вряд ли узнает большая часть школьников 21 века.

Цели и задачи исследования:

1. Изучить материалы о творчестве Диофанта.

2. Ознакомиться с «диофантовым анализом».

3. Изучить способы решений неопределенных уравнений 1 степени.

4. Исследовать методы решений диофантовых уравнений 2 степени.

5. Ознакомиться с неопределенными уравнениями с 3 неизвестными.

6. Обозначить и обобщить вклад Диофанта в математику.

Новизна исследования: написание программы на языке программирования Pascal для решения диофантовых уравнений.

Практическая значимость — умение решать диофантовы уравнения может пригодиться в реальной жизни, например задачи на оптимизацию, которые неоднократно встречаются в ЕГЭ; также данное умение окажется как нельзя кстати при решении задач выходящих за рамки школьной программы, олимпиадных заданий.

Гипотеза: После проведения опроса среди одноклассников, я задумалась об актуальности этой темы, ведь задачи на оптимизацию, которых много в ЕГЭ, предполагают решение с помощью диофантовых уравнений; также в том пресловутом справочнике прозвучала мысль, что подход Диофанта к решению уравнений особенный, и мне хотелось бы поделиться умением решать диофантовы уравнения с другими. Первое, с чего началось мое «дознание», было изучение Википедии по интересующему вопросу. При первом просмотре теории я многого не поняла, и мой интерес разгорелся еще больше. Я уверена, что если школьникам 50 лет назад это было интересно и доступно, то и для нас это должно быть точно так же. Я предполагаю, что элементы высшей математики могут быть доступны и интересны ученикам средней школы.

Объект исследования : диофантовы уравнения

Предмет исследования: способы решения диофантовых уравнения.

Методы исследования : анализ, синтез, сравнение, аналогия.

Глава I . Диофант и его труды.

Диофант ( ок. 325 г . – ок. 409 г .) — знаменитый древнегреческий математик , автор трактата «Арифметика» в 13 книгах, посвященного главным образом исследованию неопределенных уравнений, которые впоследствии стали называться диофантовыми.
О жизни ученого нет почти никаких сведений ; даже даты его рождения и смерти не вполне достоверны . Лишь исходя из эпитафии на надгробном камне, которая показывает нам, что Диофант был математиком до мозга костей, мы можем узнать нечто достоверное – количество прожитых им лет:

Прах Диофанта гробница покоит; дивись ей — и камень.

Мудрым искусством его скажет усопшего век.

Волей богов шестую часть жизни он прожил ребенком.

И половину шестой встретил с пушком на щеках.

Только минула седьмая. С подругой он обручился.

С нею, пять лет проведя, сына дождался мудрец;

Только полжизни отцовской, возлюбленный сын его прожил.

Отнят он был у отца ранней могилой своей.

Дважды два года родитель оплакивал тяжкое горе,

Тут и увидел предел жизни печальной своей.

(Перевод Боброва С.Н.)

Составим уравнение: _{, где х – продолжительность жизни.}

Отсюда нетрудно подсчитать, что Диофант прожил 84 года. Однако для этого вовсе не нужно владеть искусством Диофанта, достаточно уметь решать уравнение 1 степени с одним неизвестным.

Но самое интересное – это творчество Диофанта. До нас дошло 6 книг из 13, которые были объединены в «Арифметику», сборник задач (их всего 189), каждая из которых снабжена решением (или несколькими способами решения) и необходимыми пояснениями. Поэтому с первого взгляда кажется, что она не является теоретическим произведением. Однако при внимательном чтении видно, что задачи тщательно подобраны и служат для иллюстрации вполне определённых, строго продуманных методов. «Арифметика», несомненно, явилась результатом многочисленных исследований, мы можем только изумляться богатству и красоте её методов и результатов.

Заметим, что история методов Диофанта растягивается ещё на несколько сотен лет, переплетаясь с развитием теории алгебраических функций и алгебраической геометрии. Развитие идей Диофанта можно проследить вплоть до работ Анри Пуанкаре и Андре Вейля. Поэтому-то история диофантова анализа особенно интересна.

Глава II . Что такое диофантовы уравнения.

Проследим, как осуществлялось развитие и происходило становление теории диофантовых уравнений. Если обратиться к истории, то можно заметить, что конкретные задачи такого рода были решены еще в Древнем Вавилоне около 4 тысяч лет тому назад. Диофант, который жил около 2 тысяч лет тому назад, в своей книге «Арифметика» решил большое число таких и более сложных уравнений в целых числах, и описал общие методы их решения. Комментировать Диофанта начали ещё в древности. Разбору его книг были посвящены труды знаменитой Гипатии, дочери Теона Александрийского. Свое новое «рождение» идеи Диофанта получили в Константинополе, а также на арабском Востоке, откуда проникли в Европу. В 1572 году в «Алгебре» Рафаэля Бомбелли, профессора университета в Болонье, вдруг появляются 143 задачи из «Арифметики» Диофанта. Методы Диофанта обрели новую жизнь только в произведениях двух крупнейших математиков Франции XVI–XVII веков — Франсуа Виета и Пьера Ферма. Первый этап развития учения о неопределённых уравнениях второго и третьего порядков, начало которому положил Диофант, нашёл своё завершение в работах Леонарда Эйлера. Диофантовы уравнения можно разделить на неопределенные уравнения 1-й степени, 2-й степени, 3-й степени и etc ; также можно проклассифицировать неопределенные уравнения по количеству переменных, обычно рассматриваются уравнения с 2, 3 переменными, и все же сформулируем общее определение понятия «диофантово уравнение»: линейным диофантовым уравнением называется уравнение с несколькими неизвестными вида a ₁ x ₁ + a ₂ x ₂ +. + a _n x _n = c , где коэффициенты a ₁ , a ₂ , . , a _n , c — целые числа, а неизвестные x ₁ , x ₂ , . , x _n являются целыми или рациональными числами. К решению подобных уравнений сводятся разнообразные текстовые задачи, в которых неизвестные величины выражают количество предметов того или иного рода и поэтому являются натуральными (или неотрицательными целыми) числами. Каждая конкретная задача в целых числах может решаться с помощью разных методов. В настоящее время задача решения неопределенных уравнений формулируется так: пусть дано m многочленов от n переменных, m n , f ₁ ( x ₁ , x ₂ , . , x _n ), . f _m ( x ₁ , x ₂ , . , x _n ), с коэффициентами из некоторого поля k . Требуется найти множество M ( k ) всех рациональных решений системы

и определить его алгебраическую структуру. При этом решение ( x ₁ (0) , . , x _n (0) ) называется рациональным , если все x _i (0) ∈ k .

Ограничимся рассмотрением только таких задач Диофанта, которые сводятся к одному уравнению с двумя или тремя неизвестными.

Глава III . Решение уравнений 1-й степени.

Десятая проблема Гильберта — одна из 23 неразрешимых задач, которые Давид Гильберт предложил 8 августа 1900 года в Париже на II Международном конгрессе математиков. Она состоит в нахождении универсального метода определения разрешимости произвольного алгебраического диофантова уравнения. Доказательство алгоритмической неразрешимости этой задачи заняло около двадцати лет и было завершено Юрием Матиясевичем , советским и российским ученым в возрасте 22 лет, в 1970 году.

При исследовании линейных диофантовых уравнений необходимо ответить на следующие вопросы: 1) имеет ли уравнение целочисленные решения;

2) конечно или бесконечно множество его целочисленных решений;

3) решить уравнение на множестве целых чисел, т. е. найти все его целочисленные решения;

4) решить уравнение на множестве целых положительных чисел;

5) решить уравнение на множестве рациональных чисел.

В настоящее время известны следующие способы решения линейных диофантовых уравнений, а именно:

-способ перебора вариантов;

-использование алгоритма Евклида;

-метод цепных дробей.

Попробуем и мы разобраться со способами решения диофантовых уравнений 1-й степени: уравнение вида ax + by = c является одним из простейших неопределенных уравнений 1-ой степени, но не смотря на это, решить такое уравнение весьма непросто. Можно выделить два основных метода решения неопределенных уравнений вида ax + by = c : способ перебора и метод «спуска».

1. Способ перебора вариантов. Метод перебора включает в себя перебор чисел вместо переменных х и у, с учетом, что уравнение при определенном подборе чисел обращается в верное равенство.

Рассмотрим уравнение: 1,5х +2у = 50.

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

Решение: Помножим обе части уравнения на 2, чтобы избавиться от дробных чисел, получим: 3х + 4у = 100.

Далее воспользуемся методом перебора (учитывая, что х и у N ):

Таким образом, подставляя вместо х числа, удовлетворяющие равенству, получили некоторые значения у (причем х и у N ).

2. Метод «спуска». Перебор вариантов при решении уравнения в целых числах часто оказывается весьма трудоемким. Поэтому рассмотрим еще один старинный прием – метод «спуска» (или метод рассеивания). Таким методом решения неопределенных (диофантовых) уравнений 1-ой степени с целыми коэффициентами занимались еще в Древней Индии. Этим способом и в наше время решают такие уравнения.

Но всегда ли возможно решить уравнение вида ax + by = c в целых числах? Можно рассмотреть три случая:

1). Если свободный член с неопределенного уравнения ax + by = c не делится на НОД ( a , b ), то уравнение не имеет целых корней.

2). Если коэффициенты a , b являются взаимно простыми числами, то уравнение имеет, по крайней мере, одно целое решение.

3). Неопределенное уравнение ax + by = c , в котором a , b – взаимно простые числа допускает бесконечное множество целых решений. Все эти решения задаются формулами: x = λ + bt , y = β – at , где ( λ , β) – некоторые решения уравнения, at — принадлежит множеству целых чисел.

Рассмотрим уравнение: 19х – 7у = 100 (1).

Требуется найти все целые решения уравнения.

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

Теперь нам нужно выяснить, при каких целых значениях х соответствующие значения у также являются целыми числами. То есть, выделив целую часть, запишем уравнение (2) следующим образом: (3). Из уравнения (3) следует, что у при целом значении х будет иметь целое значение только в том случае, если выражение также будет иметь целое значение, заменим это выражение на z ( z ).

Значит (4), сведем к решению уравнения (4) с двумя неизвестными х и z , тогда его можно записать так: 5 x – 7 z = 100 (5).

Продолжая тем же способом, из уравнения (5) получим: (6).

Получается, неизвестное х принимает целое значение при целом z тогда, когда будет принимать целое значение. Пусть это выражение равно p ( p ), получим:

Аналогично (4) и (7) должно быть целым числом, подставим вместо этого выражения q ( q ) , получаем: (10),

Из уравнения (11) получаем: (12).

Заметим, что при любых значениях 2 q , p будет принимать целые значения.

Из равенств (3), (6), (9), (12) при помощи последовательных подстановок находим следующие выражения для неизвестных х и у уравнения (1):

Таким образом, формулы: , при q = 0, , , … дают все целые решения уравнения (1).

Далее приведены примеры таких решений:

Мы рассмотрели наиболее распространенные методы решения диофантовых уравнений – способ перебора вариантов и метод «спуска», но не стоит забывать и о других, менее популярных, но не менее интересных способах.

3. Использование алгоритма Евклида.

Евклид, великий древнегреческий ученый, оказывается, был не только основоположником геометрии как науки, он отлично разбирался и в теории чисел и внес свой вклад в ее развитие. Алгоритм Евклида можно назвать одним из старейших алгоритмов, применяемых и в наше время, ведь его первое описание находится в главном детище Евклида – в «Началах» (ок. 300 лет до н.э.). Основная задача алгоритма Евклида заключается в том, чтобы найти НОД 2 чисел, что бывает крайне затруднительно, когда числа большие, сложные.

Алгоритм решения неопределенного уравнения с помощью алгоритма Евклида:

1. Найти наибольший общий делитель чисел a и b , если (a,b)= d >1 и с не делится на d , то уравнение целых решений не имеет;

если (a,b)= d >1 и с делится на d , то уравнение имеет целые решения;

4. Составить общую формулу целых решений данного уравнения x= x ₀ c + bt , y = y ₀ c — at , где х ₀ , у ₀ – целое решение уравнения ax+ by =1, t – любое целое число. После изучения самого алгоритма Евклида, попробуем решить уравнение 5х+8у=29: