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

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

Ученик от 9 клас MOU "Upshinskaya OOSh"

Антонов Юрий

„Ако искаш да се научиш да плуваш, тогава

смело влизайте във водата, а ако искате

научете се да решавате проблеми, а след това ги решавайте.

Д.Поя

Ръководител - Софронова Н.А. .

Задача

За подови настилки с ширина 3 метра има дъски с ширина 11 см и 13 см. Колко дъски от двата размера са ви необходими?

Ако х - броят на дъските с ширина 11 см и при - броя на дъските с ширина 13 см, тогава трябва да решим уравнението:

11 х + 13 y = 300

Характеристики на уравнението 11 x + 13 y \u003d 300: ▪ Коефициенти 11, 13, 300 са цели числа. ▪ Броят на неизвестните надвишава броя на уравненията. ▪ Решенията на това уравнение x и y трябва да бъдат цяло число положителни числа

Алгебрични уравнения или системи от алгебрични уравнения с цели коефициенти, в които броят на неизвестните е по-голям от броя на уравненията и за които трябва да се намерят цели решения, се наричат ​​неопределени или диофантинова, кръстен на гръцки математик Диофант .

Примери за диофантови уравнения

1 . Намерете всички двойки цели числа

х , г , за което е вярно равенство

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

има безкраен брой решения

цели числа

Обективен:

Да открия:

• Какъв вид методи с съществуват за решения на диофантови уравнения?

Задачи:

• Намерете и и научете методи за решаване линеен Диофантови уравнения с две променливи.

• Разгледайте възможностите на теорията на линейните диофантови уравнения.

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

• Неопределените уравнения в цели числа са решени още преди Диофант. Голям интерес представляваше например алгебричното уравнение х 2 + г 2 = z 2 , обвързващи страни х , при , z правоъгълен триъгълник. Цели числа х , г и z , които са решения на това уравнение, се наричат "Питагорови тройки" .

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

• Трудовете на Диофант са пряко свързани и с математическите изследвания на френския математик Пиер дьо Ферма. Смята се, че работата на Ферма е дала началото на нова вълна в развитието на теорията на числата. И един от неговите проблеми е известното уравнение на Ферма

х н +y н =z н

Нито един голям математик не подмина теорията на диофантовите уравнения.

Ферма, Ойлер, Лагранж, Гаус, Чебишев оставиха незаличима следа в тази интересна теория.

1, (Каталуна); ax 2 + bxy + su 2 + dx + ey + f \u003d 0, където a, b, c, d, e, f са цели числа, т.е. нехомогенно уравнениевтора степен с две неизвестни (P. Fermat, J. Vallis, L. Euler, J. Lagrange и K. Gauss) "width="640"

Примери за неопределени уравнения решени от велики математици 19-ти и 20-ти век: х 2 − ню 2 = 1 , където н не е точен квадрат (Ферма, Пел); х z − г T = 1 , където z , T 1, (Каталуна); о 2 + b.xy + су 2 + dx + ей + f = 0 , където а , b , с , д , д , f - цели числа, т.е. общо нехомогенно уравнение от втора степен с две неизвестни (P. Fermat, J. Vallis, L. Euler, J. Lagrange и K. Gauss)

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

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

10-та задача на Хилберт

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

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

10-тата задача на Хилберт е неразрешима – не съществува търсеният алгоритъм.

Винаги ли е възможно да се намерят всички цели решения за конкретно неопределено уравнение или да се докаже липсата на такова?

• Задачата за решаване на уравнения в цели числа е напълно решена само за уравнения от първа степен с две или три неизвестни.
• DE от втора степен с две неизвестни вече се решава много трудно.
• DE от втора степен с повече от две неизвестни се решават само в някои специални случаи, например уравнението х 2 + г 2 = z 2 .
• DE със степен по-висока от втората имат, като правило, само краен брой решения (в цели числа).
• За уравнения над втора степен с две или повече неизвестни дори проблемът за съществуването на целочислени решения е доста труден. Например, не е известно дали уравнението има

х 3 + г 3 + z 3 = 30 поне едно цяло число решение.

• За решаване на отделни диференциални уравнения, а понякога и за конкретни уравнения, трябва да се измислят нови методи. Очевидно няма алгоритъм, който да позволи намирането на решения на произволни DE.

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

Обща форма:

LDE с две променливи:

а х + от = c

LDE с три променливи:

а х + от + cz = d

LDE с две неизвестни

LDE с две променливи:

а х + от = c

Решения:

х = х 0 - bt

при = при 0 + при

Хомогенен:

а х + от = 0

Решения:

х = - bt

при = при

Намиране на лично решение

Методи за решение:

• Множествен метод.
• Приложение на алгоритъма на Евклид.
• Итерационен метод.
• Метод на спускане.

• Метод за разглеждане на остатъци от деление

Множествен метод

реши уравнението 11 x + 2 y = 69

Търсим сума, равна на 69: 55 + 14 = 69 Частно решение на уравнението

х 0 = 5, y 0 = 7

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

реши уравнението 4 x + 7 y = 16

• Нека намерим gcd на числата 4 и 7 с помощта на алгоритъма на Евклид: gcd(4,7) = 1

• Нека изразим числото 1 чрез коефициенти а = 4 и b =7 с помощта на теоремата за линейно разширение на GCD:

GCD ( а, b ) = au+bv .

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

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

при 0 = -1 ∙ 16 = -16

метод на изброяване

реши уравнението 7 x + 12 y = 100

• 7x + 12y = 100
• 7x \u003d 100 - 12г
• 100 - 12 г, кратно на 7

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

100-12u

Метод на освобождаване: 3x+8y=60

Експрес

променлива х

през при

Експрес

променлива х

през T

Отговор:

Преглед:

Метод за разглеждане на остатъци от деление

• Решете уравнението в цели числа 3x - 4y \u003d 1
• 3 x = 4 y + 1
• Лявата страна на уравнението се дели на 3, така че дясната страна трябва да се дели на 3. Разделянето на 3 може да доведе до остатъци 0, 1 и 2.
• Нека разгледаме 3 случая.

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

y=3p+1

Не се дели на 3

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

y=3p+2

Не се дели на 3

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

3x=3(4p+3)

x = 4 p + 3

Отговор:

Дели се на 3

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

Възможности на теорията на LDE Намерете всички цели числа на уравнение х 2 + 5 г 2 + 34z 2 + 2xy - 10xz - 22uz =0

Какво ми даде проектът?

• Получих представа за работата по изследователски проект.
• Запозна се с историята на развитието на диофантовите уравнения и биографията на Диофант.
• Изучава методи за решаване на LDE с две и три неизвестни.
• решава група задачи, които са от практически характер, а също така се срещат на олимпиади, изпити за курса на основното училище
• Придобити умения за решаване на нестандартни задачи.

Мисля, че в бъдеще ще продължа да изучавам диофантовите уравнения от втора степен и методите за тяхното решаване.

СПИСЪК НА ИЗПОЛЗВАНИТЕ ИЗТОЧНИЦИ

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

Министерство на образованието и науката на Руската федерация

Държавно висше учебно заведение

професионално образование

„Тоболска държавна социално-педагогическа академия

тях. DI. Менделеев"

Факултет по математика, TIMOM

Някои диофантови уравнения

Курсова работа

Студентка 3-та година на ФМФ

Матаев Евгений Викторович

Научен ръководител:

Кандидат на физико-математическите науки А. И. Валицкас

Степен: ____________

Тоболск - 2011 г

Въведение……………………………………………………………………........2

§ 1. Линейни диофантови уравнения……………………………………..3

§ 2. Диофантово уравнениех 2 – г 2 = а………………………………….....9

§ 3. Диофантово уравнениех 2 + г 2 = а…………………………………... 12

