Разрешимость линейных диофантовых уравнений с двумя переменными. Вокруг теоремы Пифагора. Истоки данных неравенств

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

Первый способ решения таких уравнений- алгоритм Евклида. Можно найти наибольший делитель натуральных чисел a и b, не раскладывая эти числа на простые множители, применяя процесс деления с остатком. Для этого надо разделить большее из этих чисел на меньшее, потом меньшее из чисел на остаток при первом делении, затем остаток при первом делении на остаток при втором делении и вести этот прицесс до тех пор, пока не произойдёт деление без остатка. Последний отличный от нуля остаток и есть искомый НОД(a,b). Чтобы доказать это утверждение, представим описанный процесс в виде следующей цепочки равенств:если a>b ,то

Здесь r1,….,rn-положительные остатки, убывающие с возрастанием номера. Из первого равенства следует,что общий делитель чисел a и b делит r1 и общий дилитель b и r1 делит а,поэтому НОД (a,b) = НОД (r1 ,r2)=….= НОД (rn-1, rn) = НОД (rn,0)= rn.Обратимся снова к системе(1).Из первого равенства, выразив остаток r1 чирез а и b ,получим r1=а- bq0. Подставляя его во второе равенство,найдём r2=b(1+q0q1)-aq1. Продолжая этот процесс дальше,мы сможем выразить все остатки через а и b, в том числе и последний rn=Аа+Вb. В результате нами доказано предложение:если d-наибольший общий делитель натуральных чисел а и b,то найдутся такие целые числа А и В,что d= Аа+Вb. Заметим,что коэффициенты А и В имеют разные знаки; если НОД(a,b)=1,то Аа+Вb=1. Как найти числа А и В видно из алгоритма Евклида.

Перейдём теперь к решению линейного уравнения с двумя неизвестными. Оно имеет вид:

Возможны два случая: либо c делится на d= НОД(a,b), либо нет. В первом случае можно разделить обе части на d и свести задачу к решению в целых числах уравнения a1x+b1y=c1, коэффициенты которого а1=а/d и b1=b/d взаимно просты. Во втором случае уравнение не имеет целочисленных решений: при любых целых x и y число аx+by делится на d и поэтому не может равнятся числу с,которое на d не делится. Итак, мы можем ограничиться случаем, когда в уравнении (2) коэффициенты взаимно просты. На основании предыдущего предложения найдутся такие целые числа x0 и y0,что ax0+by0=1, откуда пара (сx0,cy0) удовлетворяет уравнению (2) Вместе с ней уравнению (2) удовлетворяет бесконечное множество пар (x,y) целых чисел, которые можно найти по формулам

x=cx0+bt,y=cy0-at. (3)

Здесь t-любое целое число. Нетрудно показать,что других целочисленных решений нет уравнение ax+by=c не имеет. Решение, записанное в виде (3), называется общим решением уравнеия (2). Подставив вместо t конкретное целое число, получим его частное решение. Найдём, например, целочисленные решения уже встречавшегося нам уравнения 2x+5y=17. Применив к числам 2 и 5 алгоритм Евклида, получим 2*3-5=1. Значит пара cx0=3*17,cy0=-1*17 удовлетворяет уравнению 2x+5y=17. Поэтому общее решение исходного уравнения таково x=51+5t, y=-17-2t,где t принимает любые целые значения. Очевидно, неотрицательные решения отвечают тем t , для которых выполняются неравенства

Отсюда найдем -51 ?t? -17 . Этим неравенствам удовлетворяют числа -10, -9. 52

Соответствующие частные решения запишутся в виде пар (1,3), (6,1).

Применим этот же метод к решению одной из древних китайских задач о птицах.

Задача: Сколько можно купить на 100 монет петухов, кур и цыплят, если всего надо купить 100 птиц, причем петух стоит 5 монет, курица - 4, а 4 цыпленка - 1 монету?

Для решения этой задачи обозначим искомое число петухов через х, кур - через y, а цыплят через 4z (из условия видно, что число цыплят должно делится на 4). Составим систему уравнений:

которую надо решить в целых неотрицательных числах. Умножив первое уравнение системы на 4, а второе -- на (-- 1) и сложив результаты, придем к уравнению -- х+15z= 300 с целочисленными решениями х= -- 300+ 15t, z = t. Подставляя эти значения в первое уравнение, получим y = 400 -- 19t. Значит, целочисленные решения системы имеют вид х= --300+15t, y = 400--19t, z = t. Из условия задачи вытекает, что

откуда 20?t?21 1/19, т.е. t = 20 или t = 21. Итак, на 100 монет можно купить 20 кур и 80 цыплят, или 15 петухов, 1 курицу и 84 цыпленка

Второй метод решения диофантовых уравнений первой степени по своей сути не слишком отличается от рассмотренного в предыдущем пункте, но он связан с ещё одим интересным математическим понятием. Речь идёт о непрерывных или цепных дробях. Чтобы определить их вновь обратимся к алгоритму Евклида. Из первого равенства системы (1) вытекает, что дробь а/b можно записать в виде суммы целой части и правильной дроби: a/b=q0+r1/b . Но r1/b=1/b, и на основании второго равенства той же системы имем b/r1=q1+r2/r1. Значит, a/b=q0+1/q1+r2/r1. Далее получим a/b=q0+1/q1+1/q2+r3/r2. Продолжим этот процесс до тех пор, пока не придём к знаменателю qn. В результате мы представим обыкновенную дробь a/b в следующем виде: a/b=q0+1/q1+1/q2+1/…1/qn. Эйлер назвал дроби такого вида непрерывными. Приблизительно в то же время в Германии появился другой термин- цепная дробь. Так за этими дробями и сохранились оба названия. В качестве примера представим дробь 40/3t в виде цепной: 40/3t=1+9/3t=1/3t/9=1+1/3+4/9=1+1/3+1/9/4=1+1/3+1/2+1/4 .

Цепные дроби обладают следующим важным свойством: если действительное число а записать в виде непрерывной дроби, то подходящая дробь Pk/Qk даёт наилучщее приближение числа a среди всех дробей, знаменатели которых не превосходят Qk . Именно в процессе поиска наилучшего приблежения значений квадратных корней итальянский математик Пиетро Антонио Катальди (1552-1626) пришёл в 1623году к цепным дробям, с чего и началось их изучение. В заключение вернёмся к цепным дробям и отметим их преимущество и недостаток по сравнению, например, с десятичными. Удобство заключается в том, что их свойства не связаны ни с какой системой исчисления. По этой причине цепные дроби эффективно используются в теоретических исследованиях. Но широкого практического применения они не получили, так как для них нет удобных правил выполнения арифметических действий, которые имеются для десятичных дробей.

