79 6.5. Řešení diofantických rovnic metodou rozkladu. Tato metoda spočívá v úpravě dané rovnice do tvaru £*¥?/hC fVbUäof bWobfdh Ax-A2.....An =£^P^~ (37) kde Ai,... ,An jsou výrazy obsahující neznámé, které pro celočíselné / / hodnoty neznámých nabývají celočíselných hodnot, a B je číslo (případ- / faji^q ně výraz), jehož rozklad na prvočísla známe. Pak totiž existuje pouze / / konečně mnoho rozkladů čísla B na n celočíselných činitelů Vyšetříme-li pak pro každý z těchto rozkladů soustavu rovnic A\ = di, A2 = 0,2, • • •, An = an, získáme všechna řešení rovnice (37). Ukažme si to na příkladec příklad. Řešte diofantickou rovnici y3 — x3 =^\^ 1^ řešení. Rozložme levou stranu rovnice: čj/j „ fj}^ ,\r (y - x)(y2 + xy + x2) = 91. Protože >0 *~*>~* » >V C3_ y2 + xy + x2=(y+X-)2 + |r2 > 0, musí být také y — x > 0. Číslo 91 můžeme rozložit na součin dvou přirozených čísel čtyřmi způsoby: 91 = 1 • 91 = 7 • 13 = 13 • 7 = 91 • 1. Budeme proto odděleně řešit čtyři systémy rovnic: (1) y — x = 1, y2 + xy + x2 = 91. Dosazením y = x + 1 z první do £ Sjé ^ "druhé rovmceTlre taneme "x2 + x — 30 = 0, odkud x = 5 nebo r" , ^1 x = —6. Příslušné hodnoty druhé neznámé jsou pak y = 6, / J (2) j/__j_=_7, y2 + a^/+ x2 = 13. Pak x2 + 7x + 12 = 0, tedy C^3){X^h)^ & x = —3 a y = 4 nebo x = —4 at/ = 3. 7 4 "7 (3) y-x = 13, í/2 + xy + a:2 = 7. Nyní x2 + 13a: + 54 = 0. Tato p ' JĽ rovnice však nemá řešení v oboru reálných čísel, a proto ani *-~<7/^^| v oboru čísel celých. (4) y — x = 91, y2+xy+x2 = 1. V tomto případě a;2 + 91a;+2760 = 0. Ani tato rovnice nemá řešení v oboru reálných čísel. Daná rovnice má tedy čtyři řešení: (*;y)e{(5;6),(-6;-5),(-3;4),(-4;3)}. □ příklad. Řešte diofantickou rovnici x4 + 2x7y — x14 — y2 = 7. řešení. Upravme nejprve levou stranu rovnice: x4 + 2x7y — x14 — y2 = x4 — (x7 — y)2 = (x2 — x7 + y)(x2 + x7 — y) a uvažme, že číslo 7 můžeme rozložit čtyřmi způsoby na součin dvou celých čísel: 7 = 1-7 = 7-1 = (— 1) - (—7) = (—7) • (—1). Budeme proto řešit čtyři soustavy rovnic. 80 (1) x2 — x7 + y = 1, x2 + x7 — y = 7. Sečtením obou rovnic dostaneme x2 = 4, odkud x = 2 a y = 125, nebo x = —2 a y = -131. (2) x2 — x7 + y = 7, x2 + x7 — y = 1. Nyní x2 = 4, a tedy x = 2, í/ = 131 nebo x = —2, y = —125. (3) x2 — x7 + y = — 1, x2 + x7 — y = — 7. Sečtením x2 = —4, což je spor. (4) x2 — x7 + y = —7, x2 + x7 — y = — 1. Opět spor x2 = —4. Rovnice má tedy čtyři řešení: (x; y) e {(-2; -131), (-2; -125), (2; 125), (2; 131)}. □ K. x y p m Č ~£ příklad. Řešte diofantickou rovnici ^ t •ívwl (jO**^ ^Cj^^jkde p je libovolné prvočíslo. (jfy^Ii/ "p I XM řešení. Vynásobením číslem xyp a další úpravou dostaneme ^ ^/j" J^) ~~~0 pofeíM- X.-'-to-Xi Úprava do tvaru (37) vyžaduje nyní umělý obrat: přičteme k oběma? ' Nfl/" (J (J ' r ^ / ^ stranám rovnice p2, aby bylo možno její levou stranu zapsat jako součin: ^ -*Vl/£íVň ) j4' (*-p)(»-p)=^. , 7, , X>| l^f . M ^.fc'ty | Protože p je prvočíslo, lze p2 rozložit na součin dvou celých čísel jen ř^""]* (j'^^f "VI těmito šesti způsoby: p2 = 1 • p2 = p • p = p2 • 1 = (—1) • (—p2) = /H.Í (2) x — p = p, y — p = p, a tedy x = 2p, y = 2p; |j li*^ ^-f-j =D V.(3) x -p = p2, y - p = 1, a tedy x = p2 + p, y = p + 1; .(4) x-p = -l,y-p = -p2, a tedy x = p - 1, y = p - p2; Sjfc,/ (5) x - p = -p, y - p = -p, a tedy x = y = 0, což nevyhovuje; jj"'^ - p* ' v (6) x — p = —p2, y — p = —1, a tedy x = p — p2, y = p — 1. tytí) Daná rovnice má tedy pět řešení, popsaných v případech (l)-(4) a (6). ad by □ ) J~*a fTI 6.5.1. Pythagorova rovníce. Pythagorova rovnice se zabývá otázkou hledání všech pravoúhlých trojúhelníků s celočíselnými délkami stran. H - *íf p-- ^ příklad. V oboru přirozených čísel řešte rovnici r-f^pfrf) *2 + ž/2 = ,2. *iiJi^*/ Řešení. Označme ŕ = (x, y, z), xx = |, yx = |, ^ = |. Pak platí 81 odkud po vydělení číslem t2 ^ 0 vychází 'í '1 t yi - (38) a navíc (x1} y1} z{) = 1. Ukážeme nyní, že čísla x1; y1} Z\ jsou dokonce po dvou nesoudělná: kdyby nějaké prvočíslo p dělilo dvě z čísel Xi,yi,Zi, vyšlo by z (38), že dělí i třetí, což vzhledem k (xi,yi,Zi) = 1 není možné. Z čísel x±, y± je tedy nejvýše jedno sudé. Připusťme, že jsou obě lichá. Pak z kongruence z* = xl + y*=Q+Q (mod8) plyne, že z\ je sudé číslo, které není dělitelné 4, což není možné. Je tedy z čísel xl7 yi právě jedno sudé. Protože v rovnici (38) vystupují X\ a yi symetricky, můžeme pro určitost předpokládat, že sudé je X\ = 2r, r G n. Z (38) pak plyne , . . , . ^ . V-Zr, ľ eis) a tedy r z\ + Vi zi- yi 2 í/i). Pak zx Označme u = \[z\ + y±), v = \[z\ — y\). Pak z\ = u + v, y± u — v. Protože jsou y1} Z\ nesoudělná čísla, jsou i u, v nesoudělná čísla. Z rovnice „2 r u ■ v „ p (l&Wtl3 _ ip ( Q -f c? I -* Ď což^skutečně pro libovolné t £ n a libovolná nesoudělná a. bj2 n taková. pak plyne, že existují nesoudělná přirozená čísla a, b tak, že u v = b2 navíc vzhledem k u > v platí a > b. Celkem tedy dostáváme tx\ = 2tr = 2tab, tyl = t(u — v) = t(a2 — b2), t(u x y z t(a2 že a > b, vyhovuje dané rovnici. Zbylá řešení bychom dostali záměnou x á y (v průběhu řešení jsme předpokládali, že právě X\ je sudé): H * tf j ^f^3y^^4f^^" x = t{a2 - b2), y = 2tab, z = t{a2 + b2), kde opět t, a, b E n jsou libovolná taková, že a > b, (a, b) = 1. □ Jť-&- \ U/l/ o. 1 6.6. Řešitelnost diofantických rovnic. V předchozí čáasti jsme viděli, že řešení většiny diofantických rovnic není snadné, a ačkoli jsme se naučili několik metod, v mnoha konkrétních případech se nám nepodaří diofantickou rovnici vyřešit ani jednou z nich. Přesto se nám v těchto případech může podařit něco o řešení zjistit. Například nalézt nekonečnou množinu řešení a tím dokázat, že množina všech řešení, i když ji celou neumíme popsat, je nekonečná. Nebo naopak ukázat, že množina všech řešení je prázdná (a tím vlastně danou rovnici vyřešit), popřípadě konečná. í in- l/Jít ^f^h^ V&) ?vo y?^ J ^ J J J í -7/-T- \ J f / ď i - - -š' -~f - - -i - -/- "-T it- -fl--f- ptpfity íltiJ h%4t rviricj ß Kí***, 1 **» Zrs . f~ ŕ-ŕ. 3~Aŕ . LA r,&4, (&1 ToJk po neu ..^ľy(* -W-r - - CtŤ=* a-l'fať) . ha i'MPoLhtaxtf> -^-t--r--J"-t-jT • f r f / u íl ^ I *Tnlt> ŕ@ruf )l«Jk kjuociI ku puvocíJ, itflv^ 82 6.6.1. Neexistence řešení. Při důkazu, že nějaká diofantická rovnice nemá žádné řešení, je často možné s úspěchem využít kongruencí. Má-li totiž řešení diofantická rovnice L = P (kde L, P jsou výrazy obsahující neznámé, nabývající celočíselných hodnot pro libovolné celočíselné hodnoty neznámých), musí mít řešení i kongruence L = P (mod m) pro libovolné m g N, protože řešením této kongruence je například zmíněné řešení rovnice. Odtud plyne, že nalezneme-li nějaké přirozené číslo m tak, že kongruence L = P (mod m) nemá řešení, nemůže mít řešení ani původní diofantická rovnice L = P. Je nutno si však uvědomit, že obrácení předchozí úvahy obecně neplatí: má-li kongruence L = P MfafygfcJ^ ^ že a . ^ i a má řešení též diofantická rovnice L = P (ukážeme to v Příkladu na (mod m) pro každé přirozené číslo m řešení, neznamená to ještě, že , ^^J/lf má řešení též diofantická rovnice L = P (ukážeme to v Příkladu na ^ *™ str. 84). j?0 příklad. Řešte diofantickou rovnici ^/n&ffJ, ľ° /*! ^ + 4 + --- + ^4 = 15999. Reseni. Ukážeme, že kongruence i nema reseni, oukuu vypiyne, ze reseni nemá ani aana uioianucKa j - .v nice. Je-li totiž celé číslo n sudé, je n = 2k pro A; g Z a tedy rŕ = JV- ni (2s) 16/c4 = 0 (mod 16). Jestliže je celé číslo n liché, platí rŕ — 1 = [n — „ "~ ' 1)(n + l)(n2 + 1) = 0 (mod 16), neboť čísla n — 1, n + 1 a n2 + 1 jsou 4- ť 2 (jf) sudá a jedno z čísel n — 1, n + 1 musí být dokonce dělitelné čtyřmi. Q^JžOfl *- Znamená to tedy, že podle modulu 16 je rŕ kongruentní s 0 pro sudá n a s 1 pro lichá čísla n. Je-li proto mezi čísly xi,X2, ■ ■ ■ ,x±4 právě r 0 lichých, je efO/tčj^jbj x{ + xA2 + --- + x{A = 15999 (mod 16) nemá řešení, odkud vyplyne, že řešení nemá ani daná diofantická rov- „4 , ,4 r (mod 16). Platí 15999 = 16000 - 1 = 15 (mod 16) a protože 0 < r < 14, nemůže mít kongruence x\ + x\ + • • • + x\± = 15 (mod 16) řešení, a nemá ho tedy ani daná rovnice. □ příklad. V oboru celých čísel řešte soustavu rovnic x2 + 2y2 = z2, 2x2 + y2 = u2. řešení. Snadno ověříme, že z x = y = 0 plyne také z = u = 0, což je řešení dané soustavy. Ukážeme, že další řešení soustava nemá. Předpokládejme, že x, y, z, u je řešení a že x ^ 0 nebo y ^ 0, a označme d = (x, y) > 0 největší společný dělitel čísel x, y. Z první rovnice plyne d | z, ze druhé d \ u. Označíme-li X\ = |, yľ = |, z\ = |, iti = 83 ^, dostáváme, že (xi,yi) = 1, a po zkrácení obou rovnic číslem d2 dostaneme x\ + 2y\ = zl, 2x\ + yl=u\. Odtud plyne sečtením 3xf + 3yf = z\ + u\ a tedy 3 | z\ + u\. Podle Tvrzení 3.1 platí 3 | z±, 3 | u\ a tedy 9 | z\ + w2. Pak ale 9 | 3(x\ + í/2), a tedy 3 | x\+y\. Opět podle Tvrzení 3.1 platí 3 | x±, 3 | y±, což je spor s (xi,yi) = 1. Soustava má tedy jediné řešení x = y = z = u = 0. □ příklad. V oboru přirozených čísel řešte rovnici 1! + 2! + 3! + ••• + x\ = y2. řešení. Přímým výpočtem se přesvědčíme, že pro x < 5 vyhovují rovnici pouze x = y= lax = y = 3. Ukážeme, že pro x > 5 rovnice řešení nemá. Protože pro libovolné n > 5 je n\ dělitelné pěti, platí 1! + 2! + 3! + • • • + x\ = 1! + 2! + 3! + 4! = 33 = 3 (mod 5). Ovšem druhá mocnina přirozeného čísla je podle modulu 5 kongruentní s 0 nebo 1 nebo 4. Kongruence 1! + 2! + • • • + x\ = y2 (mod 5) pro x > 5 tedy nemá řešení, a proto nemá pro x > 5 řešení ani daná rovnice. □ příklad. V oboru přirozených čísel řešte rovnici x2 - y3 = 7. řešení. Ukážeme, že daná rovnice nemá řešení. Předpokládejme naopak, že pro vhodná x, y g Z platí x2 — y3 = 7. Kdyby y bylo sudé, platilo by x2 = 7 (mod 8), což není možné. Je tedy y liché, y = 2k + 1 pro k E Z. Pak platí x2 + 1 = y3 + 23 = (y + 2) (y2 - 2y + 4) = (39) = (y + 2)((y - l)2 + 3) = (2k + 3)(4A;2 + 3). (40) Číslo 4A;2 + 3 musí být dělitelné nějakým prvočíslem p = 3 (mod 4). V opačném případě vzhledem k tomu, že Ak2 + 3 je liché, by totiž v rozkladu čísla Ak2 + 3 na prvočísla vystupovala pouze prvočísla kongruentní s 1 podle modulu 4 a tedy by i jejich součin Ak2 + 3 musel být kongruentní s 1 podle modulu 4, což jistě není. Je tedy 4A;2 + 3 dělitelné prvočíslem p = 3 (mod 4), a tedy platí x2 + 1 = 0 (mod p). Podle Tvrzení 3.1 odtud plyne x = 1 = 0 (mod p), a to je spor. □ Nyní uvedeme slibovaný příklad toho, že diofantická rovnice nemusí být řešitelná ani v případě, že je kongruence L = P (mod m) řešitelná pro libovolný modul m g N. 84 příklad. Dokažte, že kongruence 6a;2 + 5a; + 1 = 0 (mod m) má řešení pro každé přirozené číslo m, a přitom diofantická rovnice 6x2 + 5a; + 1 = 0 řešení nemá. Řešení. Platí 6x2 + 5a; + 1 = (3a; + l)(2x + 1), a tedy rovnice 6a;2 + 5a; + l = 0 nemá celočíselné řešení. Nechť m je libovolné přirozené číslo a platí m = 2n ■ k, kde n G N0 a fc je liché číslo. Protože (3, 2n) = (2, k) = 1, mají obě kongruence soustavy 3a: = -1 (mod2n) 2a; = —1 (mod k) podle Věty 21 řešení, a protože (2n,k) = 1, má podle Věty 23 řešení i celá soustava. Pro libovolné x vyhovující této soustavě je pak 3a; + 1 dělitelné číslem 2n a 2a; + 1 číslem k a proto součin (3a; + l)(2a; + 1) je dělitelný číslem 2n ■ k = m. Je tedy x řešením kongruence 6a;2 + 5a; + 1 = 0 (mod m). □ 6.6.2. Zmenšování ad absurdum. Je to metoda důkazu neexistence řešení diofantické rovnice. Při důkazu touto metodou libovolné řešení dané diofantické rovnice charakterizujeme nějakým přirozeným číslem (například největším společným dělitelem hodnot některých neznámých nebo druhou mocninou hodnoty některé neznámé a podobně) a ukážeme, že existuje-li řešení charakterizované přirozeným číslem d, musí existovat jiné řešení, charakterizované přirozeným číslem ď < d. Pak totiž žádné takové řešení existovat nemůže, o čemž se snadno můžeme přesvědčit sporem: kdyby existovalo, mohli bychom zvolit to řešení, které je ze všech řešení charakterizováno co nej menším přirozeným číslem d; pak by ovšem muselo existovat i jiné řešení, charakterizované přirozeným číslem ď < d, což však by byl spor s volbou d. příklad. Řešte diofantickou rovnici a;3 + 2y3 + Az3 — 6xyz = 0. Kj*-^S£ řešení. Rovnici jistě vyhovuje x = y = z = 0. Ukážeme, že jiné řešení rovnice nemá. Označme d = x2+y2+z2 a předpokládejme, že pro nějaké řešení x, y, z dané rovnice platí d > 0. Z původní rovnice plyne, že a;3 je sudé číslo, a proto je x = 2x\ pro vhodné x\ G z. Dosazením do rovinceaosMn^me 8a;3 + 2y3 + Az3 - 12W = 0, ^ _ po vydělení dvěma ^ ^ C^aMÍH ^ ' Ax31+y3 + 2z3-Qx1yz = 0, ^ 85 r* a proto i y3 je sudé číslo, tedy y = 2y\ pro vhodné y\ G z. Dosazením a vydělením dvěma dostaneme 2x\ + Ay\ + z3 - §xxyxz = 0, odkud plyne, že z3 je také sudé číslo, a proto z = 2z\ pro vhodné Z\ G z. Dosazením a vydělením dvěma dostaneme x\ + 2y3 + 4^3 - 6a;ií/i;zi = 0, a tedy Xi,yi,zi je řešení původní diofantické rovnice, přičemž platí r2 ?/2 z2 d Á^t* 2,2,2 x , y , ^ " ^ j ^i + ž/i+^i = -r + -r + -r = 7< «• 1 ^ 1 4 4 4 4 Podle metody popsané v 6.4 daná diofantická rovnice nemá řešení s vlastností d > 0, a tedy x = í/ = 2 = 0je jejím jediným řešením. □ příklad. V oboru přirozených čísel řešte rovnici x2 + y2 = 4Z. řešení. Užijeme metodu 6.6.2 pro d = z. Předpokládejme nejprve, že x, y, z je řešením dané rovnice. Pak jistě platí z / 1, protože je-li x = y = 1, platí x2 + y2 = 2 < 4, a je-li alespoň jedno z čísel x, y větší než jedna, je x2 + y2 > 4. Je tedy z > 1 a platí x2 + í/2 = 4Z = 0 (mod 8). Protože druhá mocnina lichého čísla je kongruentní s 1 podle modulu 8 a druhá mocnina sudého čísla je kongruentní s 0 nebo 4 podle modulu 8, plyne z této kongruence, že x i y jsou sudá, a tedy x = 2x±, y = 2yi pro vhodná x±,yi G n. Pak ovšem a tedy, označíme-li z\ = z — 1 G n, čísla x±,yi, z\ splňují danou rovnici, přičemž z\ < z. Proto daná rovnice nemá řešení. příklad. Řešte diofantickou rovnici x4 + y4 + z4 = 9u4. řešení. Je-li u = 0, musí být rovněž x = y = z = 0, což je řešení dané rovnice. Ukážeme, že jiné řešení rovnice nemá. Předpokládejme, že celá čísla x, y, z, u vyhovují dané rovnici, přičemž a označme d = u4. Kdyby číslo u nebylo dělitelné pěti, bylo by u4 = 1 (mod 5) podle Fermatovy věty, a tedy by platilo x4 + y4 + z4 = A (mod 5), což však není možné, neboť podle Fermatovy věty každé z čísel x4, y4, z4 může být podle modulu 5 kongruentní pouze s 0 nebo 1. Je tedy u dělitelné pěti, u = 5uľ pro vhodné ui G z, a platí x4 + y4 + z4 = 0 (mod 5), odkud plyne, že čísla x,y,z jsou dělitelné pěti, tj. x = 5x±, y = 5y±, z = 5zi pro vhodná x±,yi,zi G z. Dosazením do rovnice a vydělením 54 dostaneme xi + Ví + zi = 9MÍ? 86 a tedy xi,yi,xi,ui vyhovují dané rovnici. Přitom platí v4 A U A 7 u-, = — < u = a. 1 54 □ příklad. Řešte diofantickou rovnici x2 + y2 + z2 = 2xyz. řešení. Rovnice jistě splňuje x = y = z = 0. Ukážeme, že další řešení tato rovnice nemá. Dokážeme dokonce silnější tvrzení: žádná rovnice x2 + y2 + z2 = 2uxyz, (41) kde x,y, z G Z a u G N nemá jiné řešení než x = y = z = 0, u E N libovolné. Předpokládejme, že x, y, z G Z, u G N vyhovují rovnici (41) & že d = x2 + y2 + z2 > 0. Protože it > 1, je 2uxyz sudé číslo, a proto i x2 +y2 + z2 je sudé číslo. To ale znamená, že právě jedno z čísel x, y, z, nebo všechna tři jsou sudá. V prvním případě je však x2 + y2 + z2 = 1 + 1 + 0 = 2 (mod4), kdežto Txyz = 0 (mod 4), neboť u > 1 a jedno z čísel rr, y, z je sudé. Nastane tedy druhý případ a čísla X\ = |, yi = ^, ^ = | jsou celá. Položme u^w+la dosaďme do (41): 4x? + Ay\ + 4^2 = • 2xi • 2í/i • 2^, po vydělení čtyřmi ^ + í/12 + 2;12 = 2Ul -XiyiZi, a tedy rri, y±, Zi,u± vyhovují rovnici (41). Přitom platí 0 < xf+yf+zf = | < d, neboť d > 0. Podle 6.6.2 tedy rovnice (41) může mít jen řešení s vlastností d = 0, což jsou výše uvedená řešení x = y = z = 0, iíGN libovolné. Speciálně, zadaná rovnice má jediné řešení x = y = z = 0. □ 6.6.3. Početnost množiny řešeni. V mnoha případech, kdy neumíme najít všechna řešení diofantické rovnice, se nám může alespoň podařit rozhodnout, zda řešení je konečně či nekonečně mnoho. Konečnost je například zaručena zjištěním, že hodnoty neznámých jsou v absolutní hodnotě menší než nějaké číslo. Pokud toto číslo nalezneme a je „rozumně" malé, můžeme pak najít všechna řešení metodou popsanou v 6.4 To, že daná diofantická rovnice má řešení nekonečně mnoho, můžeme dokázat například tak, že nalezneme pro každou neznámou nějaký výraz s parametrem, a to takový, že po dosazení do rovnice dostaneme rovnost, přitom pro nekonečně mnoho hodnot parametru dostaneme navzájem různé hodnoty neznámých (jde tedy o jakousi zkoušku nekonečně mnoha řešení). Nebo můžeme nalézt jedno řešení rovnice a