§ 4. Уравнение x 2 + x + 1 = 3y 2 …………………………………………….. 16

§ 5. Питагорови тройки……………………………………………………….. 19

§ 6. Последната теорема на Ферма……………………………………………………23

Заключение……………………………………………………………….….....29

Библиография .............………………………………………………..30

ВЪВЕДЕНИЕ

Диофантово уравнение е уравнение на формата П(х 1 , … , х н ) = 0 , където лявата страна е полином от променливи х 1 , … , х нс цели коефициенти. Всеки поръчан комплект (u 1 ; … ; u н ) цели числа със свойство П(u 1 , … , u н ) = 0 се нарича (частично) решение на диофантовото уравнение П(х 1 , … , х н ) = 0 . Да се ​​реши диофантово уравнение означава да се намерят всички негови решения, т.е. общото решение на това уравнение.

Нашата цел ще бъде да научим как да намираме решения на някои диофантови уравнения, ако тези решения са налични.

За да направите това, трябва да отговорите на следните въпроси:

а. Диофантовото уравнение винаги ли има решение, намерете условията за съществуване на решение.

b. Има ли алгоритъм, който позволява намирането на решение на диофантово уравнение.

Примери: 1.Диофантово уравнение 5 х – 1 = 0 няма решения.

2. Диофантово уравнение 5 х – 10 = 0 има решение х = 2 , който е единственият.

3. Уравнението вътре х – 8 х 2 = 0 не е Диофантинова.

4. Често уравнения на формата П(х 1 , … , х н ) = Q(х 1 , … , х н ) , където П(х 1 , … , х н ) , Q(х 1 , … , х н ) са полиноми с цели коефициенти, наричани още диофантови. Те могат да бъдат записани във формата П(х 1 , … , х н ) – Q(х 1 , … , х н ) = 0 , което е стандартно за диофантовите уравнения.

5. х 2 – г 2 = ае Диофантово уравнение от втора степен с две неизвестни x и y за всяко цяло число a. Има решения за а = 1 , но няма решения за а = 2 .

§ 1. Линейни диофантови уравнения

Позволявам а 1 , … , а н , СЗ . Типово уравнение а 1 х 1 + … + а н х н = cсе нарича линейно диофантово уравнение с коефициенти а 1 , … , а н , дясна страна c и неизвестен х 1 , … , х н . Ако дясната страна c на линейно диофантиново уравнение е нула, тогава такова диофантово уравнение се нарича хомогенно.

Нашата непосредствена цел е да се научим как да намираме частни и общи решения на линейни диофантови уравнения с две неизвестни. Очевидно всяко хомогенно диофантово уравнение а 1 х 1 + … + а н х н = 0 винаги има конкретно решение (0; … ; 0).

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

Теорема (за съществуването на решение на линейно диофантиново уравнение).Линейно диофантиново уравнение а 1 х 1 + … + а н х н = c, чиито коефициенти не са равни на нула, има решение тогава и само ако GCD(a 1 , … , а н ) | ° С.

Доказателство.Необходимостта от условието е очевидна: GCD(a 1 , … , а н ) | а аз (1 аз н) , така GCD(a 1 , … , а н ) | (а 1 х 1 + … + а н х н ) , което означава, че разделя и

° С = а 1 х 1 + … + а н х н .

Позволявам д= gcd(а 1 , … , а н ) , c =Dt и а 1 u 1 + … + а н u н = д – линейно разширение на най-големия общ делител на числата а 1 , … , а н. Умножавайки двете страни по T, получаваме а 1 (u 1 T) + … + а н (u н T) = Dt = ° С, т.е. цяло число

н-ка (х 1 T; … ; х н T)е решение на първоначалното уравнение с ннеизвестен.

Теоремата е доказана.

Тази теорема дава конструктивен алгоритъм за намиране на конкретни решения на линейни диофантови уравнения.

Примери: 1.Линейно диофантиново уравнение 12x+21y=5няма решение, защото gcd(12, 21) = 3не разделя 5 .

2. Намерете конкретно решение на диофантовото уравнение 12x+21y = 6.

Очевидно сега gcd(12, 21) = 3 | 6, значи решението съществува. Записваме линейното разширение gcd(12, 21) = 3 = 122 + 21(–1). Следователно двойка (2; –1) е конкретно решение на уравнението 12x+21y = 3, и двойка (4; –2) е конкретно решение на първоначалното уравнение 12x+21y = 6.

3. Намерете конкретно решение на линейно уравнение 12x + 21y - 2z = 5.

защото (12, 21, –2) = ((12, 21), –2) = (3, –2) = 1 | 5 , тогава решението съществува. След доказателството на теоремата първо намираме решение на уравнението (12.21)x–2y=5, и след това, замествайки линейното разширение на най-големия общ делител от предишната задача, получаваме решението на първоначалното уравнение.

За решаване на уравнението 3x - 2y = 5запишете линейното разширение gcd(3, -2) = 1 = 31 - 21очевидно. И така, няколко числа (1; 1) е решение на уравнението 3 х – 2 г = 1 , и двойка (5; 5) е конкретно решение на диофантовото уравнение 3x - 2y = 5.

Така, (12, 21)5 – 25 = 5 . Замествайки тук предварително намереното линейно разширение (12, 21) = 3 = 122 + 21(–1) , получаваме (122+21(–1))5 – 25 = 5 , или 1210 + 21(–5) – 25 = 5 , т.е. тройка от цели числа (10; –5; 5) е конкретно решение на първоначалното диофантиново уравнение 12x + 21y - 2z = 5.

Теорема (за структурата на общото решение на линейно диофантиново уравнение).За линейно диофантиново уравнение а 1 х 1 + … + а н х н = cследните твърдения са верни:

(1) ако = (ф 1 ; … ; u н ), = (v 1 ; … ; v н ) са неговите конкретни решения, след това разликата (ф 1 –v 1 ; … ; u н –v н ) е частно решение на съответното хомогенно уравнение а 1 х 1 + … + а н х н = 0 ,

(2) набор от конкретни решения на линейното диофантиново хомогенно уравнение а 1 х 1 + … + а н х н = 0 затворен при събиране, изваждане и умножение с цели числа,

(3) ако Ме общото решение на даденото линейно диофантиново уравнение, и Ле общото решение на съответното хомогенно диофантиново уравнение, тогава за всяко конкретно решение = (ф 1 ; … ; u н ) на първоначалното уравнение, равенството M = +L .

Доказателство.Изваждане на равенство а 1 v 1 + … + а н v н = ° С от равенството а 1 u 1 + … +a н u н = c, получаваме а 1 (ф 1 –v 1 ) + … + а н (ф н –v н ) = 0 , т.е. множеството

(ф 1 –v 1 ; … ; u н –v н ) е частно решение на линейното хомогенно диофантиново уравнение а 1 х 1 + … + а н х н = 0 . По този начин е доказано, че

= (u 1 ; … ; u н ), = (v 1 ; … ; v н ) МЛ .

Това доказва твърдение (1).

Твърдение (2) се доказва по подобен начин:

, Л z З Л z Л .

За да докажем (3), първо отбелязваме, че М+Л. Това следва от предишното: М+Л .

Обратно, ако = (л 1 ; … ; л н ) L и = (u 1 ; … ; u н ) М, след това М:

а 1 (ф 1 + л 1 )+ …+a н (ф н + л н ) = (а 1 u 1 + … + а н u н )+(a 1 л 1 + … + а н л н ) = c + 0 = c.

По този начин, + ЛМ, и в крайна сметка M = +L .

Теоремата е доказана.