Рассмотрим Диофантовы уравнения и решим их.

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

x=7-5y/3=6-3y-2y+1/3=2-y+1-2y/3,

y=1-3k/2=1-2k-k/2=-k+1-k/2,

y=1-3(1-2t)/2=-1+3t,

x=7-5(-1+3t)/3=4-5t

(t-любое число).

2 Решить в целых числах уравнение 6xІ+5yІ=74.

6xІ-24=50-5yІ, или 6(xІ-4)=5(10-yІ), откуда xІ-4=5u,т.е. 4+5u?0, откуда u?-4/5.

Аналогично:

10-yІ=6u, т.е. 10-6u?0, u?5/3.

Целое число u удовлетворяет неравенству

4/5?u?5/3, значит. u=0 и u=1.

При u=0, получим 10=yІ, где y-не целое, что неверно. Пусть u=1, тогда xІ=9, yІ=4.

Ответ: {x1=3, {x2=3, {x3=-3, {x4=-3,

{y1=2, {y2=-2, {y3=2, {y4=-2 .

3 Решить в целых числах уравнение xі+yі-3xy=2.

Если x и y оба нечётны или одно из них нечётно, то левая часть уравнения есть нечётное число, а правая-чётное. Если же x=2m и y=2n, то 8mі+8nі-12mn=2, т.е. 2(2mі+2nі-3mn)=1, что невозможно ни при каких целых m и n.

4 Доказать, что уравнение 2xІ+5yІ=7 не имеет решений в целых числах.

Доказательство.

Из уравнения видно, что y должен быть нечётным числом. Положив y=2z+1, получим 2xІ-20zІ-20z-5=7, или xІ-10zІ-10z=6, откуда следует что x есть чётное число. Положим x=2u. Тогда 2uІ-5z(z=1)=3, что невозможно, так как z(z+1) есть чётное число.

5 Доказать, что при любом целом положительном значении а уравнение xІ+yІ=аі разрешимо в целых числах.

Доказательство.

Положим x+y=аІ, x-y=а, откуда x=a(a+1)/2 и y=a(a-1)/2. Поскольку при любом целом значении а в числителе каждой из данных дробей стоит произведение чётного и нечётного чисел, определённые таким образом x и y представляют сорбой целые числа и удовлетворяют исходному уравнению.

6 Решите в целых числах уравнение (x+1)(xІ+10=yі.

Непосредственно видим, что пары чисел (0;1) и (-1;0) являются решениями уравнения. Других решений нет, так как

xі<(x+1)(xІ+1)<(x+1)(x+1)І=(x+1) і, то (x+1)(xІ+1)?yі

ни для какого целого y (распологающегося между кубами последовательных целых чисел).

Алгебраические неравенства или их системы с рациональными коэффициентами, решения которых ищутся в интегральных или целых числах. Как правило, количество неизвестных в диофантовых уравнениях больше. Таким образом, они также известны как неопределенные неравенства. В современной математике указанное выше понятие применяется к алгебраическим уравнениям, решения которых ищутся в алгебраических целых числах некоторого расширения поля Q-рациональных переменных, поля p-адических и т. д.

Истоки данных неравенств

Исследования уравнений Диофанта находится на границе между теорией чисел и алгебраической геометрией. Поиск решений в целых переменных является одной из старейших математических задач. Уже в начале второго тысячелетия до н.э. древним вавилонянам удалось решить системы уравнений с двумя неизвестными. Эта отрасль математики в наибольшей степени процветала в Древней Греции. Арифметика Диофанта (примерно, 3-го века н.э.) является значимым и главным источником, который содержит различные типы и системы уравнений.

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

Изучение этих неравенств обычно связано с серьезными трудностями. Ввиду того, что в них присутствуют многочлены с целыми коэффициентами F (x,y1,…, y n). На основе этого, были созданы выводы, что нет единого алгоритма, с помощью которого можно было бы для любого заданного определить x, выполняется ли уравнение F (x, y 1 ,…., y n). Ситуация разрешима для y 1 , …, y n . Примеры таких многочленов могут быть записаны.

Простейшее неравенство

ax + by = 1, где a и b - относительно целые и простые числа, для него имеется огромное количество выполнений (если x 0, y 0 сформирован результат, то пара переменных x = x 0 + b n и y = y 0 -an , где n - произвольное, также будет рассматриваться как выполнение неравенства). Другим примером диофантовых уравнений служит x 2 + y 2 = z 2 . Положительные интегральные решения этого неравенства представляют собой длину малых сторон x, y и прямоугольных треугольников, а также гипотенузы z с целыми боковыми размерами. Эти числа известны как пифагорейские числа. Все триплеты относительно простых указанных выше переменных даются формулами x=m 2 - n 2 , y = 2mn, z = m 2 + n 2 , где m и n- целые и простые числа (m>n>0).

Диофант в своей «Арифметике» занимается поиском рациональных (не обязательно интегральных) решений специальных типов своих неравенств. Общая теория решения диофантовых уравнений первой степени была разработана К. Г. Башетом в 17 веке. Другие ученые в начале XIX века в основном изучали подобные неравенства типа ax 2 +bxy + cy 2 + dx +ey +f = 0, где a, b, c, d, e, и f общие, неоднородные, с двумя неизвестными второй степени. Лагранж использовал непрерывные дроби в своем исследовании. Гаусс для квадратичных форм разработал общую теорию, лежащую в основе решения некоторых типов.

В исследованиях этих неравенств второй степени значительные успехи были достигнуты только в XX веке. У А. Туэ было установлено, что диофантово уравнение a 0 x n + a 1 x n-1 y +…+a n y n =c, где n≥3, a 0 ,…,a n ,c - целые числа, а a 0 t n + … + a n не может иметь бесконечное количество целочисленных решений. Однако метод Туэ не получил должного развития. А. Бейкер создал эффективные теоремы, дающие оценки на выполнении некоторых уравнений такого рода. Б. Н. Делоне предложил другой метод исследования, применимый к более узкому классу этих неравенств. В частности, вид ax 3 + y 3 = 1 полностью разрешим этим способом.

Диофантовы уравнения: методы решения

Теория Диофанта имеет много направлений. Таким образом, хорошо известной проблемой в этой системе является гипотеза, согласно которой не существует нетривиальное решение диофантовых уравнений x n + y n = z n если n ≥ 3 (вопрос Ферма). Изучение целочисленных выполнений неравенства является естественным обобщением проблемы пифагорейских триплетов. Эйлер получил положительное решение задачи Ферма для n = 4. В силу этого результата она относится к доказательству отсутствующих целочисленных, ненулевых исследований уравнения, если n - это нечетное простое число.

Исследование, касающееся решения, не было завершено. Трудности с его выполнением связаны с тем, что простая факторизация в кольце алгебраических целых чисел не единственна. Теория дивизоров в этой системе для многих классов простых показателей n позволяет подтвердить справедливость теоремы Ферма. Таким образом, существующими методами и способами выполняется линейное диофантово уравнение с двумя неизвестными.

Виды и типы описываемых задач

Арифметика колец алгебраических целых чисел также используется во многих других задачах и решениях диофантовых уравнений. Например, такие методы были применены при выполнении неравенств вида N(a 1 x 1 +…+ a n x n) = m, где N(a) - норма a, и x 1 , …, x n найдены интегральные рациональные переменные. Этот класс включает уравнение Пелля x 2- dy 2 =1.

Значения a 1, …, a n которые появляются, эти уравнения подразделяют на два типа. Первый тип - так называемые полные формы - включают в себя уравнения, в которых среди a есть m линейно независимые числа над полем рациональных переменных Q, где m = , в которых присутствует степень алгебраических показателей Q (a1,…, a n) над Q. Неполными видами являются те, в которых максимальное количество a i меньше, чем m.

Полные формы проще, их исследование завершено, и можно описать все решения. Второй тип - неполные виды - сложнее, а разработка подобной теории еще не завершена. Такие уравнения изучаются с помощью диофантовых приближений, которые включают неравенство F(x,y)=C, где F (x,y) - многочлен степени n≥3 является неприводимым, однородным. Таким образом, можно предположить, что y i → ∞. Соответственно, если y i достаточно велико, то неравенство будет противоречить теореме Туэ, Зигеля и Рота, из которой выходит, что F(x,y)=C, где F- форма третьей степени или выше, неприводимая не может иметь бесконечное количество решений.

Данный пример составляет довольно узкий класс среди всех. Например, несмотря на их простоту, x 3 + y 3 + z 3 = N, а также x 2 +y 2 +z 2 +u 2 = N не входят в этот класс. Изучение решений является достаточно тщательно исследованной ветвью диофантовых уравнений, где в основе лежит представление квадратичными формами чисел. Лагранж создал теорему, которая гласит, что выполнение существует для всех естественных N. Любое натуральное число может быть представлено в виде суммы трех квадратов (теорема Гаусса), но оно не должно иметь вид 4 a (8K-1), где a и k неотрицательные целые показатели.

Рациональные или интегральные решения системы диофантового уравнения типа F (x 1 , …, x n) = a, где F (x 1 , …, x n) является квадратичной формой с целыми коэффициентами. Таким образом, согласно теореме Минковского-Хассе, неравенство ∑a ij x i x j = b где a ij и b рационально, имеет интегральное решение в действительных и p-адических числах для каждого простого числа p только тогда, когда оно разрешимо в этой структуре.

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

Диофантов анализ

Отделение математики, предметом которого является исследование интегральных и рациональных решений систем уравнений алгебры методами геометрии, из той же сферы. Во второй половине XIX века появление этой теории чисел привело к изучению уравнений Диофанта из произвольного поля с коэффициентами, и решения рассматривались либо в нем, либо в его кольцах. Система алгебраических функций развивалась параллельно с числами. Основная аналогия между двумя, которая была подчеркнута Д. Гильбертом и, в частности, Л. Кронекером, привела к равномерному построению различных арифметических концепций, которые обычно называются глобальными.

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

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

Исследования неравенств и варианты выполнения

При изучении рациональных (или интегральных) точек на алгебраических многообразиях возникает первая проблема, заключающаяся в их существовании. Десятая задача Гильберта сформулирована как проблема нахождения общего метода решения этого вопроса. В процессе создания точного определения алгоритма и после того, как было доказано, что подобных выполнений для большого числа задач не существует, проблема приобрела очевидный отрицательный результат, и наиболее интересным вопросом является определение классов диофантовых уравнений, для которых существует указанная выше система. Наиболее естественным подходом, с алгебраической точки зрения, является так называемый принцип Хассе: начальное поле K изучается вместе с его пополнениями K v по всем возможным оценкам. Поскольку X(K) = X(K v) являются необходимым условием существования, а K точка учитывает, что множество X(K v) не пусты для всех v.

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

Последнее важное соображение состоит в том, что множества X(K v) являются непустыми для всех v, за исключением конечного числа, так что количество условий всегда конечное, и они могут быть эффективно проверены. Однако принцип Хассе не применим к кривым степени. Например, 3x 3 + 4y 3 =5 имеет точки во всех p-адических числовых полях и в системе но не имеет рациональных точек.

Этот способ послужил отправным пунктом для построения концепции, описывающей классы главных однородных пространств абелевых многообразий для выполнения «отклонения» от принципа Хассе. Оно описывается в терминах специальной структуры, которые могут быть связаны с каждым многообразием (группа Тейта-Шафаревича). Основная трудность теории заключается в том, что методы вычисления групп сложно получить. Эта концепция также была распространена на другие классы алгебраических многообразий.

Поиск алгоритма выполнения неравенств

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

Однако впоследствии было доказано с его помощью, что если форма нечетной степени - это F, в d и n переменных и с рациональными коэффициентами, то n достаточно велико по сравнению с d, таким образом, имеет рациональную точку проективная гиперповерхность F = 0. Согласно гипотезе Артина, этот результат верен, даже если n > d 2 . Это доказано только для квадратичных форм. Аналогичные проблемы могут быть заданы и для других полей. Центральной проблемой диофантовой геометрии является структура множества целых или рациональных точек и их изучение, а первый вопрос, который нужно уточнить, состоит в том, является ли это множество конечным. В этой задаче ситуация обычно имеет конечное количество выполнений, если степень системы намного больше, чем число переменных. Это и есть основное предположение.

Неравенства на линиях и кривых

Группа X(K) может быть представлена ​​как прямая сумма свободной структуры ранга r и конечной группы порядка n. С 1930-х годов изучается вопрос о том, ограничены ли эти числа на множестве всех эллиптических кривых над данным полем K. Ограниченность кручения n была продемонстрирована в семидесятых годах. Существуют кривые произвольного высокого ранга в функциональном случае. В числовом случае по-прежнему нет ответа на этот вопрос.

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

А. Вейль обобщил теорему о конечности числа образующих группы рациональных точек на абелевы многообразия любой размерности (концепция Морделла-Вейля), распространив ее. В 1960-х годах появилась гипотеза Берча и Суиннертона-Дайера, усовершенствовавшая эту и группу и дзета-функции многообразия. Числовые доказательства подтверждают эту гипотезу.

Проблема разрешимости

Задача нахождения алгоритма, с помощью которого можно определить, имеет ли какое-либо диофантово уравнение способ решения. Существенной особенностью поставленной задачи является поиск универсального метода, который был бы подходящим для любого неравенства. Такой метод также позволил бы решать указанные выше системы, так как он эквивалентен P21+⋯+P2k=0.п1= 0 , ... , PK= 0п = 0,...,пК = 0 или п21+ ⋯ + P2К= 0 . п12+⋯+пК2=0. Проблема нахождения такого универсального способа обнаружения решений для линейных неравенств в целых числах была поставлена ​​Д. Гильбертом.

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

После этого для гипотезы Дэвиса осталось доказать, что существует метод преобразования неравенства, которое также (или не имело) в то же время решение. Было показано, что такое изменение диофантового уравнения возможно, если оно с указанными двумя свойствами: 1) в любом решении этого типа v ≤uu ; 2) для любого k существует выполнение, в котором присутствует экспоненциальный рост.

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

Алгоритмы решений диофантовых уравнений

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

• Пример №1 (простой)
• Пример №2 (сложный)

Решаем задачи на подбор чисел без подбора

• Задача про кур, кроликов и их лапы
• Задача про продавщицу и сдачу

По отзывам сибмам, настоящим камнем преткновения в школьном курсе математики не только для учеников, но и для родителей становятся диофантовы уравнения. Что это такое и как их правильно решать? Разобраться нам помогли учитель математики образовательного центра «Горностай» Аэлита Бекешева и кандидат физико-математических наук Юрий Шанько.

Кто такой Диофант?

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

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

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

А ведь вы знаете кое-что о диофантовых уравнениях…

Диофантовы уравнения знают все! Это задачки для учеников младших классов, которые решаются подбором.

” Например, «сколькими различными способами можно расплатиться за мороженое ценой 96 копеек, если у вас есть только копейки и пятикопеечные монеты?»

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

” Зачастую мамы (особенно те, кто окончил школу еще при развитом социализме) полагают, что основная цель таких задач - научить детей расплачиваться мелочью за мороженое. И вот, когда они искренне убеждены, что раскладывание мелочи кучками осталось далеко в прошлом, их любимый семиклассник (или восьмиклассник) подходит с неожиданным вопросом: «Мама, как это решать?», и предъявляет уравнение с двумя переменными. Раньше таких задачек в школьном курсе не было (все мы помним, что уравнений должно быть столько же, сколько и переменных), так что мама не-математик нередко впадает в ступор. А ведь это та же самая задача про мелочь и мороженое, только записанная в общем виде!

Кстати, а зачем к ней вдруг возвращаются в седьмом классе? Все просто: цель изучения диофантовых уравнения - дать основы теории целых чисел, которая дальше развивается как в математике, так и в информатике и программировании. Диофантовы уравнения часто встречаются среди задач части «С» единого госэкзамена. Трудность, прежде всего в том, что существует множество методов решения, из которых выпускник должен выбрать один верный. Тем не менее, линейные диофантовы уравнения ax + by = c могут быть решены относительно легко с помощью специальных алгоритмов.

Алгоритмы для решения диофантовых уравнений

Изучение диофантовых уравнения начинается в углубленном курсе алгебры с 7 класса. В учебнике Ю.Н. Макарычева, Н.Г. Миндюка приводятся некоторые задачи и уравнения, которые решают с использованием алгоритма Евклида и метода перебора по остаткам , - рассказывает Аэлита Бекешева. - Позже, в 8 - 9 классе, когда уже рассматриваем уравнения в целых числах более высоких порядков, показываем ученикам метод разложения на множители , и дальнейший анализ решения этого уравнения, оценочный метод . Знакомим с методом выделения полного квадрата . При изучении свойств простых чисел знакомим с малой теоремой Ферма, одной из основополагающих теорем в теории решений уравнений в целых числах. На более высоком уровне это знакомство продолжается в 10 - 11 классах. В это же время мы подводим ребят к изучению и применению теории «сравнений по модулю», отрабатываем алгоритмы, с которыми знакомились в 7 - 9 классах. Очень хорошо это материал прописан в учебнике А.Г. Мордковича «Алгебра и начала анализа, 10 класс» и Г.В. Дорофеева «Математика» за 10 класс.

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

Сам метод Евклида относится к другой математической задаче - нахождению наибольшего общего делителя: вместо исходной пары чисел записывают новую пару - меньшее число и разность между меньшим и большим числом исходной пары. Это действие продолжают до тех пор, пока числа в паре не уравняются - это и будет наибольший общий множитель. Разновидность алгоритма используется и при решении диофантовых уравнений - сейчас мы вместе с Юрием Шанько покажем на примере, как решать задачи "про монетки".

Рассматриваем линейное диофантово уравнение ax + by = c, где a, b, c, x и y — целые числа. Как видите, одно уравнение содержит две переменных. Но, как вы помните, нам нужны только целые корни, что упрощает дело - пары чисел, при которых уравнение верно, можно найти.

Впрочем, диофантовы уравнения не всегда имеют решения. Пример: 4x + 14y = 5. Решений нет, т.к. в левой части уравнения при любых целых x и y будет получаться четное число, а 5 — число нечетное. Этот пример можно обобщить. Если в уравнении ax + by = c коэффициенты a и b делятся на какое-то целое d, а число c на это d не делится, то уравнение не имеет решений. С другой стороны, если все коэффициенты (a, b и c) делятся на d, то на это d можно поделить все уравнение.

Например, в уравнении 4x + 14y = 8 все коэффициенты делятся на 2. Делим уравнение на это число и получаем: 2𝑥 + 7𝑦 = 4. Этот прием (деления уравнения на какое-то число) позволяет иногда упростить вычисления.

Зайдем теперь с другой стороны. Предположим, что один из коэффициентов в левой части уравнения (a или b) равен 1. Тогда наше уравнение уже фактически решено. Действительно, пусть, например, a = 1, тогда мы можем в качестве y взять любое целое число, при этом x = c − by. Если научиться сводить исходное уравнение к уравнению, в котором один из коэффициентов равен 1, то мы научимся решать любое линейное диофантово уравнение!

Я покажу это на примере уравнения 2x + 7y = 4.

Его можно переписать в следующем виде: 2(x + 3y) + y = 4.

Введем новую неизвестную z = x + 3y, тогда уравнение запишется так: 2z + y = 4.

Мы получили уравнение с коэффициентом один! Тогда z — любое число, y = 4 − 2z.

Осталось найти x: x = z − 3y = z − 3(4 − 2z) = 7z − 12.

Пусть z=1. Тогда y=2, x=-5. 2 * (-5)+7 * 2=4

Пусть z=5. Тогда y=-6, x=23. 2 * (23)+7 * (-6)=4

” В этом примере важно понять, как мы перешли от уравнения с коэффициентами 2 и 7 к уравнению с коэффициентами 2 и 1. В данном случае (и всегда!) новый коэффициент (в данном случае - единица) это остаток от деления исходных коэффициентов друг на друга (7 на 2).

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

Давайте попрообуем решить более сложное уравнение, предлагает Аэлита Бекешева.

Рассмотрим уравнение 13x - 36y = 2.

Шаг №1

36/13=2 (10 в остатке). Таким образом, исходное уравнение можно переписать следующим образом: 13x-13* 2y-10y=2. Преобразуем его: 13(x-2y)-10y=2. Введем новую переменную z=x-2y. Теперь мы получили уравнение: 13z-10y=2.

Шаг №2

13/10=1 (3 в остатке). Исходное уравнение 13z-10y=2 можно переписать следующим образом: 10z-10y+3z=2. Преобразуем его: 10(z-y)+3z=2. Введем новую переменную m=z-y. Теперь мы получили уравнение: 10m+3z=2.

Шаг №3

10/3=3 (1 в остатке). Исходное уравнение 10m+3z=2 можно переписать следующим образом: 3* 3m+3z+1m=2. Преобразуем его: 3(3m+z)+1m=2. Введем новую переменную n=3m+z. Теперь мы получили уравнение: 3n+1m=2.

Ура! Мы получили уравнение с коэффициентом единица!

m=2-3n, причем n может быть любым числом. Однако нам нужно найти x и y. Проведем замену переменных в обратном порядке. Помните, мы должны выразить x и y через n, которое может быть любым числом.

y=z-m; z=n-3m, m=2-3n ⇒ z=n-3* (2-3n), y=n-3*(2-3n)-(2-3n)=13n-8; y=13n-8

x=2y+z ⇒ x=2(13n-8)+(n-3*(2-3n))=36n-22; x=36n-22

Пусть n=1. Тогда y=5, x=24. 13 * (14)-36 * 5=2

Пусть n=5. Тогда y=57, x=158. 13 * (158)-36 * (57)=2

Да, разобраться не очень просто, зато теперь вы всегда сможете решить в общем виде задачи, которые решаются подбором!

Решаем задачи на подбор чисел

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

Задача про лапы

Условия

В клетке сидят куры и кролики. Всего у них 20 лап. Сколько там может быть кур, а сколько - кроликов?

Решение

Пусть у нас будет x кур и y кроликов. Составим уравнение: 2х+4y=20. Сократим обе части уравнения на два: x+2y=10. Следовательно, x=10-2y, где x и y - это целые положительные числа.

Ответ

Число кроликов и куриц: (1; 8), (2; 6), (3; 4), (4; 2), (5; 0)

Согласитесь, получилось быстрее, чем перебирать «пусть в клетке сидит один кролик...»

Задача про монетки

Условия

У одной продавщицы были только пяти- и двухрублевые монетки. Сколькими способами она может набрать 57 рублей сдачи?

Решение

Пусть у нас будет x двухрублевых и y пятирублевых монеток. Составим уравнение: 2х+5y=57. Преобразуем уравнение: 2(x+2y)+y=57. Пусть z=x+2y. Тогда 2z+y=57. Следовательно, y=57-2z , x=z-2y=z-2(57-2z) ⇒ x=5z-114 . Обратите внимание, переменная z не может быть меньше 23 (иначе x, число двухрублевых монеток, будет отрицательным) и больше 28 (иначе y, число пятирублевых монеток, будет отрицательным). Все значения от 23 до 28 нам подходят.

Ответ

Шестью способами.

Подготовила Татьяна Яковлева

Пункт 5. Линейные диофантовы уравнения с двумя неизвестными.

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

Отступление про Диофанта и его исторический след.

Третий и последний период античного общества - период господства Рима. Рим завоевал Сиракузы в 212 году, Карфаген - в 146 году, Грецию - в 146, Месопотамию - в 46, Египет - в 30 году до нашей эры. Огромные территории оказались на положении колоний, но римляне не трогали их культуры и экономического устройства пока те исправно платили налоги и поборы. Установленный римлянами на столетия мир, в отличие от всех последующих великих миров и рейхов, принес всей завоеванной территории самый длинный период безвоенного существования, торговли и культурного обмена.

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

Основной труд Диофанта (ок. 250 г.) - "Арифметика". Уцелели только шесть книг оригинала, общее их число - предмет догадок. Мы не знаем, кем был Диофант, - возможно, что он был эллинизированный вавилонянин. Его книга - один из наиболее увлекательных трактатов, сохранившихся от греко-римской древности. В ней впервые встречается систематическое использование алгебраических символов, есть особые знаки для обозначения неизвестного, минуса, обратной величины, возведения в степень. Папирус N 620 Мичиганского университета, купленный в 1921 году, принадлежит эпохе Диофанта и наглядно это подтверждает. Среди уравнений, решаемых Диофантом, мы обнаруживаем такие, как x 2 - 26 y 2 = 1 и x 2 - 30 y 2 = 1, теперь известные нам как частные случаи "уравнения Пелля", причем Диофант интересуется их решениями именно в целых числах.

Книга Диофанта неожиданно оказала еще и огромное косвенное влияние на развитие математической науки последних трех столетий. Дело в том, что юрист из Тулузы Пьер Ферма (1601 - 1665), изучая "Арифметику" Диофанта, сделал на полях этой книги знаменитую пометку: "Я нашел воистину удивительное доказательство того, что уравнение x n + y n = z n при n > 2, не имеет решений в целых числах, однако поля этой книги слишком малы, чтобы здесь его уместить". Это одно из самых бесполезных математических утверждений получило название "Великой теоремы Ферма" и, почему-то, вызвало настоящий ажиотаж среди математиков и любителей (особенно после назначения в 1908 году за его доказательство премии в 100 000 немецких марок). Попытки добить эту бесполезную теорему породили целые разделы современной алгебры, алгебраической теории чисел, теории функций комплексного переменного и алгебраической геометрии, практическая польза от которых уже не подлежит никакому сомнению. Сама теорема, кажется, благополучно доказана в 1995 году; Пьер Ферма, конечно, погорячился на полях "Арифметики", ибо он физически не мог придумать подобного доказательства, требующего колоссальной совокупности математических знаний. Элементарного доказательства великой теоремы Ферма пока никто из жителей нашей планеты найти не смог, хотя над его поиском бились лучшие умы последних трех столетий. Однако, до сих пор тысячи психически нездоровых любителей-"ферматистов" в жажде славы и денег бомбят своими письмами академические институты и университеты и почти ежегодно один из сотрудников кафедры алгебры и дискретной математики Уральского госуниверситета, где я работаю, вынужден вести с таким психом дипломатическую переписку на заранее заготовленном бланке:

"Уважаемый.............................! В Вашем доказательстве на странице №......, в строке №........, содержится ошибка..............................................................".

Пусть требуется решить линейное диофантово уравнение:

ax + by = c ,

где a , b , c О Z ; a и b - не нули.

Попробуем порассуждать, глядя на это уравнение.

Пусть (a , b ) = d . Тогда a = a 1 d ; b = b 1 d и уравнение выглядит так:

a 1 d· x + b 1 d· y = c , т.е. d· (a 1 x + b 1 y ) = c .

Теперь и ежику ясно, что у такого уравнения имеется решение (пара целых чисел x и y ) только тогда, когда d | c . Поскольку очень хочется решать это уравнение дальше, то пусть d | c . Поделим обе части уравнения на d , успокоимся, и всюду далее будем считать, что (a , b ) = 1. Так можно.

Рассмотрим несколько случаев.

Случай 1. Пусть c = 0, уравнение имеет вид ax + by = 0 - " однородное линейное диофантово уравнение". Немножко потрудившись, находим, что

x = -

b a

y .

Так как x должен быть целым числом, то y = at , где t - произвольное целое число (параметр). Значит x = - bt и решениями однородного диофантова уравнения ax + by = 0 являются все пары вида {- bt , at }, где t = 0; ±1; ±2;... Множество всех таких пар называется общим решением линейного однородного диофантова уравнения, любая же конкретная пара из этого множества называется частным решением.

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

Случай 2. Пусть теперь c № 0. Этот случай закрывается следующей теоремой.

Теорема. Пусть (a , b ) = 1, { x 0 , y 0 } - частное решение диофантова уравнения ax + by = c . Тогда его общее решение задается формулами:

м н о

x = x 0 - bt y = y 0 + at .

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

Доказательство. То, что правые части указанных в формулировке теоремы равенств действительно являются решениями, проверяется их непосредственной подстановкой в исходное уравнение. Покажем, что любое решение уравнения ax + by = c имеет именно такой вид, какой указан в формулировке теоремы. Пусть { x * , y *} - какое-нибудь решение уравнения ax + by = c . Тогда ax * + by * = c , но ведь и ax 0 + by 0 = c . Следуя многолетней традиции доказательства подобных теорем, вычтем из первого равенства второе и получим:

a (x *- x 0) + b (y *- y 0) = 0

Однородное уравнение. Далее, глядя на случай 1, рассмотрение которого завершилось несколькими строками выше, пишем сразу общее решение: x *- x 0 = - bt , y *- y 0 = at , откуда моментально, используя навыки третьего класса средней школы, получаем:

м н о

x * = x 0- bt , y * = y 0 + at.

"Все это, конечно, интересно", - скажет читатель, - "Но как же искать то самое частное решение { x 0 , y 0 }, ради которого и затеяна вся возня этого пункта и которое, как теперь выясняется, нам так нужно?". Ответ до глупости прост. Мы договорились, что (a , b ) = 1. Это означает, что найдутся такие u и v из Z , что au + bv = 1 (если вы это забыли, вернитесь в пункт 4), причем эти u и v мы легко умеем находить с помощью алгоритма Евклида. Умножим теперь равенство au + bv = 1 на c и получим: a (uc ) + b (vc ) = c , т.е. x 0 = uc , y 0 = vc . Вот и все!

Пример. Вы - хроноп, придуманный Хулио Кортасаром в книжке "Из жизни хронопов и фамов". Вам нужно расплатиться в магазине за синюю пожарную кишку, ибо красная в хозяйстве уже давно есть. У вас в кармане монеты достоинством только в 7 и 12 копеек, а вам надо уплатить 43 копейки. Как это сделать? Решаем уравнение:

7 x + 12 y = 43

Включаем алгоритм Евклида:

12 = 7· 1 + 5
7 = 5· 1 + 2
5 = 2· 2 + 1
2 = 1· 2

Значит, наибольший общий делитель чисел 7 и 12 равен 1 , а его линейное выражение таково:

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

т.е. u = - 5, v = 3. Частное решение:

x 0 = uc = (- 5) · 43 = - 215
y 0 = vc = 3 · 43 = 129.

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

x = -215 - 12 t
y = 129 + 7 t

и, легко видеть, что при t = - 18, получаются вполне разумные x = 1, y = 3, поэтому дубасить кассира необязательно.

Муниципальное бюджетное общеобразовательное учреждение

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

г. Павлово.

Научно-исследовательская работа

Методы решения диофантовых уравнений.

Отделение: физико-математическое

Секция: математика

Выполнил:

ученик 8 А класса Трухин Николай (14 лет)

Научный руководитель:

учитель математики

Лефанова Н. А.

г. Павлово

2013 г.

Оглавление

I Введение…………………………………………………………………………3

II Обзор литературы……………………………………………………………....5

III Основная часть…………………………………………………………………6

IV Заключение…………………………………………………………………...15

V Список литературы……………………………………………………………16

VI Приложение…………………………………………………………………..17

Введение.

В 2011-2012 году я выполнял исследовательскую работу на тему: «Решение уравнений в Древней Греции и Индии». При работе над ней я познакомился с трудами Диофанта Александрийского и Мухаммеда аль - Хорезми. В своей прошлой работе я рассмотрел некоторые способы решения уравнений первой степени с двумя неизвестными, познакомился с некоторыми старинными задачами, приводящими к решению уравнений первой степени с двумя неизвестными.

Мухаммед Бен Мусса аль – Хорезми, - или Магомед сын Моисея Хорезмского, состоящий членом «дома мудрости» в Иране, около 820 года нашего летоисчисления написал книгу, где учил решать простые и сложные вопросы арифметики, которые необходимы людям при дележе наследства, составлении завещаний, разделе имущества и судебных делах, в торговле, всевозможных сделках. С именем аль – Хорезми связаны понятия «алгебра», «арабские цифры», «алгоритм». Он отделил алгебру от геометрии, внёс большой вклад в математику исламского средневековья. Мухаммед аль – Хорезми был известен и уважаем, как при жизни, так и после смерти.

Но мне захотелось больше узнать о Диофанте. И тема моего исследования в этом году: «Методы решения диофантовых уравнений»

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

Цель моей работы:

1.Продолжить знакомство с диофантовыми уравнениями.

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

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

II . Обзор литературы.

При написании работы мной использовалась следующая литература:

Мной использована информация о Диофанте и аль – Хорезми.

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

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

В этой книге собрано около 200 статей, посвященных основным понятиям математики и её приложения. Мной были использованы материалы статей «Алгебра», «Уравнения», «Диофантовы уравнения»

Из книги взяты тексты задач для практического использования.

По теме мной использовался сайт:

http :// ru . wikipedia . org (информация об аль – Хорезми и Диофанте. О методах решения диофантовых уравнений).

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

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

(1)

Рассмотрим задачу.

Задача 1. В клетке находится x фазанов и у кроликов. Сколько в клетке фазанов и кроликов, если общее количество ног равно 62.

Общее число ног можно записать с помощью уравнения 2х+4у=62 (2)

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

Линейным уравнением с двумя переменными называется уравнение вида ax +by =c , где x и у – переменные, а, b и с – некоторые числа.

Однозначно определить из уравнения (2) значения x и y нельзя. Даже если ограничиться только натуральными значениями переменных, здесь могут быть такие случаи: 1 и 15, 3 и 14, 5 и 13 и т. д.

Пара чисел (a , b ) называется решением уравнения с двумя переменными, если при замене x на а и y на b получаем истинное равенство.

Каждому уравнению с двумя переменными соответствует множество его решений, т. е. множество, состоящее из всех пар чисел (a , b ), при подстановке которых в уравнение получается истинное равенство. При этом, конечно, если заранее указаны множества Х и Y , которые могут принимать неизвестные x и у, то надо брать лишь такие пары (a , b ), для которых а принадлежит Х и b принадлежит Y .

Пару чисел (a , b ) можно изобразить на плоскости точкой М, имеющей координаты а и b , М= М (a , b ). Рассматривая изображения всех точек множества решений уравнения с двумя неизвестными, получим некоторое подмножество плоскости. Его называют графиком уравнения.

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

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

Например, равносильны уравнения х+2у=5 и 3х+6у=15 – любая пара чисел, удовлетворяющая одному из этих уравнений, удовлетворяет и второму.

Уравнения с двумя переменными обладают такими же свойствами, как и уравнения с одной переменной:

1) если в уравнении перенести слагаемое из одной части в другую, изменив его знак, то получится уравнение, равносильное данному;

2) если обе части уравнения умножить или разделить на одно и то же отличное от нуля число, то получится уравнение, равносильное данному.

Существует несколько способов решения диофантовых уравнений:

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

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

С использованием цепной дроби

Метод рассеивания (измельчения)

При помощи программирования на языке программирования Паскаль

В своей работе я исследовал методы – перебор вариантов и рассеивание (измельчения)

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

Задача 2 . Андрей работает летом в кафе. За каждый час ему платят 10 р. И высчитывают 2 р. за каждую разбитую тарелку. На прошедшей неделе он заработал 180 р. Определите, сколько часов он работал и сколько разбил тарелок, если известно, что он работает не более 3 ч в день.

Решение.

Пусть x часов он всего работал в неделю, тогда 10х р. ему заплатили, но он разбил у тарелок, и с него вычли 2у р. Имеем уравнение 10х – 2у =180 , причем x меньше или равен 21. Получим: 5х-у=90, 5х=90+у, х=18+у:5.

Так как x целое число, то у должно нацело делится на 5, чтобы в правой части получилось целое число. Возможны четыре случая

у=0, х=18, т. е. решением является пара – (18, 0);

у=5, х=19, (19, 5);

у=10, х=20, (20, 10);

у=15, х=21, (21, 15).

Эту задачу я решил, используя способ перебора вариантов. Ответ содержит четыре возможных варианта. Я попробовал решить этим способом ещё несколько задач.

Задача 3. Из двухрублевых и пятирублевых монет составлена сумма в 23 рубля. Сколько среди этих монет двухрублевых?

Решение.

Пусть x – количество двухрублевых монет, у – количество пятирублевых монет. Составим и решим уравнение: 2х+5у=23; 2х=23–5у; x = (23 – 5у):2; x =(22+1 – 5у):2, почленно поделим 22 на 2 и (1 – 5у) на 2, получим: x = 11 + (1 – 5у):2.

Так как x и y натуральные числа по условию задачи, то левая часть уравнения есть натуральное число, значит, и правая часть должна быть натуральным числом. К тому же, чтобы получить в правой части число натуральное, нужно чтобы выражение (1 – 5у) нацело делилось на 2. Осуществим перебор вариантов.

y =1, х=9, то есть двухрублевых монет может быть 9;

у=2, при этом выражение (1 – 5у) не делится нацело на 2;

у=3, х=4, то есть двухрублевых монет может быть 4;

при у больше или равном 4 значение x не является числом натуральным.

Таким образом, ответ в задаче следующий: среди монет 9 или 4 двухрублевых.

Задача 4. Шехерезада рассказывает свои сказки великому правителю. Всего она должна рассказать 1001 сказку. Сколько ночей потребуется Шехерезаде, чтобы рассказать все свои сказки, если x ночей она будет рассказывать по 3 сказки, а остальные сказки по 5 за у ночей

Решение.

Сказочнице потребуется x + у ночей, где x и у – натуральные корни уравнения 3х+5у=1001

x = (1001 – 5у):3; так как x – натуральное число, то и в правой части равенства также должно быть натуральное число, а значит выражение (1001 – 5у) должно нацело делиться на 3.

Осуществим перебор вариантов.

у=1, 1001 – 5у=1001-5= 996, 996 делится на 3, следовательно, х=332; решение (332;1);

у=2, 1001– 10=991, 991 не делится на 3;

у=3, 1001 – 15 = 986; 986 не делится на3;

у =4, 1001 – 20 = 981, 981 делится на 3, следовательно, x = 327, решение (327;4) и т. д.

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

Уравнение ax + by = c (1) в приведённых задачах я решал способом перебора вариантов. Я уяснил для себя, что способ перебора вариантов не всегда эффективен для решения данной задач, так как для нахождения всех решений уравнения требуются значительные временные затраты. И, на мой взгляд, в настоящее время он неактуален.

Поэтому я решил задачу про Шехерезаду, используя метод рассеивания (измельчения).

Метод рассеивания – это общий метод для решения в целых числах неопределённых уравнений первой степени с целыми коэффициентами.

Итак, решим задачу про Шехерезаду методом рассеивания:

Обратимся к уравнению 3х + 5у = 1001.

Перепишем его иначе: 3х= 1001- 5у; 3х= 1001 - 2у - 3у;

x = – y +
и обозначим x l = у + x

В результате уравнение примет вид 3х 1 = 1001 – 2у или

у = –x l
.

Если вновь произвести замену у 1 = у + х 1 , то придем к уравнению

x 1 + 2у 1 = 1001. Заметим, что коэффициенты при неизвестных уменьшились - измельчились.

Здесь коэффициент при x 1 , равен 1, а поэтому при любом целом у 1 = t число х 1 тоже целое. Остается выразить исходные переменные через t :

х 1 = 1001 – 2 t , следовательно, у = – 1001 + 3 t , а x = 2002 – 5 t . Итак, получаем бесконечную последовательность (2002 – 5 t , – 1001 + 3 t ) целочисленных решений. Внешний вид формул для нахождения значений переменных отличается от решений, полученных ранее, но с учетом условия задачи, корни получаются те же самые. Так, пара (332;1) получается при t =334.

На мой взгляд, этот метод не только более удобный (у него есть алгоритм действий), но и интересный. Известно, что этот метод в первые применил в начале VI в. индийский математик Ариабхатта.

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

Оно представлено ниже:

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

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

Решение:

(1) 19x – 8y = 13

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

(2) y = (19x – 13)/8

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

(3) y = 2x + (3x – 13)/8

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

(4) (3x - 13)/8 = y 1 ,

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

(5) 3x – 8y 1 = 13.

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

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

(6) x = (8y 1 +13)/3 = 2y 1 + (2y 1 + 13)/3.

Итак, неизвестное x при целом y 1 только тогда принимает целые значения, когда (2y 1 + 13)/3 есть целое число, скажем y 2 :

(7) (2y 1 + 1)/3 = y 2 ,

или

(8) 3y 2 – 2 y 1 = 13.

(9) y 1 = (3y 2 - 13)/2 = y 2 + (y 2 - 13)/2

Полагая

(10) (y 2 - 13)/2 = y 3 ,

получаю

(11) y 2 – 2 y 3 = 13.

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

Из (11) получаю:

(12) y 2 = 2y 3 + 13.

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

x = 2y 1 + y 2 = 2(y 2 + y 3 ) + y 2 = 3y 2 + 2y 3 = 3(2y 2 + 13) + 2y 3 = 8y 3 + 39;

у = 2x + y 1 = 2(8y 3 + 39) + y 2 + y 3 = 19y 3 +91.

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

x = 8y 3 + 39,

y = 19y 3 + 91.

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

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

Таблица 1.

y3

x

y

Решим эту задачу рационально. В решении используется определённый алгоритм.

Задача 5.

Найти два числа, если разность произведений первого на 19 и второго на 8 равна 13.

Решение. Требуется решить уравнение 19х - 8у = 13

Перепишем его иначе: 8y =19x –13; 8y =16x +3x –13; у = 2х +

и обозначим y 1 = у - 2х.

В результате уравнение примет вид 8у 1 = Зx - 13 или x = 2y 1
.

Если вновь произвести замену х 1 = x - 2у 1 , то придем к уравнению

3x l - 2у 1 = 13.

Коэффициенты при неизвестных уменьшились - измельчились. Дальнейшее измельчение: y 1 = x l +
, то получим у 2 =у 1 –х 1 .

В результате последнее уравнение преобразуется к виду х 1 - 2у 2: = 13. Здесь коэффициент при х 1 , равен 1, а поэтому при любом целом у 2 = t число х 1 тоже целое.

Остается выразить исходные переменные через t :

вначале выразим х 1 =2t +13, y 1 = 3t +13; а затем x = 8 t +39, y = 19 t + 91.

Итак, получаем бесконечную последовательность (39 + 8 t , 91 + 19 t ) целочисленных решений . Уравнение ax + by = c (1) в приведённых задачах я решал способом рассеивания (измельчения).

IV . Заключение.

Изучая диофантовы уравнения для их решения, я использовал методы перебора вариантов и рассеивания (измельчения). Этими методами я решал, как современные, так и древние задачи. В содержании моей работы были включены задачи, которые сводятся к решению уравнений первой степени с двумя переменными ах+b у=с (1)

В ходе своей работы я сделал выводы:

Метод перебора требует значительные временные затраты, а значит он не очень удобен и рационален.

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

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

V . Список литературы

Г. И. Глейзер «История математики в школе» М.: изд. «Просвещение» 1964г. 376с.

И. Г. Башмакова «Диофант и диофантовы уравнения» М.: изд. «Наука» 1972г. 68с.

В. А. Никифоровский «В мире уравнений» М.: изд. «Наука» 1987г. 176с.

А. П. Савин «Энциклопедический словарь юного математика» М.: изд. «Педагогика» 1985г.

Г. М. Возняк, В. Ф. Гусев «Прикладные задачи на экстремумы» М.: изд. «Просвещение» 1985г. 144с.

http :// ru . wikipedia . org

VI . Приложение.

На фермерском хозяйстве нужно провести водопровод длиной 167м. Имеются трубы длиной 5м и 7м. Сколько нужно использовать тех и других труб, чтобы сделать наименьшее количество соединений (трубы не резать)?

Учитывая, что количество как одних, так и других труб может изменяться, количество 7 – метровые трубы обозначаем через х, 5 – метровые – через у

Тогда 7х – длина 7 – метровых труб, 5у – длина 5 – метровых труб.

Отсюда получаем неопределённое уравнение:

7х+5у=167

Выпазив, например, переменную у через переменную х , получим:

Методом перебора легко найти соответствующие пары значений х и у , которые удовлетворяют уравнению 7х+5у=167

(1;32), (6;25), (11;18), (16;11), (21;4).

Из этих решений наиболее выгодное последнее, т. е. х=21; у=4.

Многие старинные способы отгадывания чисел и дат рождения основываются на решении диофантовых уравнений. Так, например, чтобы отгадать дату рождения (месяц и число) собеседника, достаточно узнать у него сумму, получаемую от сложения двух произведений: числа даты (х ) на 12 и номера месяца (у ) на 31.

2. Пусть сумма произведений, о которых идёт речь, равна 330. Найти дату рождения.

Решим неопределённое уравнение

12 х + 31 у = 330.

С помощью метода рассеивания получим:

х = 43 – 31 у 4 ,

у = 6 – 12 у 4 .

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

у 4 = 1, х = 12, у = 6.

Итак, дата рождения: 12-е число 6-го месяца, т.е. 12 июня.