Neurčité rovnice (někdy též diofantické nebo diofantovské) Úvod. Jistě jste se už setkali s jednou rovnicí o dvou neznámých tvaru a · x + b · y = c (a ¹ 0, b ¹ 0, a Î R, b Î R, c Î R) v oboru reálných čísel. Nalézt některé z nekonečně mnoha řešení této rovnice je velmi snadné; hodnotu jedné z neznámých lze zvolit libovolně a hodnotu druhé neznámé dopočítat. Obtížnější situace nastane tehdy, jestliže požadujeme, aby obě dvě složky x a y řešení byla celá čísla. Tomu se nyní budeme věnovat. Neurčité rovnice jsou rovnice se dvěma neznámými, které se řeší v oboru všech celých čísel. Je pochopitelné, že koeficienty u obou neznámých i pravá strana rovnice musí být v tomto případě racionální čísla; vynásobením celé rovnice společným jmenovatelem racionálních čísel a, b, c dostaneme neurčitou rovnici, jejíž koeficienty a, b i pravá strana c jsou celá čísla. Poznámka 1. Možná se někteří z Vás setkali i s neurčitými rovnicemi o více neznámých či s neurčitými rovnicemi vyšších stupňů. Zde se omezíme pouze na lineární neurčité rovnice o dvou neznámých (obě dvě neznámé x, y jsou umocněny na první). Definice. Lineární neurčitá rovnice o dvou neznámých x, y je rovnice a · x + b · y = c, a ¹ 0, b ¹ 0 , a, b, c Î Q, (1) kde řešení hledáme v oboru celých čísel. Poznámka 2. Je-li alespoň jeden z koeficientů a, b, c racionální necelé číslo, vynásobíme rovnici vhodným číslem tak, aby všechny tři koeficienty nabyly celočíselných hodnot. Věta 1. (Řešitelnost lineární neurčité rovnice.) Neurčitá rovnice a . x+ b . y = c má řešení v případě, že největší společný dělitel koeficientů a, b je také dělitelem čísla c . Pak řešením je nekonečně mnoho dvojic celých čísel x , y. V případě, že největší společný dělitel čísel a, b není dělitelem koeficientu c, pak rovnice nemá řešení. Poznámka 3: Je snadné uvést příklad neřešitelné neurčité rovnice. Např. rovnice 4x + 6y = 1 nemůže mít řešení, protože D(4, 6) = 2 a číslo 1 není dělitelné dvěma. I úsudkem je neřešitelnost této rovnice zřejmá, protože na levé straně je po dosazení libovolných hodnot x, y číslo sudé, zatímco na pravé straně je číslo liché. Poznamenejme dále, že pokud je D(a, b) dělitelem čísla c a rovnice je tedy řešitelná, vydělíme celou rovnici číslem D(a, b). Tím se hodnoty koeficientů na levé straně i číslo na pravé straně sníží a navíc bude platit, že koeficienty a, b budou po vydělení číslem D(a, b) čísla nesoudělná. Věta 2. (Postup řešení neurčité rovnice) I. Nechť x[0] , y[0 ]je jedno pevné známé řešení neurčité rovnice (1). Potom obecné řešení je dáno vztahy: x = x[0 + ] , y = y[0] - , t Î Z . (2) Určení x[0] , y[0 ]: a) úsudkem b) výpočtem z podílů Eukleidova algoritmu při určování D(a, b). II. Redukční metoda. Poznámka 4. Vzhledem k Vašemu studijnímu programu Učitelství pro 1. stupeň ZŠ se v praxi setkáte s neurčitými rovnicemi, v nichž a, b, c budou malá celá čísla. V tomto případě je nejvýhodnější postup řešení I a), protože při nízkých hodnotách a, b, c naleznete jedno řešení rovnice (1) snadno úsudkem. Uvedeme příklad. Příklad 1. Řešte neurčitou rovnici 3x + 2y = 5. Řešení. D(3, 2) = 1, 1½5. Rovnice je tedy řešitelná. Zpaměti určíme jedno možné řešení, např. x[0] = 3, y[0] = - 2. Ze zadání rovnice platí a = 3, b = 2, D(3, 2) = 1. Pak podle vztahů (2) máme obecné řešení (t je celočíselný parametr): x = 3 + 2 t, y = - 2 - 3 t . Provedeme zkoušku: 3(3 + 2 t) + 2(- 2 - 3 t) = 5. Dosazením libovolného celého čísla za t dostaneme dvojici celých čísel, která je řešením zadané rovnice. Např. pro t = 4 dostaneme x = 11, y = - 14. Poznámka 5. V případě, že řešení dané rovnice je součástí slovní úlohy, je nutno s obecným řešením dále pracovat. Můžeme např. požadovat, aby x, y byla kladná čísla. V tom případě výpočtem omezíme hodnoty parametru t , který pak může nabývat třeba jen několika hodnot. Příklady uvedeme v dalším textu. Poznamenejme ještě, že řešení takovýchto rovnic na 1. stupni ZŠ probíhá formou experimentu, postupným vyplňováním tabulek atp. S těmito postupy se setkáte v didaktice matematiky. Poznámka 6. V případě, že koeficienty a, b v rovnici (1) jsou větší čísla, není již prakticky možné určit úsudkem jedno pevné řešení x[0] , y[0 ]a při řešení je nutno postupovat podle bodu I b) nebo II, kterým lze nahradit oba způsoby řešení I a) , I b). Ukážeme řešení podle I b). Příklad 2. Řešte neurčitou rovnici 137x - 89y = 2. Řešení. Čísla 137 a 89 jsou prvočísla (dokažte sami), proto D(137, 89) = 1, 1½2. Rovnice je tedy řešitelná. Pro určení jednoho pevného řešení x[0] , y[0] užijeme Eukleidův algoritmus při určení D(137, 89). Využijeme přitom následující tvrzení. Je -li D(a, b) = d, pak existují celá čísla u, v s vlastností au + bv = d. Čísla u, v určujeme podle Eukleidova algoritmu tím, že v každém řádku Eukleidova algoritmu vypočítáme zbytek pomocí čísel a, b (vždy postupně dosazujeme již vypočtené hodnoty). 137 = 1 . 89 + 48 , odtud 48 = 137 - 89 89 = 1 . 48 + 41 , odtud 41 = 89 - 48 = 89 - (137 - 89) = 2 . 89 - 137 48 = 1. 41 + 7, odtud 7 = 48 - 41 = (137 - 89) - (2 . 89 - 137) = 2 . 137 - 3 . 89 41 = 5 . 7 + 6, odtud 6 = 41 - 5 . 7 = (2 .89 - 137) - 5.(2.137 - 3.89) = 17 . 89 - 11 . 137 7 = 1 . 6 + 1, odtud 1 = 7 - 6 = (2 . 137 - 3 . 89) - (17 . 89 - 11 . 137) = 13 . 137 - 20 . 89 6 = 6 . 1 + 0 Z výpočtu plyne 137 . 13 - 89 . 20 = 1. Tento vztah vynásobíme dvěma (čísla 137 a 89 určené v zadání neurčité rovnice ponecháme při násobení beze změny) a dostaneme: 137 . 26 - 89 . 40 = 2 (3) Porovnáme-li vztah (3) se zadanou neurčitou rovnicí, vidíme, že x[0 ]= 26, y[0 ]= 40. Neurčitá rovnice 137x - 89y = 2 má pak obecné řešení x = 26 - 89 t, y = 40 - 137 t. Zkouška: 137 . (26 - 89 t ) - 89 . (40 - 137 t) = 2 Poznámka 7. Nyní zbývá ukázat postup řešení neurčité rovnice (1) pomocí postupu II, tj. redukční metodou. Tato metoda nahrazuje obě metody I a), I b), protože v ní není nutné hledat jedno pevné řešení x[0 ], y[0]. Postup spočívá v tom, že pomocí postupných redukčních kroků převádíme zadanou neurčitou rovnici na neurčité rovnice s nižšími koeficienty (odtud redukce) tak dlouho, až dostaneme rovnici, jejíž řešení můžeme přímo určit. Řešení původní rovnice pak získáme postupným zpětným dosazováním. Uvedeme příklad. Příklad 3. Řešte neurčitou rovnici 12x + 31y = 328. Řešení. Čísla 12 a 31 jsou prvočísla, proto D(12, 31) = 1, 1½328. Rovnice je tedy řešitelná. Z rovnice 12x + 31y = 328 vypočteme neznámou, u které je koeficient s nižší absolutní hodnotou. V našem případě platí x = . V čitateli tohoto zlomku nalezneme nejbližší násobek dvanácti k číslům 328 a 31 (je jedno, zda větší nebo menší) a výraz pro x rozdělíme na dva zlomky tak, aby první z nich bylo možno krátit 12. Nalezneme tedy x = = + = (27 - 3y) + . Aby bylo x celé číslo, musí být čitatel posledního zlomku dělitelný dvanácti, tedy musí platit 4 + 5y = 12k. Po formální úpravě 12k - 5y = 4. Tím jsme dostali další neurčitou rovnici s nižšími koeficienty. Tu můžeme vyřešit např. metodou I a), kde pevné řešení je k[0 ]= 2, y[0 ]= 4 nebo můžeme pokračovat opět redukční metodou. Pokračujeme již bez komentáře: y = = + = (2k - 1) + . Aby bylo y celé číslo, musí být čitatel posledního zlomku dělitelný pěti, tedy 2k + 1 = 5u. Po formální úpravě 5u - 2k = 1. Tím jsme dostali další neurčitou rovnici s nižšími koeficienty. Tu můžeme opět vyřešit metodou I a), kde pevné řešení je u[0 ]= 1, k[0 ]= 2 nebo můžeme pokračovat opět redukční metodou. Provedeme další redukci: k = = + = 2u + . Aby bylo k celé číslo, musí být čitatel posledního zlomku dělitelný dvěma, tedy u - 1 = 2t, po formální úpravě u - 2t = 1. Tím jsme dostali další neurčitou rovnici s ještě nižšími koeficienty. Její řešení lze však přímo napsat ve tvaru u = 1+ 2t (t je celočíselný parametr). Nyní postupným dosazováním dostaneme řešení původně zadané rovnice. Podrobnější úpravy si již odpustíme (proveďte sami). u = 1+ 2t ; k = = = … = 2 + 5t ; y = = = … = 4 + 12t ; x = = = … = 17 - 31t . Neurčitá rovnice 12x + 31y = 328 má tedy obecné řešení x = 17- 31t , y = 4 + 12t . Poznámka 7. Nyní uvedeme několik slovních příkladů vedoucích k řešení neurčité rovnice. Tyto rovnice již řešit nebudeme, uvedeme vždy pouze výsledek. (řešení proveďte sami). Cílem těchto příkladů je ukázat, jak se při matematizaci takových úloh neurčité rovnice sestavují, resp. jak se dále pracuje s parametrem t. Příklad 4. Nalezněte všechny dvojice kladných celých čísel, které jsou řešením rovnice 12x + 31y = 328. Řešení: Obecné řešení jsme určili v příkladu 3. Rovnice 12x + 31y = 328 má nekonečně mnoho řešení určených parametrickými rovnicemi x = 17- 31t , y = 4 + 12t . Hledáme-li pouze kladná řešení, musíme nyní vyřešit soustavu nerovnic 17- 31t > 0, 4 + 12t > 0. Výpočtem určíme nerovnost < t < ; pro všechna celá čísla t ležící v tomto intervalu platí, že po jejich dosazení do zadané rovnice budou hodnoty x, y kladná čísla. Výše uvedeným nerovnostem vyhovuje pouze jediné celé číslo t = 0. Po dosazení dostáváme jediné kladné řešení x = 17, y = 4. Příklad 5. Rozměňte 210 Kč pomocí mincí o hodnotách 10 Kč, 20 Kč a 50 Kč tak, aby celkový počet mincí byl 9. Řešení: Počet padesátikorun označíme x, počet dvacetikorun y a počet desetikorun z. Řešení příkladu je dáno soustavou rovnic 50 x + 20 y + 10 z = 210 x + y + z = 9 Ze druhé rovnice vyjádříme z = 9 - x - y a dosadíme do první rovnice. Po úpravě obdržíme neurčitou rovnici 4 x + y = 12. Tato rovnice je řešitelná a její obecné řešení (získané třeba metodou I a), kde pevné řešení je např. x[0] = 2, y[0] = 4) je x = 2 + t, y = 4 - 4 t. Po dosazení do vztahu pro z a úpravě dostáváme z = 3 + 3 t. Nyní musí platit (počet mincí je nezáporné celé číslo) x ³ 0, y ³ 0, z ³ 0. Musíme tedy vyřešit soustavu nerovnic 2 + t ³ 0, 4 - 4 t ³ 0, 3 + 3 t ³ 0. Řešením dostáváme nerovnici - 1 £ t £ 1. Všechna celá čísla ležící v tomto intervalu dávají po dosazení řešení zadaného příkladu. Pro t = - 1 máme řešení x = 1, y = 8, z = 0 (jedna padesátikoruna a osm dvacetikorun), pro t = 0 máme řešení x = 2, y = 4, z = 3 (dvě padesátikoruny, čtyři dvacetikoruny a tři desetikoruny), pro t = 1 máme řešení x = 3, y = 0, z = 6 (3 padesátikoruny a 6 desetikorun). Příklad 6: Určete nejmenší trojciferné číslo a největší trojciferné číslo, která při dělení osmi dává zbytek 7 a při dělení jedenácti zbytek 3. Řešení: Nejprve nalezneme obecný vztah pro hledané číslo, které označíme třeba k. Podle zadání platí k = 8 x + 7 a současně k = 11 y + 3. Musí tedy platit rovnost 8 x + 7 = 11 y + 3; po úpravě obdržíme neurčitou rovnici 8 x - 11y = - 4. Tato rovnice je řešitelná, obecné řešení je x = 5 - 11 t, y = 4 - 8 t. Po dosazení do vztahu pro k dostaneme po úpravě k = 47 - 88t . Pro každou celočíselnou hodnotu parametru t obdržíme po dosazení číslo s požadovanými vlastnostmi. Největší a nejmenší trojciferné číslo lze nalézt buďto experimentem, kdy vypíšeme několik prvních kladných hodnot k (vždy se liší o 88) a postupujeme až do tisíce: 47, 135, 223, 311 …, 927, 1015,…, nebo řešíme soustavu nerovnic k > 100, k < 1000, tedy 100 < 47 - 88t < 1000. Vyřešením obdržíme interval < t < , což je přibližně - 10,83 < t < - 0,60. Nejmenší a největší celé číslo t z tohoto intervalu určuje hledané řešení (které jsme už určili experimentem): pro t = - 1 máme k = 135, pro t = - 10 máme k = 927. Příklad 7. Rozložte číslo 4000 na dva přirozené sčítance, z nichž jeden je dělitelný číslem 41 a druhý číslem 61. Řešení: Hledaná čísla označíme např. a, b. Podle zadání platí a = 41x, b = 61y. Neurčitá rovnice, kterou musíme vyřešit, je tvaru 41x + 61y = 4000. Tato rovnice je řešitelná, obecné řešení získáme buďto metodou I b) nebo redukční metodou. Toto obecné řešení je x = 105 - 61 t, y = -5 + 41 t. Potom po dosazení získáme vztahy pro hledaná čísla a, b ve tvaru: a = 41 (105 - 61 t) = 4305 - 2501 t, b = 61 (-5 + 41 t) = - 305 + 2501 t. Sečtením vztahů pro a, b snadno ověříme, že a + b = 4000. Podle zadání máme nalézt dva přirozené sčítance, tzn. nezáporná celá čísla. Protože číslo nula zřejmě řešením není, řešíme soustavu nerovnic a > 0, b > 0, tedy 4305 - 2501t > 0, - 305 + 2501t > 0 . Po vyřešení dostáváme interval < t < , což je přibližně 0,12 < t < 1,72. Jediné celé číslo t ležící v tomto intervalu, je číslo 1. Po dosazení t = 1 dostaneme a = 1804, b = 2196.