Доказаната теорема има ясен геометричен смисъл. Ако разгледаме линейното уравнение а 1 х 1 + … + а н х н = c, където х аз Р, то, както е известно от геометрията, определя в пространството Р нхиперравнина, получена от равнината Л с хомогенно уравнение а 1 х 1 + … +а н х н =0 преминаване през началото на координатите чрез изместване с някакъв вектор Р н. Виж повърхност + Лнаричан още линеен колектор с направляващо пространство Ли вектор на изместване . Така се доказва, че общото решение Мдиофантиново уравнение а 1 х 1 + … + а н х н = cсе състои от всички точки на някакво линейно многообразие с цели координати. В този случай координатите на вектора на изместване също са цели числа, а множеството Лрешения на хомогенното диофантово уравнение а 1 х 1 + … + а н х н = 0 се състои от всички точки в направляващото пространство с цели координати. Поради тази причина често се казва, че наборът от решения на произволно диофантиново уравнение образува линейно многообразие с вектор на изместване и водещо пространство Л.

Пример:за диофантовото уравнение x - y \u003d 1общо решение Мима формата (1+y; y), където yЗ, конкретното му решение = (1; 0) и общото решение Лхомогенно уравнение x – y = 0ще бъдат записани във формуляра (y; y), където приЗ. Така можем да начертаем следната картина, в която решенията на първоначалното диофантиново уравнение и съответното хомогенно диофантиново уравнение са показани с дебели точки в линейното многообразие Ми пространство Лсъответно.

2. Намерете общото решение на диофантовото уравнение 12x + 21y - 2z = 5.

Частно решение (10; –5; 5) това уравнение беше намерено по-рано, намираме общото решение на хомогенното уравнение 12x + 21y - 2z = 0, еквивалентно на диофантовото уравнение 12 х + 21 г = 2 z.

За да бъде разрешимо това уравнение, е необходимо и достатъчно условието gcd(12, 21) = 3 | 2z,тези. 3 | zили z = 3tза някакво цяло число T. Намаляване на двете части до 3 , получаваме 4x + 7y = 2t. Частно решение (2; –1) на диофантовото уравнение 4x+7y= 1 намерени в предишния пример. Ето защо (4t ; -2t)е конкретно решение на уравнението 4x + 7y = 2tза всякакви

T З. Общо решение на съответното хомогенно уравнение

(7 u ; –4 u) вече намерени. Така общото решение на уравнението 4x + 7y = 2tизглежда като: (4t + 7u; -2т - 4u) , и общото решение на хомогенното уравнение 12x + 21y - 2z = 0ще бъде написана така:

(4t + 7u; -2т - 4u; 3т).

Лесно е да се провери, че този резултат съответства на теоремата, посочена по-горе, без доказателство за решения на хомогенното диофантово уравнение а 1 х 1 + … + а н х н = 0 : ако P = ,тогава Ри

(u; T) Пе общото решение на разглежданото хомогенно уравнение.

И така, общото решение на Диофантовото уравнение 12x + 21y - 2z = 5изглежда така: (10 + 4t + 7u; –5 – 2t – 4u; 5+3t).

3. На примера на предишното уравнение ние илюстрираме друг метод за решаване на диофантови уравнения с много неизвестни, който се състои в последователно намаляване на максималната стойност на модулите на неговите коефициенти.

12x + 21y - 2z = 5 12x + (102 + 1)y - 2z = 5

12x + y - 2(z - 10y) = 5

По този начин общото решение на разглежданото уравнение може да бъде написано, както следва: (x; 5 - 12x + 2u; 50 - 120x + 21u), където x, uса произволни цели числа параметри.

§ 2. Диофантово уравнениех 2 – г 2 = а

Примери: 1.При а = 0 получаваме безкраен брой решения: х = гили х = – гза всеки г З.

2. При а = 1 ние имаме х 2 – г 2 = 1 (х + г)(х – г) = 1 . Така числото 1 се разлага на произведението на два целочислени множителя х + ги х – г(важно, че х, г- цял!). Тъй като броят 1 само две разширения в произведението на цели числа 1 = 11 и 1 = (–1)(–1) , получаваме две възможности: .

3. За а = 2 ние имаме х 2 – г 2 = 2 (х + г)(х – г) = 2. Продължавайки подобно на предишния, разглеждаме разширенията

2=12=21=(–1)(–2)=(–2)(–1), съставяме системи:, които за разлика от предишния пример нямат решения. Така че няма решения за разглежданото диофантиново уравнение х 2 – г 2 = 2.

4. Предходните разсъждения водят до някои изводи. Решения на уравнения х 2 – г 2 = а са в процес на разлагане а = кмв произведението на цели числа от системата . Тази система има цели решения, ако и само ако к + м и к – м са четни, т.е. когато числата к и м еднакъв паритет (едновременно четен или нечетен). По този начин диофантовото уравнение x 2 – y 2 = a има решение тогава и само ако a може да се разложи в произведение на два целочислени множителя с еднаква четност. Остава само да се намерят всички такива.

Теорема (за уравнениетох 2 – г 2 = а ). (1) Уравнение х 2 – г 2 = 0 има безкраен брой решения .

(2) Всяко решение на уравнението се получава като , където а = кме разлагането на числото a в произведението на два целочислени множителя с еднаква четност.

(3) Уравнение х 2 – г 2 = аима решение тогава и само ако а 2 (мод 4).

Доказателство.(1) вече е доказано.

(2) вече е доказано.

(3) () Нека първо диофантовото уравнение х 2 – г 2 = а има решение. Нека докажем това а 2 (мод 4) . Ако а = км е разширяването в произведение на цели числа с еднакъв паритет, тогава за четно ки мние имаме к = 2 л, м = 2 ни а = км = 4 вътре 0 (мод 4) . В случай на странно к, мтяхната работа асъщо странно, разлика а – 2 нечетно и неделимо на 4 , т.е. отново

а 2 (мод 4).

() Ако сега а 2 (мод 4) , тогава можем да конструираме решение на уравнението х 2 – г 2 = а. Наистина, ако a е странно, тогава а = 1 ае разлагане на произведение на нечетни цели числа, така че е решението на диофантовото уравнение. Ако a е четно, тогава с оглед на а 2 (мод 4) разбираме това 4 | а, а = 4 b = 2(2 b) е разлагане на произведение на четни цели числа, така че е решението на диофантовото уравнение.

Теоремата е доказана.

Примери: 1.Диофантово уравнение х 2 – г 2 = 2012 няма решения, тъй като 2010 = 4502 + 2 2 (мод 4).

2. Диофантово уравнение х 2 – г 2 = 2011 има решения, т.к

2011 3 (мод 4). Имаме очевидни разширения

2011 = 12011 = 20111 = (–1)(–2011) = (–2011)(–1),

за всяка от които намираме решения (всяка комбинация от знаци). Други решения няма, т.к номер 2011 просто (?!).

§ 3. Диофантово уравнениех 2 + г 2 = а

Примери: 1. 0 = 0 2 + 0 2 , 1 = 0 2 + 1 2 , к 2 = 0 2 + к 2 . По този начин е очевидно, че всеки квадрат може тривиално да бъде представен като сбор от два квадрата.

2. 2 = 1 2 + 1 2 , 5 = 1 2 + 2 2 , 8 = 2 2 + 2 2 , 10 = 1 2 + 3 2 , 13 = 2 2 + 3 2 , 17 = 1 2 + 4 2 , 18 = 3 2 + 3 2 , 20 = 2 2 + 4 2 , …

3. Няма решения за а = 3, 6 = 23, 7, 11, 12 = 2 2 3, 14 = 27, 15 = 35, 19, 21 = 37, 22 = 211, 23, 24 = 32 3 , …

Анализът на горните резултати може да подскаже, че липсата на решения е свързана по някакъв начин с простите числа на формата

4 н+3 присъства в факторизирането на числа, които не могат да бъдат представени като суми от два квадрата.

