Решение уравнений в целых числах курсовая

Решение уравнений в целых числах курсовая

Объектом исследования является один из наиболее интересных разделов теории чисел – решение уравнений в целых числах.

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

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

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

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

Для достижения поставленной цели необходимо было решить следующие задачи:

изучить учебную и справочную литературу, проанализировать олимпиадные материалы, а также материалы профильного ЕГЭ по математике;

собрать теоретический материал по способам решения уравнений;

разобрать алгоритмы решения уравнений данного вида;

рассмотреть примеры решения уравнений с применением данных способов;

составить тренировочные задания.

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

Теоретический анализ и обобщение сведений научной литературы об уравнениях в целых числах.

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

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

Глава 1. Знакомство с уравнениями в целых числах и их классификация по методам решения

Уравнения в целых числах – это алгебраические уравнения с двумя или более неизвестными переменными и целыми коэффициентами. Решениями такого уравнения являются все целочисленные (иногда натуральные или рациональные) наборы значений неизвестных переменных, удовлетворяющих этому уравнению. Такие уравнения ещё называют диофантовыми, в честь древнегреческого математика Диофанта Александрийского, который исследовал некоторые типы таких уравнений ещё до нашей эры.

Примером диофантового уравнения является уравнение вида

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

Современной постановкой диофантовых задач мы обязаны французскому математику Ферма. Именно он поставил перед европейскими математиками вопрос о решении неопределённых уравнений только в целых числах. Наиболее известное уравнение в целых числах – великая теорема Ферма: уравнение

не имеет ненулевых рациональных решений для всех натуральных n > 2.

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

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

Для решения уравнений в целых и натуральных числах можно условно выделить множество методов, наиболее часто используемые – следующие методы:

метод, основанный на алгоритме Евклида;

цепной (непрерывной) дроби;

разложения на множители;

метод, основанный на выражении одной переменной через другую и выделении целой части дроби;

решение уравнений в целых числах как квадратных (или иных) относительно какой-либо переменной;

метод, основанный на выделении полного квадрата.

Глава 2. Линейные уравнения

2.1. Метод перебора вариантов

В способе перебора вариантов необходимо учитывать признаки делимости чисел, рассмотреть все возможные варианты равенства конечного перебора.

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

Задача 1. У нескольких велосипедов 26 колес. Сколько из этих велосипедов трёхколесных и сколько двухколёсных?

Решение: составляем уравнение , в котором х – число трёхколесных, у – число двухколёсных велосипедов.

х и у – целые неотрицательные числа, значит 27 – 3х должно делиться на 2 без остатка.

Учебно – исследовательская работа «Решение уравнений в целых числах»

XII конкурс учебно-исследовательских и проектных работ учащихся

«Школьники города — науке XXI века»

МОУ «Средняя общеобразовательная школа №8» г. о. Саранск

Учебно – исследовательская работа

«Решение уравнений в целых числах»

Выполнил: учащийся 10А класса руководитель: ,

I. Биография Диофанта. 10-я проблема Гильберта…………………..стр.3

II. Решение уравнений в целых числах

1. Применение теории делимости к решению неопределенных

уравнений в целых числах. стр.5

2.Метод полного перебора всех возможных значений переменных,

3. Решение уравнений методом разложения на множители………. стр.8

4. Выражение одной переменной через другую и выделение

5. Методы, основанные на выделении полного квадрата………. стр.9

6. Решение уравнений с двумя переменными как квадратных

относительно одной из переменных…………………………………..стр.9

7. Оценка выражений, входящих в уравнение………………………..стр.10

8. Примеры уравнений второй степени с тремя неизвестными……..стр.10

III. Решение уравнений в целых числах из Межрегиональной

Заочной математической олимпиады для школьников

(Всероссийская школа математики и физики «Авангард»)…………стр.11

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

V. Решение уравнений в целых числах из Единого государственного

VI. Заключение. стр.19

VII. Литература. стр.20

В математике следует помнить не формулы, а процессы мышления.

Решение в целых числах алгебраических уравнений с целыми коэффициентами более чем с одним неизвестным представляет собой одну из труднейших и древнейших математических задач. Этими задачами много занимались самые выдающиеся математики древности, например, греческий математик Пифагор (VI век до н. э.), александрийский математик Диофант (III век н. э.), П. Ферма(XVII в.), Л. Эйлер(XVIII век), (XVIII век), П. Дирихле(XIX век), К. Гаусс(XIX век), П. Чебышев(XIX в.) и многие другие.

