Диофантове једначине

Диофантова једначина је алгебарска једначина с две или више непознатих с целобројним коефицијентима у којој се траже целобројна или рационална решења. Име је добила по Диофанту који је први систематски проучавао такве једначине. Линеарна Диофантова једначина изједначава збир два или више монома, сваки степена 1 у једној од променљивих, са константом. Експоненцијална Диофантова једначина је она у којој експоненти на члановима могу бити непознати.

Проналажење свих правих троуглова са целобројним дужинама страница еквивалентно је решавању Диофантове једначине а² + б² = ц².

Примери

У следећим Диофантовим једначинама, w, x, y, и з су непознате, а осталим словима су дате константе:

аx + бy = 1	Ово је линеарна Диофантова једначина.
w3 + x3 = y3 + з3	Најмање нетривијално решење у позитивним целобројним бројевима је 123 + 13 = 93 + 103 = 1729. Познато је по томе што му је дато евидентно својство 1729. године, број таксија (такође назван Харди–Рамануџанов број), по Рамануџану и Хардију током састанка 1917. Постоји бесконачно много нетривијалних решења.
xн + yн = зн	За н = 2 постоји бесконачно много решења (x, y, з): Питагориних тројки. За веће целобројне вредности од н, последња Фермаова теорема (коју је иницијално објавио Фермат 1637. и доказао Ендру Вајлс 1995) наводи да не постоје позитивна целобројна решења (x, y, з).
x2 − нy2 = ±1	Ово је Пелова једначина, која је добила име по енглеском математичару Џону Пелу. Њу је студирао Брамагупта у 7. веку, као и Фермат у 17. веку.
4/н = 1/x + 1/y + 1/з	Ердос-Штраусова хипотеза наводи да, за сваки позитивни цели број н ≥ 2, постоји решење у x, y, и з, сва од којих су позитивни цели бројеви. Иако се обично не наводи у полиномном облику, овај пример је еквивалентан полиномској једначини 4xyз = yзн + xзн + xyн = н(yз + xз + xy).
x4 + y4 + з4 = w4	Ојлер је погрешно претпоставио да нема нетривијалних решења. Елкис је доказао да има бесконачно много нетривијалних решења, а Фрај је рачунарском претрагом одредио најмање нетривијално решење.

Линеарне Диофантове једначине

Диофантова линеарна једначина је једначина облика:

$ax+by=c$

гдје су a, b и c неки цели бројеви.

Пример

$x=-{\frac {5}{3}}y$

Како је x цео број то је y дељиво са 3

$y=3t$

односно

$x=-5t$

$(x,y)=(-5t,3t)$

Теорема

Диофантова једначина $ax+by=c$, где су $a$,$b$,$c$ цели бројеви $a^{2}+b^{2}\neq 0,$ има целобројна решења ако и само ако $M(a,b)$ дели $c$.

Ако су $x_{0}$ и $y_{0}$ решења те једначине онда су сва решења облика

$x=x_{0}+{\frac {b}{d}}t$

$y=y_{0}+{\frac {a}{d}}t$

Решење $(x_{0},y_{0})$ назива се партикуларно решење Диофантове једначине. Опште решење је збир партикуларног решења и решења хомогене једначине $ax+by=0$

Пример

$3x+5y=8$

Партикуларно решење је $(1,1)$, а решења припадне хомогене једначине су $(-5t,3t)$, $t\in Z$

Решења једначине су парови $(1-5t,1+3t)$ за $t\in Z$ За проналажење партикуларног решења Диофантове једначине користисти се Еуклидов алгоритам помоћу којег одређују цели бројеви $k$ и $l$ за које вреди $ax+by=d$, где је $d=M(a,b)$, а затим множењем са ${\frac {c}{d}}$ добија се партикуларно решење.

Пример

$1000x-123y=5$

$1000=8*123+16$

$123=7*16+11$

$16=1*11+5$

$11=2*5+1$

па је

$16=1000-8*123$

$11=123-7*16$

$5=16-1*11$

$1=11-2*5$

У последњу једнакост се уврсти израз за број 5 из претпоследње једнакости

$1=11-2*5=11-2*(16-11*1)=3*11-2*16$

$1=3*(123-16*7)-2*16=3*123-23*16$

$1=3*123-23*(1000-8*123)=-23*1000+187*123$

тј.