Теорема (за представянето на естествени числа чрез суми от два квадрата).Естествено число a може да бъде представено като сбор от два квадрата тогава и само ако в неговото канонично разширение прости числа от вида 4 н + 3 имат четни показатели.

Доказателство.Първо доказваме, че ако естествено число a може да бъде представено като сбор от два квадрата, тогава в неговото канонично разширение всички прости числа от вида 4 н + 3 трябва да има четни показатели. Да предположим, противно на доказаното, че а= p 2 к +1 b = х 2 + г 2 , където

R -просто число на формата 4 н+3 и b стр. Представете си числа хи прикато

x =Дз, г = Dt, къдетод= gcd(х, г) = p с w, стр w; z, T, с н 0 . Тогава получаваме равенството Р 2 к +1 b = д 2 (z 2 + T 2 ) = p 2 с w 2 (z 2 + T 2 ) , т.е. Р 2( к – с )+1 b = w 2 (z 2 + T 2 ) . От лявата страна на равенството има p (нечетната степен не е равна на нула), което означава, че един от множителите от дясната страна се дели на простото число p. Тъй като стр w, тогава p | (z 2 + T 2 ) , където числата z, T взаимно прости. Това противоречи на следващата лема (?!).

Лема (за делимостта на сумата от два квадрата на просто число от формата

4 н + 3 ). Ако просто число p = 4н+3 дели сумата от квадратите на две естествени числа, след което дели всяко от тези числа.

Доказателство.От обратното. Позволявам х 2 + г 2 0(мод стр) , но х0(мод стр) или г 0 (мод стр) . Тъй като хи гса симетрични, те могат да бъдат разменени, така че можем да приемем, че х стр.

Лема (за обратимостта по модулстр ). За всяко цяло число х, неделимо на просто число стр, има обратен елемент по модул стр – такова цяло число 1 u < стр, Какво xi 1 (мод стр).

Доказателство.Номер хсъвместно с стр, така че можем да напишем линейно разширение GCD(х, стр) = 1 = xi + pv (u, v З) . Това е ясно xi1(modp) , т.е. u- обратен елемент към хпо модул стр. Ако uне удовлетворява ограничението 1 u < стр, след това разделяне uс включен остатък стр, получаваме остатъка r u (мод стр) , за което xr xi 1 (мод стр) и 0 r < стр.

Лема за обратимост по модул стрдоказано.

Умножаващо сравнение х 2 + г 2 0 (мод стр) на квадрат u 2 обратен елемент към хпо модул стр, получаваме 0 = 0u 2 х 2 u 2 +y 2 u 2 = (xu) 2 + (ю) 2 1+т 2 (mod p).

Така че за T = юсравнението е направено T 2 –1 (мод стр) , което довеждаме до противоречие. Това е ясно T стр: в противен случай T 0 (мод стр) и 0 T 2 –1 (мод стр) , което е невъзможно. По теоремата на Ферма имаме T стр –1 1 (мод стр), който заедно с T 2 –1 (мод стр) и стр = 4 н + 3 води до противоречие:

1 т p–1 = t 4n+3–1 = t 2(2n+1) = (т 2 ) 2n+1 (–1) 2n+1 = –1 (modp).

Полученото противоречие показва, че предположението за х 0 (мод стр) не беше правилно.

Лема за делимост на сбора от два квадрата на просто число 4 н+3 доказано.

Така се доказва, че числото, чието канонично разлагане включва просто число стр = 4 н + 3 на нечетна степен, не може да се представи като сбор от два квадрата.

Нека сега докажем, че всяко число, в чието канонично разширение простите числа стр = 4 н + 3 участват само в четни степени, представими като сбор от два квадрата.

Идеята на доказателството се основава на следната идентичност:

(а 2 +б 2 )(° С 2 +г 2 ) = (ac – bd) 2 + (реклама + bc) 2 ,

което може да се получи от добре известното свойство на модула на комплексните числа – модулът на произведението е равен на произведението на модулите. Наистина ли,

| z|| T| = | zt| | а + би|| ° С + ди| = |(а + би)(° С + ди)|

|a+bi| 2 |c + di| 2 = |(ac – bd) + (ad + bc)i| 2

(а 2 +б 2 )(° С 2 +г 2 ) = (ac – bd) 2 + (реклама + bc) 2 .

От тази идентичност следва, че ако две числа u, v могат да бъдат представени като сбор от два квадрата: u = х 2 + г 2 , v = z 2 + T 2 , тогава техният продукт uv може също да бъде представен като сбор от два квадрата: UV = (xz – yt) 2 + (xt + yz) 2 .

Всякакви естествено число а > 1 може да се запише във формата а= p 1 … Р к м 2 , където Р азса по двойки различни прости числа, м н . За да направите това, достатъчно е да намерите каноничното разлагане , запишете всяка степен на формата rпод формата на квадрат (r) 2 за дори = 2, или във формата r = r(r) 2 за странно = 2 + 1 , и след това групирайте отделно квадратите и останалите единични прости числа. Например,

29250 = 23 2 5 3 13 = 2513(35) 2 , м = 15.

Номер м 2 има тривиално представяне като сбор от два квадрата: м 2 = 0 2 + м 2 . Ако докажем представимостта като сбор от два квадрата на всички прости числа Р аз (1 аз к) , тогава с помощта на идентичността ще се получи и представянето на числото a. По условие, сред числата Р 1 , … , Р к може само да се срещне 2 = 1 2 + 1 2 и прости числа на формата 4 н + 1 . Така остава да се получи представяне като сбор от два квадрата на просто число p = 4m + 1. Отделяме това твърдение в отделна теорема (вижте по-долу)

Например за а = 29250 = 2513(15) 2 последователно получаваме:

2 = 1 2 + 1 2 , 5 = 1 2 + 2 2 , 13 = 2 2 + 3 2 ,

25 = (11 – 12) 2 + (12 + 11) 2 = 1 2 + 3 2 ,

2513 = (12 – 33) 2 + (13 + 32) 2 = 7 2 + 9 2 ,

29250 = 2513(15) 2 = (715) 2 + (915) 2 = 105 2 + 135 2 .

Теоремата е доказана.

§ 4. Уравнениеx + x + 1 = 3y

Нека сега се заемем с уравнението x+x+1=Zu.То вече има своята история. През 1950 г. Р. Облат предполага, че освен решаване

х=y=1. то няма други решения в естествени числа x, yкъдето x е нечетно число. През същата година Т. Нагел посочи решението х= 313, y = 181.Метод, подобен на горния за уравнението x+x-2y=0, ще ни позволи да определим всички решения на уравнението х+x+1=3y (1)

в естествени числа х, при.Нека се преструваме, че (x, y)е решение на уравнение (1) в естествени числа и х > 1. Лесно се вижда, че уравнение (18) няма решения в естествени числа х, г, където x = 2, 3. 4, 5, 6, 7, 8, 9;така и трябва да бъде х10.

Нека покажем това 12г<7 х+3, 7y>4х+ 2. 4y > 2х+1 . (2)

Ако беше 12г> 7x+3, щяхме да имаме 144г> 49 х+42 х+9 . и тъй като с оглед на (18), 144y= 48х+ 48 х + 48 , тогава би било х< 6 х +3 9, от къде

(x-z)< 48 и следователно предвид това х> 10, 7 < 148 , което е невъзможно. Така първото от неравенствата (2) е доказано.

Ако беше 7 г< 4 х+2 , щяхме да имаме 49 г< 16 х+ 16 х+4 и тъй като с оглед на (1), 16 х+ 16 х+ 16 = 48 г, тогава би било 49 г< 48u- 12, което е невъзможно. Така второто от неравенствата (2) е доказано, от което пряко следва третото. Така че неравенствата (2) са верни.

Да сложим сега

w\u003d 7x - 12y + 3,ч = -4 х+ 7u-2. (3)