Решение уравнений в целых числах является важной задачей и для современной математики. Теоретический интерес уравнений в целых числах достаточно велик, так как эти уравнения тесно связаны со многими проблемами теории чисел, что и определило актуальность нашей работы «Решение уравнений в целых числах» Ещё в начальной школе на уроках математики перед нами часто ставили задачу выяснить, при каких допустимых значениях буквы обе части того или иного равенства принимают одинаковые числовые значения. На равенство в этом случае мы смотрели как на уравнение относительно указанной неизвестной величины. В восьмом классе мы познакомились с решением квадратных уравнений с одной переменной. Но, готовясь к олимпиадам, рассматривая контрольно — измерительные материалы Единого государственного экзамена встречаемся с заданиями, в которых предлагали уравнения с двумя переменными. Появилось желание узнать решаемы ли такие уравнения, и какие способы используются для их решения, все ли они имеют алгоритм решения и где применяются. Отсюда определена

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

Цели учебно — исследовательской работы:

– показать разнообразные способы решения диофантовых уравнений;

— повысить уровень математической культуры, прививая навыки самостоятельной исследовательской работы в математике.

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

— выполнить сопоставительно – аналитическую работу с контрольно – измерительными материалами ЕГЭ и заданий олимпиад разных лет.

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

Диофант (Dióphantos) представляет одну из занимательных загадок в истории математики. Мы не знаем, кем был Диофант, точные года его жизни, нам не известны его предшественники, которые работали бы в той же области, что и он.

На могиле Диофанта есть стихотворение-загадка, решая которую нетрудно подсчитать, что Диофант прожил 84 года. О времени жизни Диофанта мы можем судить по работам французского исследователя науки Поля Таннри, и это, вероятно, середина III в. н.э.

Наиболее интересным представляется творчество Диофанта. «Труды его подобны сверкающему огню среди полной непроницаемой тьмы». [Стройк] До нас дошло 7 книг из, возможно, 13, которые были объединены в «Арифметику». Стиль и содержание этих книг резко отличаются от классических античных сочинений по теории чисел и алгебре, образцы которых мы знаем по «Началам» Евклида, леммам из сочинений Архимеда и Аполлония. «Арифметика», несомненно, явилась результатом многочисленных исследований, многие из которых остались нам неизвестны. Мы можем только гадать о её корнях и изумляться богатству и красоте её методов и результатов.

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

Поэтому, обычно, произвольное неопределенное уравнение (но, как правило, все-таки с целыми коэффициентами) получает титул «диофантово», если хотят подчеркнуть, что его требуется решить в целых числах.

Неопределенные уравнения 1-й степени начали рассматриваться индусскими математиками позднее, примерно с V века. Некоторые такие уравнения с двумя и тремя неизвестными появились в связи с проблемами, возникшими в астрономии, например, при рассмотрении вопросов, связанных с определением периодического повторения небесных явлений.

Первое общее решение уравнения первой степени , где — целые числа, встречается у индийского мудреца Брахмагупты (ок. 625 г). Поэтому, строго говоря, нет оснований называть линейные неопределенные уравнения диофантовыми. Однако, исторически все же сложилось применять термин «диофантово», к любому уравнению, решаемому в целых числах.

В 1624 г. в публикуется книга французского математика Баше де Мезирьяка «Problẻmes plaisans et delectables que se font par les nombres». Баше де Мезирьяк для решения уравнения фактически применяет процесс, сводящийся к последовательному вычислению неполных частных и рассмотрению подходящих дробей.

После Баше де Мезирьяка в XVII и XVIII веках различные правила для решения неопределенного уравнения 1-й степени с двумя неизвестными давали Роль, Эйлер, Саундерсон и другие математики.

Цепные дроби к решению таких уравнений были применены Лагранжем, который, однако, замечает, что фактически это тот же способ, который был дан Баше де Мезирьяком и другими математиками, рассматривавшими неопределенные уравнения до него. Неопределенные уравнения 1-й степени стали записываться и решаться в форме сравнения значительно позже, начиная с Гаусса.

