68 čísla. Není se čemu divit, vždyť v mnoha praktických úlohách, vedoucích k rovnicím, nemusí mít neceločíselná řešení rozumnou interpretaci. (Jde například o úlohu, jak pomocí pětilitrové a sedmilitrové nádoby odměřit do třetí nádoby osm litrů vody, která vede na rovnici 5x + 7y = 8.) Na Diofantovu počest se rovnice, ve kterých hledáme jen celočíselná řešení, nazývají diofantické. Pro řešení těchto rovnic bohužel neexistuje žádná univerzální metoda. Dokonce neexistuje ani metoda (jinými slovy algoritmus), která by určila, jestli má obecná polynomiální diofantická rovnice řešení. Tato otázka je známá pod názvem 10. Hubertův problém a důkaz neexistence algoritmu podal lOpuM MaTHHceBH^i (Yuri Matiasevič) v roce 1970 (viz elementárně psaný text [1]). Přesto však uvedeme několik nej obvyklejších metod, které v řadě konkrétních případů povedou k výsledku. 6.1. Lineární diofantické rovnice. d\X\ + 02^2 + • • • + CLnxn = b, (30) kde xi,..., xn jsou neznámé, a1;..., an, b daná celá čísla. Budeme předpokládat, že a,i ý 0 Pro každé i = 1,... ,n (je-li a« = 0, pak neznámá Xi z rovnice „zmizí"). K řešení těchto rovnic je možné užít kongruencí. Nejprve si všimněme, kdy má rovnice (30) řešení. Jestliže číslo b není dělitelné číslem d = (ai,..., an), nemůže mít (30) žádné řešení, protože pro libovolná celá čísla x±,..., xn je levá strana (30) dělitelná číslem d. Jestliže naopak d \ b, můžeme celou rovnici (30) vydělit číslem d. Dostaneme tak ekvivalentní rovnici a[xi + a'2x2 + • • • + a'nxn = b', kde a'i = ai/d pro i = l,...,nab' = b/d. Přitom platí d ■ (a'1;..., a'n) = (da,i,..., da'n) = (a±,..., an) = d, a tedy (a[,..., a'n) = 1. V následující větě ukážeme, že taková rovnice má vždy řešení, a proto naše úvahy můžeme shrnout takto: rovnice (30) má celočíselné řešení, právě když číslo b je dělitelné největším společným dělitelem čísel a±, a2,..., an. věta 39. Nechť n > 2. Rovnice d\X\ + 02^2 + ' ' • + o,nxn = b, (31) kde ai, a,2,..., an, b jsou celá čísla taková, že (ai,..., an) = 1, má vždy celočíselné řešeni. Všechna celočíselná řešeni této rovníce je možné popsat pomocí n — 1 celočíselných parametrů. DŮKAZ. Provedeme indukcí vzhledem k počtu n neznámých x,i v rovnici (31). Je výhodné formálně začít s případem n = 1, kdy podmínka (ai) = 1 znamená, že a\ = ±1. Tehdy rovnice (31) má tvar buď x\ = b, 69 nebo —x\ = b, a tedy jediné řešení, které zřejmě nezávisí na žádném parametru, což odpovídá tomu, že n — 1 = 0. Předpokládejme, že n > 2 a že věta platí pro rovnice o n — 1 neznámých; dokážeme ji pro rovnici (31) o n neznámých. Označme d = (a1;..., an_i). Pak libovolné řešení x1}..., xn rovnice (31) triviálně splňuje kongruenci a\X\ + a2^2 + • • • + anxn = b (mod d). Vzhledem k tomu, že d je společný dělitel čísel a1;... ,an_i, je tato kongruence tvaru anxn = b (mod d). Protože platí, že (d, an) = (ai,..., an_i, an) = 1, má podle věty 21 tato kongruence řešení xn = c (mod d), kde c je vhodné celé číslo, neboli xn = c + d ■ t, kde ŕ G z je libovolné. Dosazením do (31) a úpravou dostaneme a\X\ + • • • + an_ixn_i = b — anc — andt. Protože anc = b (mod d), je číslo (6 — anc)/d celé a poslední rovnici můžeme vydělit číslem d. Dostaneme pak rovnici Ct-^Xi ~\~ ' ' ' ~\~ CLn_-yXn—\ = b , kde a'i = ajd pro i = 1,... ,n — 1 a 6' = ((& — anc)/d) — ant. Protože (a[,a'^) = (da[,da'^) ■ \ = (a1;..., an_x) • i = 1, podle indukčního předpokladu má tato rovnice pro libovolné ŕ G z řešení popsatelné pomocí n — 2 celočíselných parametrů. Přidáme-li k tomuto řešení podmínku xn = c + áí, dostaneme řešení rovnice (31) popsané pomocí n — 2 původních parametrů a nového parametru t. Důkaz indukcí je hotov. □ Metodu z důkazu věty 39 použijeme na řešení následujících diofan-tických rovnic, v nichž z důvodů přehlednosti zápisu budeme neznámé značit x, y, z,... místo x±,X2, x%,.... příklad. 5x + 7y = 8. ŘEŠENÍ. Libovolné řešení této rovnice musí splňovat kongruenci 5x + 7y = 8 (mod 5), tedy 2y = —2 (mod 5)), odkud y = — 1 (mod 5)), tj. y = — 1 + 5í pro ŕ G z. Dosazením do dané rovnice dostaneme 5x + 7(-l + 5ť) = 8, odkud vypočítáme x = 3 — 7t. Řešením naší rovnice je tedy x = 3 — 7t, y = — 1 + 5í, kde ŕ je libovolné celé číslo. □ 70 příklad. 91a: - 28y = 35. ŘEŠENÍ. Protože (91, 28) = 7 a 7 | 35, má rovnice celočíselné řešení. Vydělme ji sedmi: 13x — Ay = 5. Libovolné řešení této rovnice musí splňovat kongruenci 13x — Ay = 5 (mod 13), tj. —Ay = —8 (mod 13), odkud y = 2 (mod 13) a y = 2 + 13í pro ŕ G z. Dosazením 13x - 4(2 + 13í) = 5, odkud vypočteme x = 1+41 Řešením je tedy x = l+4ŕ, y = 2+13Í, kde t je libovolné celé číslo. Tentýž výsledek bychom samozřejmě dostali, i kdybychom uvažovali kongruenci podle modulu 4 místo 13. Protože řešit kongruenci podle menšího modulu bývá snadnější, je vhodné na to pamatovat a uspořádat si výpočet tak, aby nebylo nutné pracovat s kongruencemi podle velkých modulů. □ příklad. 18x + 20y + 15z = l. ŘEŠENÍ. Protože (18,20,15) = 1, má rovnice celočíselné řešení. Libovolné řešení musí splňovat kongruenci (za modul volíme největší společný dělitel čísel 18, 20) 18x + 20y + 152 = 1 (mod 2), tedy z = 1 (mod 2), odkud z = 1 + 2s, kde s G z. Dosazením 18x + 20í/ + 15(1 + 2s) = 1 odkud po vydělení dvěma a úpravě dostaneme rovnici, 9x + Wy = -7 - 15s kterou budeme řešit pro libovolné s G z. Je-li tato rovnice splněna, musí platit 9x + 10y = -7- 15s (mod 9), odkud y = 2+3s (mod 9), a proto y = 2+3s+9í, kde ŕ G z. Dosazením 9x + 10(2 + 3s + 9í) = -7 - 15s, odkud po úpravě rr = —3 — 5s — lOt. Řešení dané rovnice jsou tedy trojice x = —3 — 5s — 10í y = 2 + 3s + 9t z=l + 2s kde s, t jsou libovolná celá čísla. □ příklad. 15x - 12y + 48,2 - 51u = 1. ŘEŠENÍ. Protože (15,12,48,51) = 3 není dělitel čísla 1, nemá rovnice celočíselné řešení. □ 71 6.2. Diofantické rovnice lineární vzhledem k některé neznámé. Jde o rovnice, které můžeme upravit do tvaru mxn = F(x1,... ,xn_i), (32) kde m je přirozené číslo a F(xi,... ,xn-i) mnohočlen s celočíselnými koeficienty. Je zřejmé, že má-li být xi,X2,... ,xn celočíselným řešením rovnice (32), musí platit F(xi,..., rrn_i) = 0 (mod m). (33) Naopak, je-li x±,..., rcn_i řešení kongruence (33), pak pro xn = F(xi,... ,x, dostaneme celočíselné řešení x±,..., xn-i, xn rovnice (32). Proto pro řešení rovnice (32) postačí vyřešit kongruenci (33). V případě n = 2, tj. v případě, kdy je mnohočlen F(xľ) mnohočlenem jedné proměnné, jde o úlohu, kterou jsme se zabývali v části 4. Případ n > 2 je však možné řešit zcela analogicky pomocí následující věty. věta 40. Pro libovolný mnohočlen F(x1}..., xs) s celočíselnými koeficienty, přirozené číslo m a celá čísla a1}..., as, b1}..., bs taková, že a\ = bi (mod m), . as = bs (mod m), platí F(a1}... ,as) = F(pi,...,bs) (mod m). důkaz. Snadný. □ Pro nalezení všech řešení kongruence (33) tedy postačí dosazovat do mnohočlenu F(xi,..., xn-i) za x±,..., xn-\ nezávisle na sobě postupně čísla 0,1, 2,..., m — 1 (tj. celkem mn_1-krát). A právě tehdy, když pro čísla ai,..., an-i je splněna podmínka F(ai,..., an_i) = (mod m), dostáváme řešení kongruence (33) ve tvaru xi = ai + rriti, ..., xn_i = an_i + mrn_1? kde ti,... ,tn-i mohou nabývat libovolných celočíselných hodnot. Tak dostaneme i řešení rovnice (32): xi = ai + mti, 1 xn = —F(a1 + mri,..., an_i + mrn_i). m příklad. Řešte diofantickou rovnici 7x2 + 5y + 13 = 0. řešení. Rovnici upravíme na tvar 5y = —7x2 — 13 a budeme řešit kongruenci -7x2 - 13 = 0 (mod 5), tj. 3x2 = 3 (mod 5), odkud x2 = 1 (mod 5). Dosadíme-li za x čísla 0, 1, 2, 3, 4, zjistíme, že kongruence je splněna pro čísla 1 a 4. Řešením této kongruence jsou tedy podle 4.11 právě čísla x = 1 + 5í nebo x = 4 + 5í, 72 kde ŕ G z. Dosazením dostaneme v prvním případě 5y = -7(1 + 5r)2 - 13 = -7 - 70t - 175r2 - 13 a tedy y = _4 - Ut - 35t2, ve druhém případě 5y = -7(4 + 5r)2 - 13 = -112 - 280ŕ - 175r2 - 13, a proto y = -25- 56ŕ - 35ŕ2. Řešením dané rovnice jsou tedy právě všechny dvojice čísel x,y tvaru x = l + 5t,y = -4-14ŕ-35ŕ2 nebo x = 4 + 5ŕ, y = -25-56ŕ-35ŕ2, kde ŕ je libovolné celé číslo. □ příklad. Řešte diofantickou rovnici x (x + 3) = 4y — 1. řešení. Rovnici upravíme na tvar 4y = x2 + 3x + 1 a budeme řešit kongruenci x2 + 3x + l = 0 (mod 4). Dosazením čísel 0, 1, 2, 3 zjistíme, že kongruenci nesplňuje žádné z nich, a tedy tato kongruence nemá řešení. Řešení proto nemá ani daná rovnice. □ příklad. Řešte diofantickou rovnici x2 + 4z2 + 6x + 7y + 8z = 1. řešení. Rovnici upravíme na tvar 7y a doplníme na čtverce 7y = -x2 - Qx - 4z2 - 8z + 1 7y = -(x + 3)2 - (2z + 2)2 + 14. Proto budeme řešit kongruenci (x + 3)2 + (2z + 2)2 = 0 (mod 7) (34) Nyní bychom mohli za uspořádanou dvojici (x; z) postupně dosazovat uspořádané dvojice (0; 0), (0; 1), ..., (0; 6), (1; 0), (1; 1), • • •, (6; 5), (6; 6) a spočítat pro všech 49 hodnot výraz stojící na levé straně kongruence (34). Výhodnější ale bude využít tvaru kongruence (34) a odvolat se na tvrzení 3.1, odkud pro p = 7, a = x + 3, b = 2z + 2 dostaneme, že z kongruence (34) plyne x + 3 = 2z + 2 = 0 (mod 7), a tedy všechna řešení kongruence (34) jsou tvaru x = — 3 + 7t, z = — 1 + 7s, kde t, s jsou celá čísla. Dosazením do rovnice dostaneme 7y = -(x + 3)2 - (2z + 2)2 + 14 = -49r2 - 196s2 + 14, 73 odkud y = -7t2 - 28s2 + 2. Řešením dané rovnice jsou tedy právě všechny trojice čísel x, y, z tvaru x = -3 + 7t, y = -7t2 - 28s2 + 2, z = -l + 7s, kde s, t jsou libovolná celá čísla. □ 6.3. Rovnice jiného tvaru. Metodu, kterou jsme řešili předchozí příklady, je možno popsat také takto: „vyjádři některou z neznámých pomocí ostatních a zkoumej, kdy je celočíselná". Skutečně, vyjádříme-li z rovnice (32) neznámou xn, dostaneme F{x\^ • • • , l) Xr, m což je celé číslo, právě když m \ F(xi,... ,xn_i), tj. právě když je splněna kongruence (33). Ukážeme si na příkladech, že tento postup je použitelný i na rovnice, které nejsou tvaru (32). V příkladech uvedeme i případ, kdy je vhodné vyjádřit namísto některé neznámé nějaký jiný vhodný výraz a zkoumat, za jakých okolností bude celočíselný. příklad. Řešte diofantickou rovnici 3X = Ay + 5. řešení. Vyjádřeme z této rovnice neznámou y: Je-li x < 0, je 0 < 3X < 1, a tedy ±(3X - 5) i z. Pro x > 0 platí 3X - 5 = {-l)x - 1 (mod 4); číslo (—l)x — 1 je kongruentní s nulou podle modulu 4 právě tehdy, když x je sudé, tj. x = 2k, kde k G No- Řešením této diofantické rovnice jsou tedy právě všechny dvojice 9k -5 x = 2k, y = kde A; G No je libovolné. □ příklad. Řešte v z rovnici x(y + l)2 = 243y. Řešení. Vyjádřeme neznámou x: 243y X (ž/ + l)2' Aby x G z, musí {y + l)2 být dělitelem čísla 243y. Protože y a, y + 1 jsou nesoudělná čísla pro libovolné y G z, musí být {y + l)2 dělitelem čísla 243 = 35. Toto číslo má však jen tři dělitele, kteří jsou druhou mocninou celého čísla: 1,9 a 81. Proto musí nastat některá z těchto 74 možností: y + 1 = ±1, y + 1 = ±3 nebo y + 1 = ±9. Dostáváme tedy šest řešení dané rovnice: y = 0, x = 0, y = -2, x = -2 • 243 = -486, y = 2, x = 2 ■ 27 = 54, y = -4, x =-4-27 =-108, y = 8, x = 8 • 3 = 24, y = -10, x =-10 • 3 =-30. Jiná řešení daná diofantická rovnice nemá. □ příklad. Řešte v z rovnici y/x + y/y = V1988 . řešení. Odečteme-li od obou stran rovnice y/y a umocníme-li na druhou, dostaneme x = 1988 -4^7-71 -y + y. Jsou-li x, y celá čísla, je i Ay/7 ■ 71y celé číslo, a tedy y/7~7\y je racionálni číslo. Pak je y/T^TYy = k nezáporné celé číslo. Platí tedy 7 • 71y = k2, odkud plyne, že k2 a tedy i k je dělitelné prvočísly 7, 71. Je tedy k = 7 ■ 71í pro vhodné ŕ G N0 a tedy V = = 497ŕ2. y 7-71 Zcela analogicky je možné odvodit, že existuje s G N0 tak, že x = 497s2. Dosazením do původní rovnice dostáváme VA97s + V497Í = V1988, odkud po vydělení plyne s + t = 2. Jsou tedy tři možnosti: s = 0, t = 2 nebo s = t = 1 nebo s = 2, t = 0, takže daná diofantická rovnice má tři řešení: x = 0, y = 1988 nebo x = y = 497 nebo x = 1988, y = 0. □ 6.4. Řešení diofantických rovnic pomocí nerovností. Tato metoda je založena na tom, že pro libovolná reálná čísla a, b existuje jen konečně mnoho celých čísel x tak, že a < x < b. Proto při řešení dané rovnice hledáme taková čísla a, b, aby nerovnosti a < x < b pro některou neznámou x byly důsledkem této rovnice. Konečně mnoho celých čísel ležících mezi čísly a, b pak můžeme jedno po druhém dosadit do rovnice za x a tím j i zjednodušit. Ukažme si to na následujících příkladech. příklad. Řešte diofantickou rovnici 6x2 + 5y2 = 74. 75 řešení. Protože pro libovolné y G z platí 5y2 > 0, musí libovolné řešení x, y dané rovnice splňovat 74 = 6x2 + 5í/2 > 6x2, odkud x2 < y, tedy —3 < x < 3, proto je některé z čísel 0, 1, 4, 9. Dosazením do rovnice postupně dostáváme 5y2 = 74, 5y2 = 68, 5í/2 = 50, 5y2 = 20. První tři případy jsou ve sporu s y G z, z posledního dostáváme í/2 = 4, tj. y = ±2. Rovnice má tedy čtyři řešení: x = 3, y = 2; x = 3, y = -2; x = -3, y = 2; x = -3, y = -2. □ příklad. Řešte v z rovnici x2 + xy + í/2 = x2y2. řešení. Protože jsou v dané rovnici neznámé x, y zastoupeny symetricky, můžeme předpokládat, že x2 < y2, odkud plyne xy < y2, a tedy x y = x + xy + y < y + y + y = áy . Platí tedy y = 0 nebo x2 < 3. Dosazením do rovnice dostáváme v prvním případě x = 0, ve druhém pro x = 0 opět y = 0, pro x = 1 je í/ = — 1 a pro x = — 1 je í/ = 1. Rovnice má tedy tři řešení: x = 0, y = 0; x = 1, y = —1; x = —1, y = 1. □ příklad. Řešte v z rovnici 2X = 1 + 3^. Řešení. Je-li y < 0, platí 1 < 1 + 3^ < 2, odkud 0 < x < 1, což je spor. Je tedy y > 0 a proto 2X = 1 + 3^ > 2, odkud rr > 1. Ukážeme, že také platí x < 2. Kdyby totiž bylo x > 3, platilo by 1 +3^ = 2^ = 0 (mod8), odkud bychom dostali 3^ = -1 (mod 8), což však není možné, neboť pro sudá čísla y je 3y = 1 (mod 8) a pro lichá čísla y platí 3^ = 3 (mod 8). Zbývá tedy vyřešit případ 1 < x < 2. Pro x = 1 dostáváme 3^ = 21 - 1 = 1, a tedy i/ = 0. Zi = 2 plyne 3^ = 22 - 1 = 3, takže y = 1. Rovnice má tedy dvě řešení: x = l, y = 0ax = 2, y=l. □ příklad. Řešte rovnici x + y + z = xyz v oboru přirozených čísel. řešení. Protože jsou v dané rovnici neznámé zastoupeny symetricky, můžeme předpokládat x < y < z. Pak ale xyz = x + y + z b) odvodíme nepravdivé tvrzení. V následujících příkladech bude takovým nepravdivým tvrzením dvojice nerovností cn < dn < (c + l)n, kde c, d jsou celá a n přirozené číslo. příklad. Řešte diofantickou rovnici x{x + l)(x + 7)(x + 8) = y2. Řešení. Úpravou y2 = (x2 + 8x)(x2 + 8x + 7). Označíme-li x2 + 8x = z, je naše rovnice tvaru í/2 = z2 + 7z. Ukážeme, že z < 9. Předpokládejme naopak z > 9. Pak platí (z + 3)2 = z2 + 6^ + 9 < z2 + 7^ = y2 < z2 + 8^ + 16 = (z + 4)2, což je spor, neboť z + 3, y, z + 4 jsou celá čísla a z těchto nerovností by plynulo \z + 3| < |y| < |z + 4|. Je tedy z < 9, tj. x2 + 8x < 9, odkud (x + 4)2 = x2 + 8x + 16 < 25, a proto —5 < x + 4 < 5, neboli —9 < x < 1. Dosazením těchto hodnot do rovnice dostaneme všechna řešení: (x;y) G {(—9; 12), (—9;—12), (-8;0), (-7;0), (-4; 12), (-4;-12), (-1;0), (0;0), (1; 12), (1;-12)}. □ příklad. Řešte diofantickou rovnici (x + 2)4 — x4 = y3. Řešení. Úpravou získáme y3 = 8X3 + 2Ax2 + 32x + 16 = 8(x3 + 3x2 + Ax + 2), 77 odkud plyne, že y je sudé. Položme y = 2z, z G Z. Platí tedy z3 = x3 + 3rc2 + 4x + 2. Je-li x > 0, platí (x + l)3 = x3 + 3x2 + 3x + l 0. Předpokládejme, že má nějaké řešení Xi,yi G Z takové, že x\ < —2. Pak platí (xi + 2)4 - x\ = y3 a dosadíme-li x2 = —X\ — 2, y2 = —yi, dostaneme x% - (x2 + 2)4 = -y3, a proto x2,í/2 Je také řešení dané rovnice. Ovšem x2 = —X\ — 2 > 0 a z předchozích úvah plyne, že tato situace nastat nemůže. Dohromady tedy — 2 Vaia2 • • • an , (35) n přitom rovnost v (35) nastane, jen když a\ = a2 = ■ ■ ■ = an. důkaz. Prozatím neuveden. □ věta 42 (Bernoulliova nerovnost). \/x G IR,x > — 1, Vn G N platí: {l + x)n > 1+n-x. důkaz. Pro n = 1 nebo x = 0 je tvrzení zřejmé. Pro reálná A > B > 0 a přirozené číslo n > 2 platí: n(A - B)Bn-1 B > 0, n > 2), z čehož po dosazení A = 1 + i a 5 = 1 (pro x > 0), resp. A = 1, B = 1 + x (pro — 1 < a: < 0) dostaneme požadované tvrzení. □ příklad. v oboru přirozených čísel řešte rovnici x y z - + - + - = 3. y z x 78 řešení. Podíl přirozených čísel je číslo kladné, a proto můžeme pro čísla ^, | a ^ použít nerovnost mezi aritmetickým a geometrickým průměrem (viz Věta 41). Geometrický průměr těchto tří čísel je 1, a proto pro jejich aritmetický průměr platí 1 / x y z* . > 1, 3 \y z x/ kde rovnost nastane právě tehdy, když x y z ^ y z x Porovnáme-li získanou nerovnost s danou rovnicí, dostáváme, že rovnice má nekonečně mnoho řešení x = y = z, kde z je libovolné přirozené číslo, a žádné jiné řešení nemá. □ příklad. Dokažte, že pro libovolné přirozené číslo n > 2 rovnice xn + (x + l)n = (x + 2)n nemá řešení v oboru přirozených čísel. řešení. Předpokládejme naopak, že pro nějaká přirozená čísla x, n, kde n > 2, je daná rovnice splněna, a označme y = x+ 1 > 2. Pak platí (y-l)n + yn = (y+l)n, (36) odkud dostáváme 0 = (y + 1)" - Vn - (y - l)n = 1 - ("l)n (mod y). Připusťme, že n je liché, pak 0 = 2 (mod y), tedy y = 2 a 0 = 3n - 2n - 1, což platí pouze pro n = 1. Je tedy n sudé a podle binomické věty platí (íř + l)n=Gy+C)!' + 1 (mody3), (y-ir^y-^+i (mody3), odkud plyne 0 = (ž/ + ir-ž/n-(ž/-ir = 2ny (mody3), tedy 0 = 2n (mod y2), a proto 2n > y2. Vydělíme-li (36) číslem yn, dostaneme • l\n / l\n Naopak podle Bernoulliovy nerovnosti (viz Věta 42) platí 1 \n n 2n y2 y 1 + - >1 + - = 1 + — >1 + — = 1 + - > 2. y) y 2y~ 2y 2 " Shrneme-li předchozí úvahy, vychází, že pro žádné přirozené číslo n > 2 nemá daná rovnice řešení v oboru přirozených čísel.