Въз основа на (2) намираме това w > 0 , ч > 0 и Х -w=3(4 г-2 х-1)>0 и следователно, w<х . Съгласно (3) имаме w 2 + w+1=3 ч 2 откъдето, с оглед на (1), приемаме g(x, y) = (7x - 12y + 3, -4x + 7y -2).

Така че можем да кажем това въз основа на всяко решение (x, y)уравнения (1) в естествени числа, където х > 1, получаваме ново решение (w, ч) = g(x, y)уравнения (1) в естествени числа w, чкъдето w < х (и следователно решението в по-малки естествени числа). Следователно, действайки както по-горе, намираме, че за всяко решение на уравнение (1) в естествени числа x, y, където х > 1, има естествено число n такова, че g(x, y) = (l, 1).

След като прие f(x, y) = (7х+12y + 3, 4х+ 7y + 2), (4) можем лесно да намерим това f(g(x, y)) = (x, y)и следователно (х, г) = f(1,1) От друга страна, лесно е да се провери дали ако (x, y)е решение на уравнение (1) в естествени числа, тогава f(х, г) има и решение на уравнение (1) в естествени числа (съответно по-големи от хи при).

След като прие x=y=1(x, y) = f(1, 1)за н=2,3,…..,

получаваме последователността { х, г} за н= 1, 2,….., съдържащ всички решения на уравнение (1) в естествени числа и само такива решения.

Тук имаме (Х,г)= f(1,1)= f(x, y),следователно, поради (4), получаваме

х=7х+12y+3,г=4x+7y+2 (5) (н=1, 2, ...)

Формули, които ви позволяват последователно да определяте всички решения (x, y)уравнения (1) в естествени числа. По този начин лесно намираме решения (1,1),(22,13),(313,181),.(4366,2521),(60817,35113),..

Очевидно има безкраен брой от тези решения. От равенствата

x=y=1и (4) чрез индукция лесно намираме, че числата хс нечетни индекси са нечетни, с четни индекси са четни, а числата гсъщност странно за н = 1, 2, ... Да се ​​получат всички решения на уравнение (1) в цели числа x, y, както е лесно да се докаже, би следвало вече получените решения (x, y)присъединяване (x, -y)и (-x-1,±y)за н=1, 2, .. .

Така че тук имаме, например, повече такива решения: (-2,1) (-23,13), (-314,181). А. Роткевич отбеляза, че от всички решения на уравнение (1) в естествени числа х > 1и y може да получи всички решения на уравнението (z+1)-z=г (6)

в естествени числа z, y.Наистина, да предположим, че естествените числа z, y удовлетворяват уравнение (5). Поставяне x=3z+l, получаваме, както е лесно да се провери, естествени числа х > 1и приудовлетворяващи уравнение (1).

От друга страна, ако естествените числа х > 1и приудовлетворяват уравнение (1), тогава имаме, както е лесно да се провери, (x-1)= 3(y-x), откъдето следва, че числото (естествено) х-1разделена на 3 , Следователно х-1=3 z, където zе естествено число, а равенството 3z=y-х=y3z-1 , което доказва, че числата zи приудовлетворяват уравнение (6). Така въз основа на решенията (22,13),(313,181), (4366,2521) уравнение (1), получаваме решения (7,13),(104,181),(1455,2521) уравнения (6). Тук също отбелязваме, че ако естествените числа z, yудовлетворяват уравнение (6), доказано е, че прие сумата от два последователни квадрата, например 13=2+3,181=9+10, 2521=35+ 36 . По подобен начин, както преди за уравнение (1), можем да намерим всички решения на уравнението х+(х+1)= гв естествени числа x, y, като за x > 3 g (x. y) \u003d (3x -2y + 1, 3y - 4x - 2)и за х> 1 f(x, y) = (3х+ 2y+l, 4x + Zu + 2),което води до формулата ( x, y)f(3,5) и до заключението, че всички решения на уравнение (6) в естествени числа x, y се съдържат в редицата { х, г} за н= 1, 2,…., където x=3, y=5 их=3 х+2 г+1 . г = 4 х+3 г+2 (н=1, 2, ...). Например, x \u003d 3 3 + 2 5 + 1 \u003d 20, y = 4 3 + Z 5 + 2 \u003d 29;х=119, y=169:х=69b, y=985;х=4059, y=5741.

Геометричният смисъл на разглежданото уравнение е, че то дава всички питагорови триъгълници (правоъгълни с естествени страни), чиито катети се изразяват с последователни естествени числа. Има безкрайно много такива триъгълници (*).

Уравнението е х+(х+1)= г, е доказано, че няма решения в естествени числа x, y.

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

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

• Пример #1 (прост)
• Пример #2 (труден)

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

• Проблем за пилета, зайци и техните лапи
• Задачата на продавачката и промяната

Според прегледите на sibms, истински препъни камък в училищен курсматематиката не само за учениците, но и за родителите стават диофантови уравнения. Какво е това и как да ги разрешите правилно? Аелита Бекешева, учител по математика в Горностайския образователен център, и Юрий Шанко, кандидат на физико-математическите науки, ни помогнаха да го разберем.

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

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

Първият, който измисли как да напише уравнението, беше прекрасният учен Диофант от Александрия. Александрия е голям културен, търговски и научен центърдревен свят. Този град все още съществува, той се намира на средиземноморския бряг на Египет.

Диофант е живял, очевидно, през 3-ти век от н.е. и е последният велик математик от древността. До нас са достигнали две негови произведения - "Аритметика" (от тринадесет книги са оцелели шест) и "За многоъгълните числа" (в откъси). Работата на Диофант има голямо влияние върху развитието на алгебрата, математическия анализ и теорията на числата.

Но знаете нещо за диофантовите уравнения...

Всеки знае диофантовите уравнения! Това са пъзели за ученици от началното училище, които се решават чрез подбор.

” Например „колко различни начиниможеш ли да платиш сладолед на стойност 96 копейки, ако имаш само копейки и монети от пет копейки?“

Ако дадем диофантовото уравнение обща дефиниция, тогава можем да кажем, че това е алгебрично уравнение с допълнително условие: всички негови решения трябва да бъдат цели числа (и в общия случай също рационални).

” Често майките (особено тези, които са завършили училище при развития социализъм) смятат, че основната цел на такива задачи е да научат децата да плащат ресто за сладолед. И така, когато са искрено убедени, че поставянето на дреболии на купчини е минало, любимият им седмокласник (или осмокласник) идва с неочакван въпрос: „Мамо, как да реша това?“ и представя уравнение с две променливи. Преди това в училищния курс нямаше такива проблеми (всички помним, че трябва да има толкова уравнения, колкото променливи), така че майката, която не е математик, често изпада в ступор. Но това е същият проблем за промяната и сладоледа, само че е написано общ изглед!

Между другото, защо изведнъж се връщат при нея в седми клас? Всичко е просто: целта на изучаването на диофантовите уравнения е да се дадат основите на теорията на целите числа, която е доразвита както в математиката, така и в компютърните науки и програмирането. Диофантовите уравнения често се срещат сред задачите от част "В" на единния държавен изпит. Трудността, на първо място, е, че има много методи за решение, от които завършилият трябва да избере един правилен. Въпреки това, линейните диофантови уравнения ax + by = c могат да бъдат решени относително лесно с помощта на специални алгоритми.

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