В августе 1900 г. в Париже состоялся II Международный конгресс математиков. 8 августа Д. Гильберт прочитал на нем доклад «Математические проблемы». Среди 23 проблем, решение которых (по мнению Д. Гильберта) совершенно необходимо было получить в наступающем XX в., десятую проблему он определил следующим образом:

«Пусть задано диофантово уравнение с произвольным числом неизвестных и рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых числах».

Гипотезу, что такого способа нет, первым выдвинул (с достаточным на то основанием) американский математик М. Дэвис в 1949 г. Доказательство этой гипотезы растянулось на 20 лет — последний шаг был сделан только в 1970 г. ленинградским математиком Юрием Владимировичем Матиясеевичем, на первом году аспирантуры он показал алгоритмическую неразрешимость 10 проблемы Гильберта. Он доказал, что общего способа быть не может, не существует единого алгоритма, позволяющего за конечное число шагов решать в целых числах произвольные диофантовы уравнения. Поэтому мы должны для каждого уравнения выбирать собственный метод решения и более чем 10 методов, в основе которых лежат определения и свойства делимости чисел.

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

II. Решение уравнений в целых числах.

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

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

Для решения в целых числах уравнения вида ах + by = c, где а, b, c – целые числа, отличные от нуля, приведем ряд теоретических положений, которые позволят установить правило решения. Эти положения основаны также на уже известных фактах теории делимости.

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

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

Найти линейное представление наибольшего общего делителя чисел 1232 и 1672.

1. Составим равенства алгоритма Евклида:

1672 = 1232 ∙1 + 440,

1232 = 440 ∙ 2 + 352,

440 = 352 ∙ 1 + 88,

352 = 88 ∙ 4, т. е. (1672,352) = 88.

2) Выразим 88 последовательно через неполные частные и остатки, используя полученные выше равенства, начиная с конца:

88 = ∙1 = (1∙2 + 1232∙2) = 1672∙∙4, т. е. 88 = 1672∙3 + 1232∙(-4).

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

Справедливость этой теоремы следует из теоремы 1. Таким образом, чтобы найти одно целое решение уравнения ах + bу = 1, если НОД (а, в) = 1, достаточно представить число 1 в виде линейной комбинации чисел а и в.

Найти целое решение уравнения 15х + 37у = 1.

2. 1 =∙2 =∙2) ∙2 = 15∙5 + 37∙(-2),

т. е. х= 5, у= -2 — решение данного уравнения.

Для доказательства теоремы достаточно предположить противное.

Найти целое решение уравнения 16х — 34у = 7.

(16,34)=2; 7 не делится на 2, уравнение целых решений не имеет.

Теорема 4. Если в уравнении ах + bу = с НОД(а, b) = d>1 и с d, то оно равносильно уравнению ах + b у = с, в котором НОД(а, b ) = 1.

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

Теорема 5. Если в уравнении ах + bу = с НОД(а, b) = 1, то все целые решения этого уравнения заключены в формулах:

х = хс + bt, у = yc—at, где х, y — целое решение уравнения ах + bу = 1,

t – любое целое число.

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

Приведенные теоремы позволяют установить следующее правило решения в целых числах уравнения ах+ bу = с НОД(а, b) = 1:

1) Находится целое решение уравнения ах + bу = 1 путем представления 1 как линейной комбинации чисел а и b (существуют и другие способы отыскания целых решений этого уравнения, например при использовании цепных дробей);

2) Составляется общая формула целых решений данного уравнения х = хс + bt, у = yc — at, где х, y — целое решение уравнения ах + bу = 1, t – любое целое число.

Придавая t определенные целые значения, можно получить частные решения данного уравнения: наименьшие по абсолютной величине, наименьшие положительные (если можно) и т. д.

Найти целые решения уравнения 407х — 2816у = 33.

1. Упрощаем данное уравнение, приводя его к виду 37х — 256у = 3.

2.Решаем уравнение 37х — 256у = 1.

1 =∙11 = ∙– 256 + 37∙6) = 256∙12 — 37∙83 =

т. е. х= -83, y= -12.

3. Общий вид всех целых решений данного уравнения:

Положив t = -1, получим х= 7, у= 1 и общие формулы решений примут вид: х = t, у = 1-37t.

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

Реферат по математике на тему: «Решение уравнений в целых числах»

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