$1=-23*1000+187*123$ $/*5$

$5=-115*1000+935*123$

$x_{0}=-115$

$y_{0}=-935$

$x=123t$

$y=1000t$

Решење дате једнадначине је

$x=-115+123t$

$y=-935+1000t$ $t\in Z$

Пример

За превоз неке робе располаже се врећама од 40 кг и 60 кг. Колико треба узети једних, а колико других да се превезе 500 кг робе

Задатак се може решити Ојлеровом методом

$40x+60y=500$

$2x+3y=25$ за $x\geq 0$ и $y\geq 0$

$x={\frac {25-3y}{2}}=12-y+{\frac {1-y}{2}}$

${\frac {1-y}{2}}=u$ $u\ Z$

$2u+y=1$

$y=1-2u$

$x=12-(1-2u)+u=11+3u$

Решења једнадчине су парови $(x,y$) где је $x=11+3u$ и $y=1-2u$

$-{\frac {11}{3}}\leq u\leq {\frac {1}{2}}=>u=-3,-2,-1,0$

Тражени парови $(x,y$) су $(2,7)$ $(5,5)$ $(8,3)$ и $(11,1)$

Нелинеарне Диофантове једначине

Не постоји универзална метода решавања ових једначина, али зато постоји низ метода којима се решавају неки специјални типови нелинеарних Диофантових једначина. Неки од тих метода су:

1. метод факторизације
2. метод разломка
3. метод последње цифре
4. метод конгруенције
5. метод збира потенција с парним експонентима
6. метод неједнакости

Метод факторизације

Метод факторизације састоји се у томе да се једна страна једначине запише у облику производа целобројних вредности, па узимајући у обзир другу страну једначине посматрају се могући случајеви.

$xy+x-3y-3=0$

($x-3)(y+1)=3$

Ово је могуће за

x-3	y+1
1	3
-1	-3
3	1
-3	-1

односно

x	y
4	2
2	-4
6	0
0	-2

Метод разломка

Основна идеја овог метода слична је као код методе факторизације, само што се сада једна страну једначине записује у облику разломка две целобројне вредности, док друга стране једначине има такође целобројну вредност. Због тога називник тог разломка мора делити бројник, што даје класификацију могућих случајева. Споменути разломак се у пракси најчешће добија тако да се једна непозната изрази као рационална функција друге.

$xy+2y=x$

$y(x+2)=x$

$y={\frac {x}{x+2}}=1-{\frac {2}{x+2}}$

$x\ {\begin{Bmatrix}-1,-3,0,-4\end{Bmatrix}}$

$y\ {\begin{Bmatrix}-1,3,0,-2\end{Bmatrix}}$

Метод последње цифре

Метод последње цифре је подметод метода остатака који користи испитивање остатака при дељењу бројем 10. Прецизније, раздвајање случајева се врши посматрањем задње цифре неких делова једначине, те њиховим усклађивањем.

$x^{2}+5y=199519941993$

Квадрат целог броја завршава цифром 0, 1, 4, 5, 6, или 9, а број $5y$ са 0 или 5, па збир на левој страни завршава са 0, 1, 4, 5, 6, или 9, а не са 3. Једначина нема решења.

Метод конгруенције

$x^{2}-4y=1995$

$1995$ непаран, а $4y$ паран, па је $x$ непаран

$x=2k-1$

$(2k-1)^{2}-4y=1995$

$4k^{2}-4k+1-4y=1995$

$4(k^{2}+k-y)=1994$

Једначина нема решења, јер 1994 није дељиво са 4

Метод збира потенција с парним експонентима

Метод збира је сличан методу факторизације, само што се сада једна страна једначине записује у облику збира (најчешће ненегативних) целих бројева.

$x^{2}+y^{2}+2x-4y+8=0$

$(x+1)^{2}+(y-2)^{2}=13$

$(x+1)^{2}=9$

$(y-2)^{2}=4$

$(x,y)\in {\begin{Bmatrix}(1,5),(2,4)\end{Bmatrix}}$

Метод неједнакости

Овај метод се често користи да би се смањио скуп могућих решења дате једначине, а затим се на том смањеном скупу разликују случајеви. На том смањеном скупу разликују се случајеви. Метод неједнакости се често користи и у комбинацији с неким другом методом за решавање нелинеарних Диофантових једначина

$3^{x}+4^{x}=5^{x}$

$x=2$

$3^{x}+4^{x}=5^{x}$ $/:5^{x}$

$({\frac {3}{5}})^{x}+({\frac {4}{5}})^{x}=1$

за $x<2$

$({\frac {3}{5}})^{x}+({\frac {4}{5}})^{x}>1$

за $x>2$

$({\frac {3}{5}})^{x}+({\frac {4}{5}})^{x}<1$

Једначина има само једно решење $x=2$

Пелове и пеловске једначине

Нека је задата једначина

$x^{2}+y^{2}=z^{2}$

Уређена тројка (x,y,з) која задовољава задату једначину се назива Питагорина тројка. Ако су бројеви x y з релативно прости онда је то примитивна Питагорина тројка

У свакој примитивној Питагориној тројци тачно је један од бројева $x$,$y$ непаран. За $x$,$y$ парне се не би радило о примитивној Питагориној тројци

Диофантова једначина облика

$x^{2}-dy^{2}=a$ где је $d\in N$ и није потпун квадрат је Пелова једначина.

Пелова једначина има бесконачно много решења у скупу природних бројева. Ако се пронађе најмање (основно) решење $(x_{e},y_{e})$, преостала решења $(x_{n},y_{n})$ се могу генерисати на следеће начине

1. :$x_{n}+y_{n}{\sqrt {d}}$ $=(x_{n}+y_{n}{\sqrt {d}})^{n}$
2. :$x_{n+1}=2x_{n}x_{e}-x_{n-1}$ и $y_{n+1}=2x_{n}y_{e}-y_{n-1}$ за $(x_{0},y_{0})=(1,0)$ и $(x_{1},y_{1})=(x_{e},y_{e})$
3. :$x_{n+1}=x_{e}x_{n}+y_{e}dy_{n}$ и $y_{n+1}=x_{e}y_{n}+y_{e}dx_{n}$

Једначина

$x^{2}-dy^{2}=1$ је Пеловска једначина (једначина Пеловог облика)

За разлику од Пелове једначине ова једначина нема увек целобројно решење.

Ердос–Штраусова хипотеза

Овом хипотезом је претпостављено да за све природне бројеве $n\geq 2$ постоји рационални број $4/n$ који се може исказати као збир три јединична разломка с позитивним, целобројним називницима како следи:

${\frac {4}{n}}={\frac {1}{x}}+{\frac {1}{y}}+{\frac {1}{z}}.\,$

Пример

за $n=1801$, постоји решење једначине где је $x=451$, $y=295364$ и $z=3249004$.

Помноже ли се обе стране једначине са $nxyz$, налази се Диофантова једначина облика:

$4xyz=n(xy+xz+yz).\,$

Литература

• Сцхмидт, Wолфганг M. (1991). Диопхантине аппроxиматионс анд Диопхантине еqуатионс. Лецтуре Нотес ин Матхематицс. 1467. Берлин: Спрингер-Верлаг. ИСБН 978-3-540-54058-8. Збл 0754.11020. 
• Схореy, Т. Н.; Тијдеман, Р. (1986). Еxпонентиал Диопхантине еqуатионс. Цамбридге Трацтс ин Матхематицс. 87. Цамбридге Университy Пресс. ИСБН 978-0-521-26826-4. Збл 0606.10011. 
• Смарт, Нигел П. (1998). Тхе алгоритхмиц ресолутион оф Диопхантине еqуатионс. Лондон Матхематицал Социетy Студент Теxтс. 41. Цамбридге Университy Пресс. ИСБН 978-0-521-64156-2. Збл 0907.11001. 
• Стиллwелл, Јохн (2004). Матхематицс анд итс Хисторy (Сецонд изд.). Спрингер Сциенце + Бусинесс Медиа Инц. ИСБН 978-0-387-95336-6. 
• Дицксон, Леонард Еугене (2005) [1920]. Хисторy оф тхе Тхеорy оф Нумберс. Волуме II: Диопхантине аналyсис. Минеола, НY: Довер Публицатионс. ИСБН 978-0-486-44233-4. МР 0245500. Збл 1214.11002. 
• Морделл, L. Ј. (1969). Диопхантине еqуатионс. Пуре анд Апплиед Матхематицс. 30. Ацадемиц Пресс. ИСБН 0-12-506250-8. Збл 0188.34503. 
• Басхмакова, Изабелла Г. "Диопханте ет Фермат," Ревуе д'Хистоире дес Сциенцес 19 (1966), пп. 289–306
• Басхмакова, Изабелла Г. Диопхантус анд Диопхантине Еqуатионс. Мосцоw: Наука 1972 [ин Руссиан]. Герман транслатион: Диопхант унд диопхантисцхе Глеицхунген. Биркхаусер, Басел/ Стуттгарт, 1974. Енглисх транслатион: Диопхантус анд Диопхантине Еqуатионс. Транслатед бy Абе Схенитзер wитх тхе едиториал ассистанце оф Хардy Грант анд упдатед бy Јосепх Силверман. Тхе Долциани Матхематицал Еxпоситионс, 20. Матхематицал Ассоциатион оф Америца, Wасхингтон, DC. 1997.
• Басхмакова, Изабелла Г. “Аритхметиц оф Алгебраиц Цурвес фром Диопхантус то Поинцарé” Хисториа Матхематица 8 (1981), 393-416.
• Басхмакова, Изабелла Г., Славутин, Е.I. Хисторy оф Диопхантине Аналyсис фром Диопхантус то Фермат. Мосцоw: Наука 1984 [ин Руссиан].
• Басхмакова, Изабелла Г. “Диопхантине Еqуатионс анд тхе Еволутион оф Алгебра,” Америцан Матхематицал Социетy Транслатионс 147 (2), 1990, пп. 85–100. Транслатед бy А. Схенитзер анд Х. Грант.
• Расхед, Росхди, Хоузел, Цхристиан. Лес Аритхмéтиqуес де Диопханте : Лецтуре хисториqуе ет матхéматиqуе, Берлин, Неw Yорк : Wалтер де Груyтер, 2013.
• Расхед, Росхди, Хистоире де л’аналyсе диопхантиенне цлассиqуе : Д’Абū Кāмил à Фермат, Берлин, Неw Yорк : Wалтер де Груyтер.

Спољашње везе

• Diophantine Equation. From MathWorld at Wolfram Research.
• Хазеwинкел Мицхиел, ур. (2001). „Диопхантине еqуатионс”. Енцyцлопаедиа оф Матхематицс. Спрингер. ISBN 978-1556080104. 
• Dario Alpern's Online Calculator
• Диофантске јеначине Архивирано на сајту Wayback Machine (11. јун 2012)