Изучаването на диофантовите уравнения започва в курса по алгебра за напреднали от 7. клас. В учебника Ю.Н. Макаричева, Н.Г. Mindyuk, дадени са някои задачи и уравнения, които се решават с помощта на Алгоритъм на Евклиди метод на груба сила, - казва Аелита Бекешева.- По-късно, в 8 - 9 клас, когато вече разглеждаме уравнения в цели числа от по-високи порядъци, показваме на учениците метод на факторизацияи допълнителен анализ на решението на това уравнение, метод за оценка. Представяме ви с метода за избор на пълен квадрат. Когато изучаваме свойствата на простите числа, въвеждаме малката теорема на Ферма, една от основните теореми в теорията на решенията на уравнения в цели числа. На по-високо ниво това запознанство продължава в 10-11 клас. В същото време привличаме децата към изучаването и прилагането на теорията на „сравненията по модул“, разработваме алгоритмите, с които се запознахме в 7-9 клас. Много добре, този материал е разписан в учебника на A.G. Мордкович "Алгебра и началото на анализа, 10 клас" и G.V. Дорофеев "Математика" за 10 клас.

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

Самият метод на Евклид се отнася до друга математическа задача - намирането на най-големия общ делител: вместо първоначалната двойка числа се записва нова двойка - по-малко число и разликата между по-малкото и по-голямото число от първоначалната двойка. Това действие продължава, докато числата в двойката са равни - това ще бъде най-големият общ множител. Разновидност на алгоритъма се използва и при решаването на диофантови уравнения - сега ние заедно с Юрий ШанкоНека използваме пример, за да покажем как се решават задачи "за монети".

Разглеждаме линейното диофантово уравнение брадва + от = c,където a, b, c, x и y са цели числа. Както можете да видите, едно уравнение съдържа две променливи. Но, както си спомняте, имаме нужда само от цели числа, което опростява нещата - могат да бъдат намерени двойки числа, за които уравнението е вярно.

Диофантовите уравнения обаче не винаги имат решения. Пример: 4x + 14y = 5. Няма решения, защото от лявата страна на уравнението за всяко цяло число x и y ще се получи четно число, а 5 е нечетно число. Този пример може да се обобщи. Ако в уравнението брадва + от = 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; х=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) ⇒ х=5z-114. Обърнете внимание, че променливата z не може да бъде по-малка от 23 (в противен случай x, броят на монетите от две рубли, ще бъде отрицателен) и по-голяма от 28 (в противен случай y, броят на монетите от пет рубли, ще бъде отрицателен). Всички стойности от 23 до 28 ни подхождат.

Отговор

Шест начина.

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

Общинско бюджетно учебно заведение

средно училище №1

Павлово.

Изследователска работа

Методи за решаване на диофантови уравнения.

Катедра: Физико-математически

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

Завършено:

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

Научен ръководител:

учител по математика

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

Павлово

2013

Съдържание

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

II Литературен преглед………………………………………………………………..5

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

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

V Списък с литература…………………………………………………………………………………………………………………………… ……………………………………………………………………………………………………………………………………… ………………………………………………………………………………………………………………….

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

Въведение.

През 2011-2012 г. изпълнявах изследователска работана тема: „Решаване на уравнения в Древна Гърцияи Индия." Докато работех върху него, се запознах с трудовете на Диофант от Александрия и Мохамед ал-Хорезми. В предишната си работа разгледах някои методи за решаване на уравнения от първа степен с две неизвестни, запознах се с някои стари задачи, които водят до решаването на уравнения от първа степен с две неизвестни.

Мохамед Бен Муса ал-Хорезми, или Мохамед, синът на Мойсей от Хорезм, който е член на „дома на мъдростта“ в Иран, написа книга около 820 г. от нашата хронология, където учи да решава прости и сложни въпроси на аритметиката които са необходими на хората при делба на наследство, съставяне на завещания, делба на имоти и съдебни дела, в търговията, всякакви сделки. С името на ал-Хорезми се свързват понятията "алгебра", "арабски цифри", "алгоритъм". Той отдели алгебрата от геометрията, направи голям принос в математиката на ислямското средновековие. Мохамед ал-Хорезми е бил известен и уважаван както приживе, така и след смъртта си.

Но исках да знам повече за Диофант. И темата на моето изследване тази година е: Методи за решаване на диофантови уравнения»

Диофант от Александрия е един от най-особените древногръцки математици, чиито трудове са голямо значениеза алгебра и теория на числата. От съчиненията на Диофант най-важна е „Аритметика“, от 13-те книги на която до наши дни са оцелели само 6. Оцелелите книги съдържат 189 задачи с решения. Първата книга съдържа задачи, които водят до определени уравнения от първа и втора степен. Останалите пет книги съдържат предимно неопределени уравнения (неопределените уравнения се наричат ​​уравнения, съдържащи повече от едно неизвестно). Тези книги все още нямат систематична теория на неопределените уравнения, методите за решаване варират от случай на случай. Диофант се задоволява с едно решение, цяло или частично, стига да е положително. Но методите за решаване на неопределени уравнения представляват основния принос на Диофант в математиката. В символиката на Диофант имаше само един знак за неизвестното. При решаването на неопределени уравнения той използва произволни числа като няколко неизвестни, вместо които могат да бъдат взети други, което запазва природата на общността на неговите решения.

Целта на моята работа:

1. Продължете запознаването с диофантовите уравнения.

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

3. Проучете възможността за използване на диофантови уравнения за решаване на някои практически проблеми.

II. Литературен преглед.

При написването на работата използвах следната литература:

Използвах информация за Диофант и ал-Хорезми.

Книгата е посветена на методите на Диофант при решаване на неопределени уравнения. Разказва за живота на самия Диофант. Тази информация се използва от мен в работата ми.

Книгата разказва за историята на алгебрата от древни времена. Използвал съм информация за теорията на уравненията от древността.

Тази книга съдържа около 200 статии за основните понятия на математиката и нейните приложения. Използвах материалите на статиите "Алгебра", "Уравнения", "Диофантови уравнения"

От книгата са взети текстове на задачи за практическо приложение.

По темата използвах сайта:

http :// en . уикипедия . орг (информация за ал-Хорезми и Диофант. За методите за решаване на диофантови уравнения).

Главна част

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

(1)

Да разгледаме задачата.

Задача 1. В клетката е х фазани и призайци. Колко фазани и зайци има в клетка, ако общият брой на краката е 62.

Общ бройкраката могат да бъдат записани с помощта на уравнението 2x + 4y \u003d 62 (2)

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

Линейно уравнение с две променливи е уравнение под формата ax + by \u003d c, където x и y са променливи, a, b и c са някои числа.

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

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

Всяко уравнение с две променливи съответства на множеството от неговите решения, т.е. множеството, състоящо се от всички двойки числа (a, b), замествайки които в уравнението, се получава истинско равенство. В този случай, разбира се, ако множествата X и Y са зададени предварително, който може да приеме неизвестни x и y, тогава трябва да вземете само такива двойки (a, b), за които a принадлежи на X и b принадлежи на Y .

Няколко числа ( а, б) може да бъде представена на равнината от точката M, която има координатите аи b, M \u003d M (a, b). Разглеждайки изображенията на всички точки от набора от решения на уравнение с две неизвестни, получаваме определено подмножество на равнината. Нарича се графика на уравнението .

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

Две уравнения с две променливи, които имат еднакви решения, се наричат ​​еквивалентни.

Например уравненията x + 2y = 5 и 3x + 6y = 15 са еквивалентни - всяка двойка числа, която удовлетворява едно от тези уравнения, удовлетворява и второто.

Уравненията с две променливи имат същите свойства като уравненията с една променлива:

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

2) ако и двете части на уравнението се умножат или разделят на едно и също ненулево число, тогава се получава уравнение, което е еквивалентно на даденото.

Има няколко начина за решаване на диофантови уравнения:

Метод на избор

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

Използване на продължителен изстрел

Метод на разпръскване (смилане).

Използване на езика за програмиране Pascal

В работата си изследвах методи - изброяване на опции и дисперсия (смилане)

Като се има предвид начинът за изброяване на опциите, е необходимо да се вземе предвид броят на възможните решения на уравнението. Например, този метод може да се приложи чрез решаване на следния проблем:

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