Государственное бюджетное общеобразовательное учреждение

средняя общеобразовательная школа № 303

с углубленным изучением немецкого языка

и предметов художественно-эстетического цикла

имени Фридриха Шиллера

Фрунзенского района Санкт-Петербурга

Реферат по математике на тему:

ученицы 9Э класса

учитель математики высшей категории ,

педагог дополнительного образования

Соколова Светлана Николаевна

Введение

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

Тема «Решение уравнений с двумя переменными в целых числах» недостаточно полно изложена в действующих учебниках математики, а задачи по этой теме предлагаются как на олимпиадах, так и в заданиях на экзаменах. В данной работе выделены основные методы решений уравнений в натуральных и целых числах и приводится система тренировочных упражнений для закрепления каждого из рассмотренных методов.

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

Изучив разные способы решения квадратного уравнения с одной переменной на уроках, нам было интересно разобраться, а как решаются уравнения с двумя переменными. Такие задания встречаются на олимпиадах и в материалах ЕГЭ.

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

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

Цель: Освоить способ решения уравнений с двумя неизвестными первой и второй степени в целых числах.

Изучить учебную и справочную литературу;

Подобрать теоретический материал по способам решения уравнений;

Разобрать алгоритм решения уравнений данного вида;

Описать способы решения.

Рассмотреть ряд примеров с применением данного приема.

Решить уравнения с двумя переменными в целых числах из материалов ЕГЭ задания С6.

Объект исследования : Решение уравнений

Глава 1. Теория уравнений с двумя переменными в целых числах

1. Историческая справка. Диофант и история диофантовых уравнений

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

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

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

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

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

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

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

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

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

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

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

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

Задача-загадка сводится к составлению и решению уравнения:

Откуда х=84 — столько лет жил Диофант.

Из работ Диофанта самой важной является «Арифметика», из 13 книг которой только 6 сохранились до наших дней. Эти книги были открыты в Венеции в 1463г.

В сохранившихся книгах Диофанта содержится 189 задач с решениями. В первой изложены задачи, приводящиеся к определенным уравнениям первой и второй степени. Остальные же пять книг содержат в основном неопределенные уравнения. В этих уравнениях еще нет систематической теории неопределенных уравнений, методы решения меняются от случая к случаю. Диофант довольствуется каким-нибудь одним решением, целым или дробным, лишь бы оно было положительным. Наиболее известной, решенной Диофантом, является задача «о разложении на два квадрата». Ее эквивалентом является известная всем теорема Пифагора. Эта теорема была известна в Вавилонии, возможно ее знали и в Древнем Египте, но впервые она была доказана, в пифагорейской школе. Так называлась группа интересующихся математикой философов по имени основателя школы Пифагора (ок. 580-500г. до н.э.).

Жизнь и деятельность Диофанта протекала в Александрии, он собирал и решал известные и придумывал новые задачи. Позднее он объединил их в большом труде под названием «Арифметика». Из тринадцати книг, входивших в состав «Арифметики», только шесть сохранились до Средних веков и стали источником вдохновения для математиков эпохи Возрождения, в том числе и для Пьера де Ферма.

Пьер де Ферма родился 20 августа 1601 года на юго-западе Франции. Он не занимался профессионально математикой, но был одним из величайших в истории математики «любителем».

Изучая задачи и решения Диофанта, Ферма черпал в них вдохновение и занимался решением аналогичных и более интересных задач. Ферма записывал для себя лишь самое необходимое для того, чтобы убедиться в правильности полученного решения.

При чтении второй книги «Арифметики», Ферма наткнулся на целую серию наблюдений, задач и решений, связанных с теоремой Пифагора и пифагоровыми тройками. Например, Диофант рассматривал существование особых троек, образующих так называемые «хромые треугольники», у которых две более короткие стороны x и y отличаются по длине только на единицу (например, x = 20, y = 21, z = 29 и 20 2 + 21 2 = 29 2 ).

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

Ферма подверг уравнение Пифагора еще большему изменению, попробовав заменить степень 2 на целые числа бóльшие 3, и обнаружил, что найти решение в целых числах каждого из этих уравнений очень трудно. И Ферма доказал, что вообще не существует трех целых чисел x , y , z , которые удовлетворяли бы уравнению

