Průvodní povídání 2
Diofantické rovnice
Průvodní povídání je také k dispozici ve formátu pdf.
Milí pikomaťáci,
\def\N{\mathbb{N}}\def\Z{\mathbb{Z}}
vítáme Tě u druhého dílu letošního průvodního povídání! Minule jsme se naučili něco o dělitelnosti a modulu, teď to využijeme na řešení lineárních diofantických rovnic.
Věta: Bézoutova věta: Pro všechna a,b \in \Z , kde a \neq 0, existují x,y \in \Z taková, že
Neboli ke každé nenulové dvojici čísel dokážeme najít takové koeficienty, aby se to sečetlo na jejich největšího společného dělitele.
Důkaz: Důkaz vynecháme. Jedná se o určeních takových koeficientů pomocí Euklidova algoritmu pro hledání největšího společného dělitele.
Příklad: Pro dvojici čísel 15,21 a jejich největší společný dělitel 3 jsou odpovídající koeficienty 3,-2. Dostáváme 15\cdot 3 + 21 \cdot (-2) = 3.
Definice: Diofantická rovnice je rovnice s celočíselnými koeficienty o několika neznámých, řešení hledáme v oboru celých nebo přirozených čísel. Jedná se například o rovnici a^{2} + b^{2} - c^{2} = 0, jejíž přirozená řešení jsou tzv. Pythagorejské trojice. Řešení nějakých diofantických rovnic nám zatím nejsou známá, například pro a^{3} + b^{3} + c^{3} = 33.
Definice: Lineární diofantickou rovnicí se dvěma neznámými rozumíme rovnici tvaru ax + by = c, kde a,b,c \in \Z jsou zadané parametry a x,y\in \Z neznámé.
Věta: Pravidlo řešitelnosti: Lineární diofantická rovnice se dvěma neznámými má řešení právě tehdy, když nsd(a,b)\mid c.
Důkaz: Abychom dokázali, že věta platí „právě tehdy, když“ dokážeme samostatně dvě části. Nejprve dokážeme, že pokud řešení existuje, pak i nsd(a,b)\mid c. Poté dokážeme, že pokud nsd(a,b)\mid c, pak má rovnice řešení.
Pokud rovnice řešení má, pak nsd(a,b)\mid ax+by (nsd(a,b) dělí oba sčítance). Protože ax+by = c, pak nutně i nsd(a,b)\mid c.
A teď druhá část důkazu, kdy předpokládáme nsd(a,b)\mid c a chceme z toho vyvodit, že rovnice má řešení. Ze vztahu nsd(a,b)\mid c a definice dělitelnosti existuje k\in \Z , že c = k~\cdot nsd(a,b). Aplikujeme Bézoutovu větu na rovnici ax+by=nsd(a,b) a dostaneme řešení x',y'. Rovnici vynásobíme číslem k a máme
Z toho určíme, že kx', ky' musí být řešení původní rovnice.
Příklad: Najděte celočíselné řešení rovnice 15x + 18y = 5. Největší společný dělitel čísel 15 a 18 je 3. Tedy ať už budeme čísla 15 a 18 násobit celými čísly jakkoli, jejich součet vždy bude dělitelný třemi. Pravá strana ale dělitelná třemi není, takže rovnice nemá celočíselné řešení. To je přímo v souladu s pravidlem řešitelnosti.
Příklad: Najděte všechna celočíselná řešení rovnice 10x - 6y = 16.
Protože nsd(10,6)=2 a 2\mid 16, z pravidla řešitelnosti plyne, že nějaké řešení určitě existuje. Rovnici tedy vydělíme dvojkou a vydáme se hledat řešení rovnice 5x - 3y = 8. Vždy si vybereme proměnnou s nižším koeficientem (v absolutní hodnotě), teď to je y. Poté ji vyjádříme a dáme ze zlomku pryč celou část. Následně vyžadujeme, aby zbylý zlomek byl celým číslem. Až už dostaneme jen celou část a ne zlomek, postup končí. Začneme tedy upravovat:
Na levé straně máme celé číslo y, napravo máme zlomek (2x-2)/3 a celé číslo x-2. Tento zlomek tedy také musí být celý, označme jeho hodnotu jako k_{1} \in \Z . Dále algebraicky vyjádříme:
Nyní provedeme podobnou úvahu ještě jednou: Víme, že x a k_{1} + 1 jsou celá čísla, tedy i zlomek k_{1}/2 musí být celé číslo. Tedy musí existovat nějaké k_{2} takové, že k_{1}=2\cdot k_{2}. Nyní můžeme začít zpětně dosazovat:
Řešením původní rovnice je právě každá dvojice x=3k+1, y=5k-1, kde k\in\Z je libovolné.
Definice: Pro danou lineární diofantickou rovnici ax+by=c je rovnice
její přidruženou homogenní rovnicí.
Rovnici si můžeme přepsat do tvaru ax = -by a vidíme, že řešením je určitě třeba x=-b, y=a. Bude se nám ale více hodit řešení x=-b/nsd(a,b), y=a/nsd(a,b). Toto řešení už nemůžeme ničím vydělit, protože by nebylo celočíselné. Můžeme ale toto řešení vynásobit libovolným celým číslem a stále se bude jednat o řešení. Obecné řešení přidružené homogenní rovnice je tedy
kde k\in \Z je libovolné.
Příklad: Určete všechna celočíselná řešení rovnice 10x-6y=0. Spočítáme nsd(10,-6)=2. Dosadíme do vzorce, který jsme si právě odvodili, a získáme x=6k/2=3k, y=10k/2=5k, kde k\in\Z je libovolné.
Tvrzení: Pokud má lineární diofantická rovnice řešení, má jich nekonečně mnoho.
Důkaz: Její přidružená homogenní rovnice určitě má nekonečno řešení, jak jsme před chvílí ukázali. Takové řešení můžeme k původní rovnici přičíst a neovlivní se tím součet na pravé straně:
Když se podíváme na příklad s rovnicí 10x-6y=16, můžeme tipnout základní řešení x=1, y=-1. K tomuto řešení můžeme přičítat řešení její přidružené homogenní rovnice. To už jsme spočítali jako x=3k, y=5k, kde k\in\Z je libovolné. Získáme tím všechna řešení původní rovnice, a to x=3k+1, y=5k-1, kde k\in\Z . To stejné nám vyšlo i předtím. Ne vždy vyjde úplně ten stejný tvar pomocí těchto dvou metod, ale vždy se bude jednat o tu stejnou množinu řešení.