Решение.

Позволявам хчасове, които е работил за една седмица, тогава 10xР. платиха му, но се счупи приплочи и се изважда от него 2 гР. Имаме уравнението 10x - 2y \u003d 180, и х по-малко или равно на 21. Получаваме: 5x-y=90, 5x=90+y, x=18+y:5.

защото х цяло число, тогава притрябва да се дели равномерно на 5, за да получим цяло число от дясната страна. Случаите са четири

y=0, x=18, т.е. решението е двойката - (18, 0);

y=5, x=19, (19, 5);

y=10, x=20, (20, 10);

y=15, x=21, (21, 15).

Реших този проблем с помощта на метода на изброяване на опциите. Отговорът съдържа четири възможни варианта. Опитах се да разреша още няколко проблема по този начин.

Задача 3. Сумата от 23 рубли е направена от монети от две и пет рубли. Колко от тези монети от две рубли има?

Решение.

Позволявам х - броят на монетите от две рубли, y -броя на монетите от пет рубли. Нека съставим и решим уравнението: 2x+5y=23; 2x=23–5y; x \u003d (23 - 5y): 2; x \u003d (22 + 1 - 5y): 2, разделяме 22 на 2 и (1 - 5y) на 2 член по член, получаваме: x \u003d 11 + (1 - 5y): 2.

защото х и г естествени числа според условието на задачата, то лявата страна на уравнението е естествено число, което означава, че дясната страна също трябва да е естествено число. Освен това, за да се получи естествено число от дясната страна, е необходимо изразът (1 - 5y) да се дели изцяло на 2. Нека изброим вариантите.

y = 1, x = 9, т.е. може да има 9 монети от две рубли;

y=2, докато изразът (1 - 5y) не се дели на 2;

y=3, x=4, т.е. може да има 4 монети от две рубли;

когато y е по-голямо или равно на 4, x не е естествено число.

Така отговорът в задачата е следният: сред монетите има 9 или 4 монети от две рубли.

Задача 4. Шехерезада разказва приказките си на великия владетел. Общо тя трябва да разкаже 1001 приказки. Колко нощи ще са необходими на Шехерезада, за да разкаже всичките си приказки, ако х нощи тя ще разказва 3 приказки, а останалите приказки 5 за принощувки

Решение.

Разказвачът се нуждае от x + y нощувки , където x и y - естествени корени на уравнението 3x + 5y \u003d 1001

x \u003d (1001 - 5y): 3; защото хе естествено число, тогава дясната страна на равенството също трябва да съдържа естествено число, което означава, че изразът (1001 - 5y) трябва напълно да се дели на 3.

Нека да разгледаме опциите.

y=1, 1001 - 5y=1001-5= 996, 996 се дели на 3, следователно x=332; решение(332;1);

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

y=3, 1001 - 15 = 986; 986 не се дели на 3;

y \u003d 4, 1001 - 20 \u003d 981, 981 се дели на 3, следователно x \u003d 327, решението е (327; 4) и др.

Има 67 двойки възможни корени в тази задача, не показах всички решения на тази задача, защото отнема много време.

Уравнението брадва + от = ° С (1) в горните проблеми реших метода на изброяване на опциите. Разбрах за себе си, че методът на изброяване на опциите не винаги е ефективен за решаването на този проблем, тъй като отнема значително време, за да се намерят всички решения на уравнението. И според мен в момента е без значение.

Затова реших проблема с Шехерезада, използвайки метода на дисперсия (смилане).

Методът на разсейване е общ метод за решаване на неопределени уравнения от първа степен с цели коефициенти в цели числа.

И така, нека решим проблема за Шехерезада по метода на разсейване:

Нека се обърнем към уравнението 3x + 5y = 1001.

Нека го пренапишем по различен начин: 3x = 1001 - 5y; 3x \u003d 1001 - 2y - 3y;

x = -y +
и обозначават х л= y + х

В резултат на това уравнението ще приеме формата 3x 1 = 1001 - 2y или

y = - х л
.

Ако отново заменим y 1 \u003d y + x 1, тогава стигаме до уравнението

x 1 + 2y 1 \u003d 1001. Обърнете внимание, че коефициентите за неизвестните са намалели - те са нарязани.

Тук коефициентът при x 1 е равен на 1 и следователно за всяко цяло число y 1 \u003d t числото x 1 също е цяло число. Остава да изразим оригиналните променливи чрез t :

x 1 \u003d 1001 - 2 t, следователно, y \u003d - 1001 + 3 t, и x \u003d 2002 - 5 t. И така, получаваме безкрайна последователност (2002 – 5 t , – 1001 + 3 t ) от цели числа . Появата на формулите за намиране на стойностите на променливите се различава от решенията, получени по-рано, но като се вземе предвид условието на проблема, корените са същите. И така, двойката (332;1) се получава при t =334.

Според мен този метод е не само по-удобен (има алгоритъм от действия), но и интересен. Този метод е известен нав за първи път приложен в началотоVIв. индийски математикАрябхатта.

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

Тя е представена по-долу:

„Намерете две цели числа, като знаете, че разликата между произведенията на първото по 19 и на второто по 8 е 13.“

В задачата се изисква да се намерят всички целочислени решения на уравнения.

Решение:

(1) 19х – 8г = 13

изразявам ге неизвестното с най-малка абсолютна стойност на коефициента през х, Взимам:

(2) г = (19х – 13)/8

Сега трябва да открием за какви цели числа х съответни стойности г също са цели числа. Ще пренапиша уравнение (2), както следва:

(3) г = 2х + (3х – 13)/8

От (3) следва, че y с цяло число x приема цяло число само ако изразът (3 х-13)/8 е цяло число, да кажем г 1 . Ако приемем

(4) (3х - 13)/8 = г 1 ,

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

(5) 3х – 8г 1 = 13.

Това уравнение има предимството пред оригиналното уравнение (1), че 3 - най-малката от абсолютните стойности на коефициентите за неизвестни - е по-малко от това в (1), т.е. 8. Това беше постигнато чрез заместване на коефициента при x (19) с остатъка от 8.

Продължавайки по същия начин, получаваме от (5):

(6) х= (8 г 1 +13)/3 = 2г 1 + (2г 1 + 13)/3.

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

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

или

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

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

Ако приемем

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

получавам

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

Това е най-простото от всички разглеждани неопределени уравнения, тъй като един от коефициентите е равен на 1.

От (11) получавам:

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

Това показва, че y 2 приема цели числа за всякакви цели стойности на y 3 . От равенства (6), (9), (12), (3) чрез последователни замествания могат да се намерят следните изрази за неизвестните x и y на уравнение (1):

х= 2г 1 +г 2 = 2(г 2 +г 3 ) + г 2 = 3y2 + 2 г 3 = 3(2г 2 + 13) + 2г 3 = 8г 3 + 39;

при= 2х + г 1 = 2(8г 3 + 39) + г 2 + г 3 = 19г 3 +91.

Така че формулите

х=8 г 3 + 39,

y=19 г 3 + 91.

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

Следващата таблица предоставя примери за такива решения.

Маса 1.

y3

х

г

Нека решим този проблем рационално. Решението използва специфичен алгоритъм.

Задача 5.

Намерете две числа, ако разликата между произведението на първото по 19 и на второто по 8 е 13.

Решение. Необходимо е да се реши уравнението 19x - 8y \u003d 13

Нека го пренапишем по различен начин: 8y =19x –13; 8y =16x +3x -13; y = 2x +

и обозначават y 1 \u003d y - 2x.

В резултат на това уравнението ще приеме формата 8y 1 = Zx - 13 или x = 2y 1
.

Ако отново заменим x 1 \u003d x - 2y 1, тогава стигаме до уравнението