На полях «Арифметики» Диофанта, рядом с задачей 8, Ферма оставил такое замечание: «Невозможно для куба быть записанным в виде суммы двух кубов, или для четвертой степени быть записанной в виде суммы двух четвертых степеней, или, в общем, для любого числа, которое есть степень больше двух, быть записанной в виде суммы двух таких же степеней. Я нашел поистине удивительное доказательство этого предложения, но поля здесь слишком узки для того, чтобы вместить его». Это замечание Ферма сделал в1637 году.

За прошедшие столетия были доказаны все утверждения Ферма, содержавшиеся в примечаниях на полях «Арифметики» Диофанта, и только Великая теорема Ферма, до недавнего времени, упорно не поддавалась усилиям математиков. Великая теорема Ферма обрела известность как самая трудная «головоломка» математики. 358 лет многие великие математики (К.Г. Баше, Л. Эйлер, Дж. Валлис Ж. Лагранж и др.) пытались доказать эту теорему, но только в конце 20 века в 1995 году она была доказана американскими математиками Э. Уайлсом и Р. Тейлором.

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

2. Делимость целых чисел. Простые и составные числа. Основная теорема арифметики

Везде далее будем рассматривать только целые числа.

Определение 2.1. Число а делится на число b (или b делит а ) если существует такое число с, что а = bc. При этом число c называется частным от деления а на b.

Обозначения: ( а делится на b ) или b  a ( b делит a ).

Перечислим простейшие свойства делимости, которые справедливы для любых целых чисел.

Если и с – частное от деления, то с – единственное.

Любое целое число делится на себя .

Если и , то .

Если и , то или a=b, или a= -b.

Если и , то а= 0.

Если и а  0, то .

Для того чтобы необходимо и достаточно чтобы.

Если , то .

Если сумма и , то .

Замечание 2.2. На основании свойства 7 в дальнейшем достаточно ограничиваться рассмотрением случая, когда делитель есть положительное число. Равным образом делимость произвольных целых чисел сводится к делимости неотрицательных чисел.

В соответствии с замечанием 2.2 будем рассматривать целые положительные числа.

Определение 2.3. Целое положительное число р  1 называется простым, если оно имеет ровно два положительных делителя: 1 и р.

Определение 2.4. Целое положительное число m  1 называется составным, если оно имеет, по крайней мере, один положительный делитель отличный от 1 и m.

3 имеет ровно 2 делителя: 1 и 3, по определению 2.3, оно простое.

4 имеет своими делителями 1, 4 и 2, по определению 2.4, число 4 – составное.

Замечание 2.5. В соответствии с определениями 2.3 и 2.4 все множество целых положительных чисел можно разбить на три подмножества: простые числа; составные числа; 1.

Замечание 2.6. Существует единственное простое четное число 2. Все остальные четные числа являются составными.

Перечислим основные свойства простых чисел.

Теорема 2.7. Если р и р₁ – простые числа и рр₁, то р не делится на р₁,и р₁ не делится на р.

Теорема 2.8. Если произведение нескольких целых чисел делится на простое число р, то по меньшей мере один из сомножителей делится на р.

Теорема 2.9. Для любого целого положительного числа n>1 наименьший, отличный от единицы положительный делитель всегда представляет собой простое число.

Теорема 2.10.(основная теорема арифметики). Всякое целое положительное число, отличное от единицы, может быть представлено в виде произведения простых сомножителей и при том единственным образом (с точностью до порядка следования сомножителей).

Таким образом, если m – целое положительное число, а р₁, р₂, …р_к— простые числа, то m =. Если, при этом, среди чисел р₁, р₂, …, р_к есть одинаковые, то можно записать каноническое представление целого числа, представив произведение одинаковых сомножителей в виде степени:

m =

Мы выяснили, что множество натуральных чисел можно разбить на три подмножества. Встает вопрос о числе простых чисел в бесконечном натуральном ряду. Существуют ли простые числа среди больших натуральных чисел, или с какого-то определенного числа все натуральные числа, следующие за ним, будут составными? Оказывается, что хотя в натуральном ряду можно найти участки составных чисел любой длины, множество простых чисел бесконечно. Это утверждение было доказано ещё древнегреческим математиком Евклидом и входит в его знаменитые «Начала». Приведём здесь доказательство этого утверждения:

Теорема 2.11. Множество простых чисел бесконечно.

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

и прибавим к этому числу 1: . Очевидно, что полученное число не делится ни на одно простое число от 1 до р , следовательно получаем, что N = 1, но непосредственно видно, что N >1 . Получили противоречие, которое возникло из-за того, что мы сделали неправильное предположение. Следовательно, множество натуральных чисел бесконечно.

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

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

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

Вот, например, еще одна частная задача на неопределенные уравнения – теперь уже второй степени, возникшая примерно за две тысячи лет до Диофанта в Древнем Египте (известно, что Диофант хорошо ее знал и часто использовал):

Если стороны треугольника пропорциональны числам 3, 4 и 5, то этот треугольник – прямоугольный.

Этот факт использовали для построения на местности прямых углов – ведь оптических измерительных приборов тогда еще не было, а для строительства домов, дворцов и тем более гигантских пирамид это надо было уметь. Поступали довольно просто. На веревке на равном расстоянии друг от друга завязывали узлы. В точке С, где надо было построить прямой угол, забивали колышек, веревку натягивали в направлении, нужном строителям, забивали второй колышек в точке В (СВ=4) и натягивали веревку так, чтобы АС=3 и АВ=5.

Треугольник с такими длинами сторон называют египетским.

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

И действительно, числа 3, 4 и 5 – корни уравнения x 2 + y 2 = z 2 .

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

Нетрудно догадаться, что числа 5, 12, 13 тоже можно считать корнями этого уравнения. А есть ли еще такие тройки чисел? Нельзя ли, взяв произвольно одно из чисел, указать остальные два? Такие вопросы интересовали еще мудрецов Древнего Вавилона. Они нашли ответы на них. Знал это и Пифагор.

Один из путей решения уравнения x 2 + y 2 = z 2 в целых числах оказался довольно простым. Запишем подряд квадраты натуральных чисел ( «квадратные числа», как говорили древние), отделив их друг от друга запятой. Под каждой запятой запишем разность между последовательными квадратами:

В нижней строке также есть квадратные числа. Первое из них 9=3 2 , над ним 16= 4 2 и 25= 5 2 , знакомая нам тройка 3, 4, 5. Следующее квадратное число в нижней строке 25, ему соответствуют 144 и 169, отсюда находим вторую известную нам тройку 5, 12, 13.Если продолжить строку квадратных чисел и подсчитать соответствующие разности, то во второй строке найдем 49= 7 2 , этому числу отвечают в строке квадратов 576= 24 2 и 625= 25 2 . Это уже третья тройка. Она была известна еще в Древнем Египте.

Теперь мы имеем право сформулировать такую теорему:

Каждое нечетное число есть разность двух последовательных квадратов.

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

Проверим, что, если х– нечётное число, то y = и z =.

Проверим также, что в этом случае равенство x 2 + y 2 = z 2 выполняется, т. е. числа, найденные по такому правилу, всегда будут составлять решение интересующего нас неопределенного уравнения. Это уравнение будем называть «уравнением Пифагора», а его решения – «пифагоровыми тройками». По этому правилу можно получить уже известные нам тройки:

если x =3 , то y =, z = =5, получилась первая пифагорова тройка;

если x =5 , то y = =12, z =–=13 — вторая тройка;

если x =7, то y = — третья тройка.

Других мы пока не знаем, но следующее за 7 нечётное число 9, тогда y =40 и z =41. Проверим наши вычисления:

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

Перепишем уравнение Пифагора следующим образом:

Это означает, что число x должно разлагаться на два неравных множителя z + y и z — y ,которые мы обозначим так, что получится такая система:

(при этом надо иметь в виду, что a ). Из этого следует, что наименьшим значением числа b может быть только единица, тогда наименьшим значением a будет 2. Вычислим x , y , z . Получается z =5, y =3, x =4, это уже известный нам «египетский треугольник». А теперь составим таблицу

Длины сторон (целочисленные) прямоугольных треугольников

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

Всем вам хорошо известно уравнение

где х, y , z – натуральные числа. Это уравнение тоже является диофантовым уравнением второй степени. Известно, что числа х, y , z можно рассматривать как длины двух катетов и гипотенузы прямоугольного треугольника. Такие числа называют в математике пифагоровыми тройками.

