Umění řešit problémy

Diofantovská rovnice je rovnice vztahující se k celočíselným (nebo někdy k přirozeným či celočíselným) kvanitům.

Nalézání řešení nebo řešení diofantovské rovnice úzce souvisí s modulární aritmetikou a teorií čísel. Má-li diofantovská rovnice nekonečně mnoho řešení, často se k vyjádření vztahu mezi proměnnými rovnice používá parametrický tvar.

Diofantovské rovnice jsou pojmenovány po starořeckém/alekandrijském matematikovi Diofantovi.

Lineární kombinace

Diofantovská rovnice ve tvaru je známá jako lineární kombinace. Zapíšeme-li v tomto tvaru dvě relativně prvočísla a s , bude mít rovnice nekonečný počet řešení. Obecněji řečeno, při bude vždy existovat nekonečný počet řešení. Je-li , pak rovnice nemá žádné řešení. Abychom viděli proč, uvažujme rovnici . je dělitelem LHS (všimněte si také, že musí být vždy celé číslo). Avšak nikdy nebude násobkem , tudíž žádné řešení neexistuje.

Nyní uvažujme případ, kdy . Tedy . Jsou-li a relativně prvočíselné, pak jsou všechna řešení zřejmě ve tvaru pro všechna celá čísla . Pokud nejsou, jednoduše je vydělíme jejich největším společným dělitelem.

Pythagorovy trojice

Hlavní článek: Pythagorova trojice

Pythagorova trojice je množina tří celých čísel, která splňují Pythagorovu větu . Existují tři hlavní metody hledání pythagorejských trojic:

Metoda Pythagorova

Jestliže je liché číslo, pak je pythagorejská trojice.

Metoda Platónova

Jestliže , je pythagorejská trojice.

Babylonská metoda

Pro libovolné máme, že je pythagorejská trojice.

Součet čtvrtých mocnin

Rovnice tvaru nemá celočíselné řešení takto: Předpokládáme, že rovnice má celočíselné řešení, a uvažujeme řešení, které minimalizuje . Nechť toto řešení je . Jestliže , pak jejich GCD musí splňovat . Řešení by pak bylo řešení menší než , což odporuje našemu předpokladu. Tato rovnice tedy nemá celočíselné řešení.

Pokud , pak pokračujeme v řešení případů, v .

Všimněte si, že každý čtverec, a tedy každá čtvrtá mocnina, je buď , nebo . Důkaz tohoto tvrzení je poměrně jednoduchý a můžete si ho ukázat sami.

Případ 1:

To by znamenalo , tedy rozpor.

Případ 2:

To by znamenalo , rozpor, protože jsme předpokládali .

Případ 3: , a

Víme také, že čtverce jsou buď , nebo . Všechny čtvrté mocniny jsou tedy buď , nebo .

Podobným postupem ukážeme, že:

, tedy .

To je rozpor, protože implikuje, že je liché, a implikuje, že je sudé. QED

Pellovy rovnice

Hlavní článek: Pellova rovnice

Pellova rovnice je typ diofantovské rovnice ve tvaru pro přirozené číslo . Řešení Pellovy rovnice, když není dokonalý čtverec, souvisí s rozkladem pokračujícího zlomku . Je-li perioda pokračujícího zlomku a je tý konvergent, jsou všechna řešení Pellovy rovnice ve tvaru pro celé kladné číslo .

Metody řešení

Souřadnicová rovina

Všimněte si, že libovolnou lineární kombinaci lze převést na lineární rovnici , což je právě rovnice sklonu a průsečíku pro přímku. Řešení diofantické rovnice odpovídají mřížovým bodům, které leží na přímce. Uvažujme například rovnici nebo . Jedno řešení je (0,1). Pokud přímku vynesete do grafu, snadno zjistíte, že přímka protíná mřížový bod, když se x a y zvětší nebo zmenší o stejný násobek , respektive (znění?). Proto lze řešení rovnice zapsat parametricky (pokud budeme považovat za „výchozí bod“).

Modulární aritmetika

Někdy lze modulární aritmetiku použít k důkazu, že žádné řešení dané diofantovské rovnice neexistuje. Konkrétně pokud ukážeme, že daná rovnice není nikdy pravdivá mod pro nějaké celé číslo , pak jsme ukázali, že rovnice je nepravdivá. Tuto techniku však nelze použít k tomu, abychom ukázali, že řešení dané diofantovské rovnice existují.

Indukce

Někdy, když bylo nalezeno několik řešení, lze k nalezení rodiny řešení použít indukci. Techniky, jako je nekonečná descendence, mohou také ukázat, že žádná řešení dané rovnice neexistují, nebo že neexistují žádná řešení mimo danou rodinu.

Obecná řešení

Je přirozené se ptát, zda existuje obecné řešení pro diofantovské rovnice, tj. algoritmus, který najde řešení pro libovolné dané diofantovské rovnice. To je známé jako Hilbertův desátý problém. Odpověď však zní ne.

Fermatova poslední věta

Hlavní článek: Fermatova poslední věta

je známá jako Fermatova poslední věta pro podmínku . Když Fermat v roce 1600 pracoval na knize o diofantovských rovnicích, napsal si na okraj poznámku ve smyslu: „Mám skutečně podivuhodný důkaz této věty, na který je tento okraj příliš úzký, než aby se do něj vešel.“ Fermat ve skutečnosti vyslovil mnoho domněnek a navrhl spoustu „tezí“, ale nebyl z těch, kteří by si důkazy nebo jiné než načmárané poznámky zapisovali. Po jeho smrti byly všechny jeho domněnky znovu dokázány (buď nepravdivě, nebo pravdivě) s výjimkou Fermatovy poslední věty. Po více než 350 letech, kdy se ji nepodařilo dokázat, ji nakonec dokázal Andrew Wiles poté, co strávil více než 7 let prací na dvousetstránkovém důkazu a další rok opravou chyby v původním důkazu.

Problémy

Úvod

Dva farmáři se shodnou, že prasata stojí dolarů a kozy dolarů. Když jeden farmář dluží druhému peníze, zaplatí dluh prasaty nebo kozami, přičemž „drobné“ dostane podle potřeby v podobě koz nebo prasat. (Například dluh ve výši dolarů může být zaplacen dvěma prasaty, přičemž jednu kozu obdrží jako drobné.) Jaká je výše nejmenšího kladného dluhu, který lze tímto způsobem vyřešit?“