3x l - 2y 1 \u003d 13.

Коефициентите за неизвестните са намалели - смачкани са. Допълнително смилане: y 1 = x l +
, тогава получаваме y 2 \u003d y 1 -x 1.

В резултат на това последното уравнение се преобразува във формата x 1 - 2y 2: \u003d 13. Тук коефициентът при x 1 е равен на 1 и следователно за всяко цяло число y 2 \u003d t числото x 1 е също цяло число.

Остава да изразим оригиналните променливи чрез t :

първо изразяваме x 1 \u003d 2t +13, y 1 \u003d 3t +13; и след това x = 8 t +39, y = 19 t + 91.

И така, получаваме безкрайна последователност (39 + 8T, 91 + 19 T) целочислени решения. Уравнението брадва + от = ° С (1) в горните проблеми реших метода на дисперсия (смилане).

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

Изучавайки диофантовите уравнения, за да ги реша, използвах методите на изброяване на опции и разсейване (смилане). С тези методи реших както съвременни, така и древни проблеми. Съдържанието на моята работа включваше задачи, които се свеждат до решаване на уравнения от първа степен с две променливи ax + b y \u003d c (1)

В хода на работата си стигнах до следните изводи:

Методът на изброяване изисква значителни времеви разходи, което означава, че не е много удобно и рационално.

По-рационален, според мен, е методът на разпръскване. Когато решавах стара индийска задача с този метод, разбрах, че има определен алгоритъм за решение. Имах достатъчно знания, придобити в училище. Бях убеден, че методите за решаване на дофантиеви уравнения непрекъснато се усъвършенстват с развитието на математиката.

Следващата година искам да продължа да изучавам методи за решаване на диофантови уравнения.

V. Библиография

Г. И. Глейзър „История на математиката в училище“ М.: изд. "Просвета" 1964г 376s.

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

В. А. Никифоровски „В света на уравненията“ М.: изд. "Наука" 1987 г 176s.

А. П. Савин" енциклопедичен речникмлад математик „М.: изд. "Педагогика" 1985г

Г. М. Возняк, В. Ф. Гусев “Приложни задачи за екстремуми” М.: изд. "Просвета" 1985г 144s.

http :// en . уикипедия . орг

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

Във фермата е необходимо да се направи водопровод с дължина 167м. Тръбите се предлагат с дължина 5 и 7 метра. Колко тръби трябва да се използват, за да се направят най-малко връзки (не режете тръбите)?

Като се има предвид, че броят на едната и другата тръба може да варира, броят на 7-метровите тръби се означава с х,5- метър - през при

Тогава 7x е дължината на 7-метрови тръби, 5y е дължината на 5-метрови тръби.

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

7x+5y=167

Извеждайки, например, променлива причрез променлива х, получаваме:

Лесно е да намерите съвпадащи двойки стойности чрез повторение хи при, които удовлетворяват уравнението 7x+5y=167

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

От тези решения последното е най-изгодно, т.е. x=21; y=4.

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

2. Нека сборът на въпросните произведения е 330. Намерете датата на раждане.

Нека решим неопределеното уравнение

12 х + 31 при = 330.

Използвайки метода на разсейване, получаваме:

х = 43 – 31 при 4 ,

при = 6 – 12 при 4 .

Поради ограниченията е лесно да се каже, че единственото решение е

при 4 = 1, х = 12, при = 6.

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

За да решите линейно диофантиново уравнение, трябва да намерите стойностите на променливите "x" и "y", които са цели числа. Целочисленото решение е по-сложно от обикновеното и изисква определен набор от действия. Първо трябва да изчислите най-големия общ делител (gcd) на коефициентите и след това да намерите решението. След като намерите едно цяло числово решение на линейно уравнение, можете да приложите прост модел, за да намерите безкраен брой други решения.

стъпки

Част 1

Как се пише уравнение

Напишете уравнението в стандартна форма.Линейно уравнение е уравнение, в което показателите на променливите не надвишават 1. За да разрешите такова линейно уравнение, първо го напишете в стандартна форма. Стандартната форма на линейно уравнение изглежда така: A x + B y = C (\displaystyle Ax+By=C), където A , B (\displaystyle A,B)и C (\displaystyle C)- цели числа.

Опростете уравнението (ако е възможно).Когато пишете уравнението в стандартна форма, погледнете коефициентите A , B (\displaystyle A,B)и C (\displaystyle C). Ако тези коефициенти имат НОД, разделете и трите коефициента на него. Решението на такова опростено уравнение също ще бъде решение на първоначалното уравнение.

Проверете дали уравнението може да бъде решено.В някои случаи можете веднага да декларирате, че уравнението няма решения. Ако коефициентът "C" не се дели на НОД на коефициентите "A" и "B", уравнението няма решения.

Част 2

Как се пише алгоритъмът на Евклид

1. Разберете алгоритъма на Евклид.Това е поредица от повтарящи се деления, в които предишният остатък се използва като следващ делител. Последният делител, който разделя числата равномерно, е най-големият общ делител (gcd) на двете числа.

   Приложете алгоритъма на Евклид към коефициентите "A" и "B".Когато пишете линейното уравнение в стандартна форма, определете коефициентите "A" и "B" и след това приложете към тях алгоритъма на Евклид, за да намерите gcd. Например, като се има предвид линейното уравнение 87 x − 64 y = 3 (\displaystyle 87x-64y=3).

   Намерете най-големия общ делител (gcd).Тъй като последният делител беше 1, НОД 87 и 64 е 1. Така че 87 и 64 са прости числапо отношение един на друг.

   Анализирайте резултата.Когато намерите НОД на коефициентите A (\displaystyle A)и B (\displaystyle B), сравнете го с коефициента C (\displaystyle C)оригинално уравнение. Ако C (\displaystyle C)разделени на НОД A (\displaystyle A)и B (\displaystyle B), уравнението има цяло число; в противен случай уравнението няма решения.

Част 3

Как да намерим решение с помощта на алгоритъма на Евклид

Номерирайте стъпките за изчисляване на GCD.За да се намери решение на линейно уравнение, трябва да се използва Евклидовият алгоритъм като основа на процеса на заместване и опростяване.

Обърнете внимание на последната стъпка, където има остатък.Пренапишете уравнението за тази стъпка, за да изолирате остатъка.

Изолирайте остатъка от предишната стъпка.Този процес е стъпка по стъпка „движене нагоре“. Всеки път ще изолирате остатъка в уравнението от предишната стъпка.

Направете промяна и опростете.Обърнете внимание, че уравнението в стъпка 6 съдържа числото 2, но в уравнението в стъпка 5 числото 2 е изолирано. Така че вместо "2" в уравнението в стъпка 6, заместете израза в стъпка 5:

Повторете процеса на заместване и опростяване.Повторете описания процес, като преминете през алгоритъма на Евклид в обратен ред. Всеки път ще пренапишете уравнението от предишната стъпка и ще го заместите в последното получено уравнение.

1. Продължете процеса на заместване и опростяване.Този процес ще се повтаря, докато стигнете до началната стъпка на алгоритъма на Евклид. Целта на процеса е да се запише уравнение с коефициенти 87 и 64 на първоначалното уравнение, което трябва да бъде решено. В нашия пример:

   • 1 = 2 (18) − 7 (5) (\displaystyle 1=2(18)-7(5))
   • 1 = 2 (18) − 7 (23 − 18) (\displaystyle 1=2(18)-7(23-18))(заместен израз от стъпка 3)
   • 1 = 9 (64 − 2 ∗ 23) − 7 (23) (\displaystyle 1=9(64-2*23)-7(23))(заместен израз от стъпка 2)
   • 1 = 9 (64) − 25 (87 − 64) (\displaystyle 1=9(64)-25(87-64))(заместен израз от стъпка 1)