Вы можете без труда привести примеры пифагоровых троек, например 3; 4; 5.

Пифагорейцами был предложен способ получения пифагоровых троек с помощью перестройки квадратов. Если взять квадрат 3×3, состоящий из 9 квадратных плиток, и квадрат 4×4, состоящий из 16 плиток, то все эти плитки можно расположить по-новому, так, чтобы они образовывали квадрат 5×5, состоящий из 25 плиток.

Конечно, этот способ не годится, если пифагоровы тройки состоят из больших чисел, например x = 99, y = 4900 и z = 4901.

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

Рассмотрим один из способов нахождения пифагоровых троек.

Заметим, что если два числа из пифагоровой тройки имеют общий делитель, то на него делится и третье число. Поделив их все на общий делитель, вновь получим пифагорову тройку. Обратно, если х , y , z – пифагорова тройка, то числа n х , ny , nz , где n — целочисленный множитель, тоже образуют пифагорову тройку. По этой причине сначала исследуем пифагоровы тройки взаимно простых чисел. Такие тройки иногда называют примитивными.

– в примитивной пифагоровой тройке два числа не могут быть чётными

– все три числа не могут быть нечётными одновременно

Учитывая это, получаем, что в примитивной пифагоровой тройке два числа нечётные, а одно чётное. Исследуем эту ситуацию.

Предположим, что z является четным, т.е. z =2 m , тогда числа х и у – нечётные. Пусть x = 2 k + 1 , y = 2 k + 1. В этом случае сумма

Таким образом, число z четным быть не может, следовательно, чётным числом является либо х , либо у .

Пусть, например, х – число чётное, а у и z – нечётные числа. Из уравнения (1) имеем: y 2 = z 2 – x 2 = ( z + х )( z – х ).

Числа z + х и z – х являются взаимно простыми (доказать). При этом их произведение есть точный квадрат. Следовательно, каждое из этих чисел есть точный квадрат, то есть . Откуда получаем:

и , тогда y 2 = ( z + х )( z – х ) = a 2 b 2 , откуда y = ab .

Таким образом, мы получили, что примитивная тройка пифагоровых чисел имеет вид:

, y = ab , ……………………..(2)

где a и b – некоторые взаимно простые нечетные числа.

Теперь, выбирая произвольно a и b можно по формулам (2) получать различные примитивные пифагоровы тройки:

a = 3; b = 1 x = 4; y = 3; z = 5;

a = 5; b = 3 x = 8; y = 15; z = 17;

a = 9; b = 7 x = 16; y = 63; z = 65 и .т.д.

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

– один из «катетов» должен быть кратен трем;

– один из «катетов» должен быть кратен четырем;

– одно из чисел должно быть кратно пяти.

Найти целочисленные решения уравнения (1), т.е. пифагоровы тройки, было достаточно несложно, но если показатель степени изменить с 2 на 3 (т.е. заменить квадраты кубами), как решение полученного уравнения в целых числах становится невозможным. Это доказал в 1753 года великий математик Леонард Эйлер.

А еще ранее французский математик Пьер Ферма в 1637 году заявил о том, что он доказал, что уравнение вида x n + y n = z n не имеет решений в целых числах. Но этого доказательства научной общественности не представил. Это утверждение в последствие и стали называть теоремой Ферма, которую на протяжении 358 лет не удавалось доказать никому.

4. Теоремы о числе решений линейного диофантового уравнения

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

Теорема 1. Если в уравнении , , то уравнение имеет, по крайней мере, одно решение.

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

Теорема 3. Если в уравнении , и , то оно равносильно уравнению , в котором .

Теорема 4. Если в уравнении , , то все целые решения этого уравнения заключены в формулах:

где х₀, у₀ – целое решение уравнения , — любое целое число.

5. Алгоритм решения уравнения в целых числах

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

Найти наибольший общий делитель чисел a и b ,

если и с не делится на , то уравнение целых решений не имеет;

если и , то

Разделить почленно уравнение на , получив при этом уравнение , в котором .

Найти целое решение (х₀, у₀) уравнения путем представления 1 как линейной комбинации чисел и ;

Составить общую формулу целых решений данного уравнения

где х ₀ , у ₀ – целое решение уравнения , — любое целое число.

6. Способы решения уравнений

При решении уравнений в целых и натуральных числах можно условно выделить следующие методы:

1. Способ перебора вариантов.

2. Алгоритм Евклида.

3. Метод рассеивания.

4. Метод разложения на множители.

5. Решение уравнений в целых числах как квадратных относительно какой-либо

6. Метод остатков.

7. Метод бесконечного спуска.

Глава 2. Применение способов решения уравнений.

Примеры решения уравнений

1. Алгоритм Евклида

Задача 1 . Решить уравнение в целых числах 407 х – 2816 y = 33.

Воспользуемся составленным алгоритмом.

Используя алгоритм Евклида, найдем наибольший общий делитель чисел 407 и 2816:

2816 = 407·6 + 374;

Следовательно (407,2816) = 11, причем 33 делится на 11

Разделим обе части первоначального уравнения на 11, получим уравнение 37 х – 256 y = 3, причем (37, 256) = 1

С помощью алгоритма Евклида найдем линейное представление числа 1 через числа 37 и 256.

Выразим 1 из последнего равенства, затем последовательно поднимаясь по равенствам будем выражать 3; 34 и полученные выражения подставим в выражение для 1.

1 = 34 – 3·11 = 34 – (37 – 34·1) ·11 = 34·12 – 37·11 = (256 – 37·6) ·12 – 37·11 =

Таким образом, 37·(– 83) – 256·(–12) = 1, следовательно пара чисел х ₀ = – 83 и у ₀ = – 12 есть решение уравнения 37 х – 256 y = 3.

Запишем общую формулу решений первоначального уравнения

где t — любое целое число.

2. Способ перебора вариантов

Задача 2. В клетке сидят кролики и фазаны, всего у них 18 ног. Узнать, сколько в клетке тех и других?

Решение: Составляется уравнение с двумя неизвестными переменными, в котором х – число кроликов, у – число фазанов:

4х + 2у = 18, или 2х + у = 9.

Далее воспользуемся методом перебора:

Таким образом, задача имеет четыре решения.

3. Метод рассеивания

В Индии, где (как и в Китае) неопределенные уравнения решались в связи с астрологическими запросами и расчетами, ставился вопрос о нахождении именно целочисленных решений неопределенных уравнений. Намеки на общее решение диофантовых уравнений первой степени, т. е. вида, встречаются в трудах индийского астронома Ариабхатты, подробное же решение предложили индийские математики Брахмагупта и Бхаскара. Общий метод для решения в целых числах неопределенных (диофантовых) уравнений первой степени с целыми коэффициентами был назван в Индии методом рассеивания (в смысле размельчения).

Воспользуемся этим методом для решения следующей задачи:

«Найти два целых числа, зная, что разность произведений первого на 19 и второго на 8 равна 13».

В задаче требуется найти все целые решения уравнения

Выражая y — неизвестное с наименьшим по абсолютной величине коэффициентом через x , получим:

y = (2)

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

y = 2 x + . (3)

Из уравнения (3) следует, что y при x целом принимает целое значение только в том случае, если выражение является целым числом, скажем y ₁ . Полагая

= y ₁ (4)

вопрос сводим к решению в целых числах уравнения (4) с двумя неизвестными x и y ₁ ; его можно записать так:

Это уравнение имеет по сравнению с первоначальным (1) то преимущество, что 3 – наименьшая из абсолютных величин коэффициентов при неизвестных – меньше, чем в (1), т. е. 8. Это было достигнуто благодаря тому, что коэффициент при x (19) был заменен остатком от деления на 8.

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

x = = 2 y ₁ + . (6)

Итак, неизвестное x при целом y ₁ только тогда принимает целые значения , когда есть целое число, скажем y ₂ :

= y ₂ (7)

y ₁ = = y ₂ + (9)

= y ₃ (10)

Это самое простое из всех рассмотренных неопределенных уравнений, т.к. один из коэффициентов равен 1.

Из (11) получаем: y ₂ =2 y ₃ +13 (12)

Отсюда видно, что y ₂ принимает целые значения при любых целых значениях y ₃ . Из равенств (6), (9), (12), (3) путем последовательных подстановок можно найти следующие выражения для неизвестных и уравнения (1):

Таким образом, формулы

при y ₃ = 0, 1, 2,… дают все целые решения уравнения (1).

В следующей таблице приведены примеры таких решений.