Základy důkazů

Autor

Patrik Bak

1Úvod

Běžná představa o matematice je, že je o počítání. Ve skutečnosti je však o porozumění obecně platných tvrzení. Abychom měli jistotu, že jde opravdu o platná tvrzení, a ne nějakou chybu měření, tak tato tvrzení precizně zdůvodňujeme, resp. dokazujeme. Nemůže být tedy pro nás překvapením, že důkazy jsou nedílnou součástí matematické olympiády, stejně jako vysokoškolských kurzů. V tomto materiálu si uděláme základní přehled o tom, jak vypadají důkazy v matematice. Ilustrujeme si je na několika příkladech. Ukázkové příklady budou hlavně o číslech, kde se principy nejlépe ilustrují. Popsaná teorie se však samozřejmě dá aplikovat i v jiných oblastech – s důkazy se setkáme ve všech materiálech.

2Základní typy důkazů

V obecnosti rozlišujeme dva základní typy důkazů: přímý důkaz a důkaz sporem. V krátkosti:

Přímý důkaz: Z platných tvrzení odvodíme dokazované tvrzení.
Důkaz sporem: Předpokládáme, že dokazované tvrzení neplatí a snažíme se odvodit matematicky neplatné tvrzení, dojít ke sporu.

Toto si umíme představit takto: Řekněme, že všechna tvrzení, ze kterých vycházíme, se nacházejí ve velkém hrnci s polévkou. Proces dokazování spočívá v kombinování tvrzení z polévky a přidávání nových z nich – pokud například máme v polévce $a^3=1$ , tak do polévky můžeme přidat $a=1$ , díky čemuž můžeme do polévky přidat $a^4-2a+1=0$ , atd. Naše dva typy důkazů potom vnímáme následovně:

Přímý důkaz funguje tak, že do polévky postupně přidáváme nová a nová tvrzení, až tam přidáme to, které cílíme dokázat.
Na druhé straně, při důkazu sporem do polévky přidáme negaci dokazovaného tvrzení a pokračujeme, jako bychom dokazovali přímo. Nová tvrzení přidáváme, dokud se nám polévka nesrazí a nedostaneme nějaký nesmysl, jako např. $0=1$ , případně opak některého z předpokladů.

V následujících dvou sekcích si ukážeme konkrétní zajímavé příklady důkazů. Ještě předtím dvě poznámky:

Velmi důležitá technika je důkaz matematickou indukcí. Přísně vzato nejde o typ důkazu, jako spíše o recept na přidávání nových platných tvrzení do polévky.
Ve škole se zvyknou rozlišovat dva typy nepřímých důkazů: nepřímý důkaz sporem a důkaz obměněné implikace. Vysvětlíme, že druhý jmenovaný je vlastně speciálním případem důkazu sporem.

2.1Přímý důkaz

Přímé důkazy jsou vcelku přirozené – kombinujeme předpoklady ze zadání s existujícími znalostmi, dokud nedojdeme k dokazovanému tvrzení. Každý důkaz se tedy dá zapsat jako série řetězců implikací:

Příklad 1

Dokažte, že druhé mocniny lichých čísel dávají po dělení 8 zbytek 1.

✓Řešení

Nejprve si vezmeme tento ucelený zápis důkazu:

Lichá čísla se dají napsat ve tvaru $m=2n+1$ pro celá $n$ . Dokazujeme, že $m^2=(2n+1)^2=4n(n+1)+1$ dává po dělení 8 zbytek 1. Jedno z čísel $n$ , $n+1$ je sudé, takže $n(n+1)$ je sudé číslo, takže $4n(n+1)$ je dělitelné 8, takže $m^2=4n(n+1)+1$ dává po dělení 8 zbytek 1, což bylo třeba dokázat.

Než půjdeme dál, uvědomme si strukturu toho důkazu. Skládá se z těchto tvrzení:

$V_0$ : $m$ je liché celé číslo
$V_1$ : $m=2n+1$ pro nějaké celé $n$
$V_2$ : $n$ je celé, tedy $n$ je sudé nebo $n+1$ je sudé
$V_3$ : $n(n+1)$ je sudé
$V_4$ : $4n(n+1)$ je dělitelné 8
$V_5$ : $4n(n+1)+1$ dává po dělení 8 zbytek 1
$V_6$ : $(2n+1)^2$ dává po dělení 8 zbytek 1
$V_7$ : $m^2$ dává po dělení 8 zbytek 1

Důkaz spočívá v přechodech $V_0 \Rightarrow V_1$ a $V_2 \Rightarrow V_3 \Rightarrow V_4 \Rightarrow V_5 \Rightarrow V_6$ . Kombinací $V_1$ a $V_6$ dostáváme $V_7$ .

Slovní zápis je zjevně praktičtější než odrážkový. Jeho problémem může být, že se v něm umí ztratit komplikovanější úlohy: Špatně sepsaná řešení často pohoří na tom, že z textu nejsou jasné implikace. Praktická rada: při každém tvrzení si položit otázku: je jasné, jaké jsou předpoklady a jak se z nich něco odvodilo? Při takové sebekontrole si člověk nejednou uvědomí, že jeho řešení má chybu.

Cvičení 1

Dokažte, že pro prvočísla $p \ge 5$ platí, že $p^2-1$ je číslo dělitelné 24.

✓Řešení

Výraz rozložíme na součin $(p-1)(p+1)$ . Jelikož $p$ je prvočíslo větší než 3, není dělitelné 3, tedy dává zbytek 1 nebo 2. V prvním případě dělí 3 činitel $p-1$ , ve druhém $p+1$ . Zároveň je $p$ liché, takže $p-1$ a $p+1$ jsou dvě po sobě jdoucí sudá čísla. Jedno z nich je proto dělitelné 2 a druhé dokonce 4, jejich součin je tedy dělitelný 8. Jelikož je číslo $p^2-1$ dělitelné 3 i 8, a tato čísla jsou nesoudělná, je dělitelné i 24.

Pro zajímavost uveďme ještě jedno řešení, které používá poznatek z předešlého příkladu: čtverce lichých čísel dávají po dělení 8 zbytek 1: Díky tomu vlastně máme, že $p^2-1$ je dělitelné 8 – zbývá zdůvodnit, že $p^2-1$ je dělitelné 3. Jelikož $p$ není 3, tak $p$ je ve tvaru buď $3k+1$ nebo $3k-1$ pro nějaké $k$ , ve zkratce $p=3k \pm 1$ . Potom

p^2-1 = (3k \pm 1)^2 - 1 = 9k^2 \pm 6k = 3(3k^2 \pm 2k),

což je zřejmě dělitelné třemi.

V těžších úlohách nemusí být hned zřejmé, jak předpoklady ze zadání využít a je potřeba analyzovat situaci.

Příklad 2

Dokažte, že pokud je přirozené číslo $n$ druhou mocninou celého čísla, tak má lichý počet dělitelů.

✓Řešení

Jak využít, že $n$ je druhá mocnina celého čísla? Můžeme si zapsat $n=m^2$ , což byl první krok v předešlém ukázkovém příkladu – to nám ale dlouho nepomůže. Klíčem je zamyslet se nad děliteli, konec konců, o těch něco dokazujeme. Základní myšlenka je:

Dělitelé přirozeného čísla typicky chodí v párech, $d$ je dělitel $n$ právě tehdy, když $n/d$ je dělitel $n$ . Pokud by se nikdy nestalo, že jde o stejné dělitele, tak počet dělitelů čísla $n$ je tedy sudý.

Kdy se ale stane, že toto párování páruje dělitele se sebou samým? Právě když $d=n/d$ , tedy když $d^2=n$ . A to je přesně náš předpoklad! Tím pádem se všichni dělitelé až na dělitele $\sqrt{n}$ s nějakým spárují, dohromady tedy budeme mít lichý počet dělitelů, což bylo třeba dokázat.

Poznámka. Tento příklad ve skutečnosti platí jako ekvivalence. Ve skutečnosti by byl lehčí, pokud by byla zadaná obrácená implikace, neboť fakt, že je čtverec, se v úvahovém řetězci používá až na konci. V soutěžních úlohách je ale běžné, že autoři se snaží tyto klíčové kroky zamaskovat.

Předešlý příklad se dá vyřešit i pomocí obecně užitečného vzorce pro počet dělitelů:

Tvrzení 1

Nechť $n=p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$ , kde $p_1,p_2,\dots,p_k$ jsou navzájem různá prvočísla a $a_1,a_2,\dots,a_k$ jsou celá čísla. Potom má číslo $n$ právě

(a_1+1)(a_2+1)\cdots (a_k+1)

dělitelů.

Důkaz

Uvažujme libovolného dělitele $d$ čísla $n$ . Jelikož $d$ dělí $n$ a prvočíselný rozklad $n$ obsahuje pouze prvočísla $p_1,\dots,p_k$ , i rozklad čísla $d$ musí obsahovat pouze tato prvočísla. Zapišme tedy $d = p_1^{b_1} \cdot p_2^{b_2} \cdots p_k^{b_k}$ . Přitom pro každé $i$ musí platit $0 \leq b_i \leq a_i$ (horní hranice plyne z toho, že $d$ jako dělitel $n$ by nemohl obsahovat vyšší mocninu $p_i$ než $n$ ). Každého dělitele tedy umíme jednoznačně reprezentovat jako $k$ -tici $(b_1,\dots,b_k)$ s vlastností $0 \leq b_i \leq a_i$ . Počet dělitelů je proto roven počtu takovýchto $k$ -tic.

Na určení počtu $k$ -tic použijeme kombinatorické pravidlo součinu. Volby jednotlivých exponentů $b_1,\dots,b_k$ jsou na sobě nezávislé – hodnota $b_i$ nijak neomezuje hodnoty ostatních exponentů. Pro exponent $b_i$ máme $a_i+1$ možností, konkrétně všechna čísla od $0$ do $a_i$ . Podle pravidla součinu je celkový počet $k$ -tic roven

(a_1+1)(a_2+1)\cdots (a_k+1).

Cvičení 2

Dokažte předešlý příklad, tedy větu o lichosti počtu dělitelů druhých mocnin, pomocí věty o počtu dělitelů. Dokažte také obrácenou implikaci této věty.

✓Řešení

Nechť $n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$ . Jelikož $n$ je druhá mocnina celého čísla, všechny exponenty $a_1, \dots, a_k$ musí být sudé. Podle věty je počet dělitelů roven součinu $(a_1+1)(a_2+1)\cdots(a_k+1)$ . Jelikož každé $a_i$ je sudé, každá závorka představuje liché číslo. Součin lichých čísel je vždy lichý, tedy počet dělitelů je lichý.

Úloha 1

Je dáno složené číslo $n > 1$ . Dokažte, že je dělitelné prvočíslem nepřevyšujícím $\sqrt{n}$ .

1Nápověda

Číslo $n$ je složené, napišme si ho $ab$ , kde $1<a \leq b<n$ .

2Nápověda

Idea je říci, že menší z čísel $a,b$ , tedy $a$ , je dělitelné dost malým prvočíslem. K tomu stačí říci, že samo o sobě je dost malé (v nejtěsnějším případě je samo prvočíslem).

✓Řešení

Jelikož $n$ je složené, můžeme ho napsat jako $n=ab$ , kde $1 < a \le b < n$ . Vynásobením nerovnosti $a \le b$ číslem $a$ dostaneme $a^2 \le ab = n$ , odkud $a \le \sqrt{n}$ . Číslo $a>1$ má alespoň jednoho prvočíselného dělitele $p$ . Zřejmě $p \le a \le \sqrt{n}$ . Jelikož $p$ dělí $a$ a $a$ dělí $n$ , tak $p$ dělí $n$ , což jsme chtěli dokázat.

Úloha 2^*

Přirozené číslo $n$ má právě $k$ dělitelů. Dokažte, že součin dělitelů $n$ je roven $\sqrt{n^k}$ .

1Nápověda

Znovu použijte trik s párovým dělitelem.

2Nápověda

Rozlišete případy, kdy $n$ je a není čtverec.

✓Řešení

V řešení budeme uvažovat párování dělitelů: $d$ je dělitel $n$ právě tehdy když $n/d$ je dělitel $n$ . Součin takových dělitelů je $n$ .

Rozeberme dva případy:

Pokud $n$ není druhá mocnina, tak pro každý dělitel platí $d \neq n/d$ (jinak by $d^2=n$ ). Všech $k$ dělitelů tedy tvoří přesně $k/2$ takových párů. Celkový součin je $n^{k/2} = \sqrt{n^k}$ .
Pokud $n$ je druhá mocnina, tak $d=\sqrt{n}$ tvoří pár sám se sebou. Ostatních $k-1$ dělitelů tvoří $(k-1)/2$ párů se součinem $n$ . Celkový součin je proto $n^{\frac{k-1}2} \cdot \sqrt{n} = n^{\frac{k}2 - \frac12 + \frac12} = \sqrt{n^k}.$

Na závěr sekce si jedno upozornění. Při sepisování důkazů je často vidět nepřesnost typu vynechání předpokladů, například někdo může napsat $x^2=1$ , takže nutně $x=1$ . To může být správná část řešení, pokud v zadání máme, že $x$ je kladné. Pokud však tento předpoklad do řešení nenapíšeme, tak to zní podezřele, protože není jasné, zda si to řešitel uvědomil, a proto to může vést ke ztrátě bodů. Správně bychom psali něco jako $x^2=1$ a $x$ je kladné, takže nutně $x=1$ . Ukážeme si velmi běžnou situaci, kdy se toto stává:

Příklad 3

Kdy pro celá čísla $a,b$ platí, že $a \mid b$ a $b \mid a$ ?

✓Řešení

Intuitivní odpověď je, že nutně $a=b$ . V řešení občas opravdu vidět úvahu, že $a \mid b$ a $b \mid a$ , takže $a=b$ . To opravdu platí, pokud víme, že čísla $a,b$ jsou nezáporná. Situaci si zanalyzujeme podrobně:

Vztah $a \mid b$ dává, že existuje celé $u$ takové, že $b=au$ . Podobně $b \mid a$ znamená, že existuje celé $v$ takové, že $a=bv$ . Vynásobením těchto rovností máme $ab=abuv$ .

Pokud $ab=0$ , tedy pokud např. $a=0$ , tak vztah $b=au$ dává $b=0$ . Potom oba vztahy znamenají $0 \mid 0$ , což je v pořádku† a platí $a=b$ .

Pokud $ab\neq 0$ , tak $ab=abuv$ dává $1=uv$ . Číslo $1$ se dá zapsat jako součin celých čísel právě dvěma způsoby: $1 \cdot 1$ a $(-1) \cdot (-1)$ . To nám dává dvě řešení $(u,v)=(1,1)$ a $(u,v)=(-1,-1)$ , která zpětně znamenají $a=b$ a $a=-b$ . Pokud bychom však měli, že $a,b$ jsou nezáporná, tak buď je nějaké nulové, to bylo vyřešeno výše, nebo jsou obě kladná, což ale při $a=-b$ nenastane – tehdy bychom tedy opravdu měli, že nutně $a=b$ .

Závěr je, že $a \mid b$ a $b \mid a$ právě tehdy, když $a=b$ nebo $a=-b$ , přičemž pro nezáporná čísla dokonce rovnou $a=b$ .

2.2Důkaz sporem

Takovýto typ důkazu je obzvláště užitečný v případě, kdy je dokazované těžké uchopit a daleko jednodušší je něco říci o jeho negaci. Velmi běžný příklad, kde se to ilustruje:

Příklad 4

Dokažte, že číslo $\sqrt{2}$ je iracionální.

✓Řešení

Postupujeme sporem. Předpokládejme, že $\sqrt{2}$ je racionální číslo, tedy se dá zapsat jako zlomek $\frac pq$ v základním tvaru (čísla $p, q$ jsou nesoudělná). Po umocnění na druhou a vynásobení jmenovatelem dostaneme $p^2=2q^2$ .

Pravá strana je dělitelná dvěma, takže i $p^2$ a následně $p$ musí být sudé, tedy $p=2k$ . Dosazením máme $(2k)^2=2q^2$ , což se upraví na $2k^2=q^2$ . Nyní vidíme, že i $q$ musí být sudé. Čísla $p$ a $q$ jsou tedy obě dělitelná dvěma, což je spor s předpokladem, že jsou nesoudělná.

Cvičení 3

Tento důkaz by neprošel, pokud bychom měli $\sqrt{4}$ . Kde by selhal?

✓Řešení

Selhal by v kroku, kde se snažíme ukázat, že i $q$ je dělitelné. Měli bychom rovnici $p^2=4q^2$ , ze které vyplývá, že $p$ je sudé, tedy $p=2k$ . Dosazením však dostaneme $4k^2=4q^2$ , což se po krácení upraví na $k^2=q^2$ . Z této rovnosti už nevyplývá, že $q$ je sudé (ani dělitelné 4). Nedostaneme tak spor s nesoudělností $p, q$ .

Cvičení 4

Dokažte zobecnění tvrzení o iracionalitě $\sqrt{2}$ : Nechť $n$ je přirozené číslo. Číslo $\sqrt{n}$ je iracionální právě když existuje prvočíslo $p$ , které se v prvočíselném rozkladu $n$ nachází v liché mocnině.

✓Řešení

Postupujeme sporem. Nechť $\sqrt{n} = \frac ab$ pro nesoudělná $a, b$ . Rovnici upravíme na $nb^2 = a^2$ . V prvočíselném rozkladu čtverce ( $a^2$ i $b^2$ ) má každé prvočíslo sudý exponent. Na levé straně je exponent libovolného prvočísla součtem jeho exponentu v $n$ a v $b^2$ . Aby nastala rovnost, musí být tento součet sudý, což znamená, že exponent každého prvočísla v $n$ musí být sudý. Pokud tedy $n$ obsahuje prvočíslo v liché mocnině, dostáváme spor. Naopak, pokud jsou všechny exponenty sudé, $n$ je druhou mocninou a $\sqrt{n}$ je racionální číslo.

Úloha 3

Dokažte, že součet racionálního a iracionálního čísla je číslo iracionální.

1Nápověda

Postupujeme sporem. Co když pro racionální $r_1,r_2$ a iracionální $r'$ platí $r_1+r'=r_2$ ?

✓Řešení

Postupujeme sporem. Nechť $r_1$ je racionální a $r'$ iracionální číslo. Předpokládejme, že jejich součet $r_2 = r_1 + r'$ je racionální. Potom můžeme vyjádřit $r' = r_2 - r_1$ . Jelikož rozdíl dvou racionálních čísel je vždy racionální číslo, musí být i $r'$ racionální. To je však spor s předpokladem, že $r'$ je iracionální.

Úloha 4

Dokažte, že číslo $\sqrt{2}+\sqrt{3}$ je iracionální.

1Nápověda

Postupujeme sporem. Nechť platí $\sqrt{2}+\sqrt{3}=r$ . Potřebujeme se zbavit odmocnin.

2Nápověda

Klíčem k zbavení se odmocnin je umocnění. Umocněním rovnosti z předešlé nápovědy budeme mít místo dvou odmocnin jednu.

✓Řešení

Postupujeme sporem. Nechť $r = \sqrt{2}+\sqrt{3}$ je racionální číslo. Umocněním rovnosti dostaneme $r^2 = 5 + 2\sqrt{6}$ , z čehož vyjádříme $\sqrt{6} = \frac{r^2-5}{2}$ . Jelikož $r$ je racionální, je racionální i pravá strana. To by znamenalo, že $\sqrt{6}$ je racionální číslo, což je spor (důkaz je analogický jako pro $\sqrt{2}$ ).

Poznámka. Typicky chybný důkaz může spočívat v argumentu, že součet dvou iracionálních čísel je vždy iracionální. Přesvědčte se ale, že to není pravda.

Následující příklady ukazují, že důkaz sporem je technicky i tehdy, pokud dokazujeme, že něco neplatí.

Úloha 5

Dokažte, že součet tří druhých mocnin lichých celých čísel nikdy není druhou mocninou celého čísla.

1Nápověda

Klíčem je podívat se na dělitelnost osmi.

2Nápověda

Vzpomeňte si na tvrzení dokázané v sekci s přímým důkazem, že druhé mocniny lichých čísel dávají po dělení 8 zbytek 1.

✓Řešení

Podle předešlého dokázaného tvrzení dává druhá mocnina lichého čísla po dělení 8 zbytek 1. Součet tří takových čísel proto dává zbytek 3. Potom ale nemůže být čtvercem, jelikož to by musel být lichý a znovu podle našeho tvrzení dávat zbytek 1.

Úloha 6

73-CSMO-B-II-1

Patrik vybral dvě různá kladná celá čísla $a$ , $b$ , každé napsal na 10 karet a všech 20 karet rozmístil po obvodu kruhu. Všiml si, že každé číslo je nyní dělitelem součtu dvou čísel na sousedních kartách. Dokažte, že čísla na kartách se ob jedno střídají.

1Nápověda

Dokazujeme, že něco nejde – co by znamenalo, kdyby to potenciálně šlo, tedy kdyby se čísla nestřídala? Co je vlastně opak tohoto tvrzení?

2Nápověda

Kdyby se čísla nestřídala, tak nějaká dvě stejná jsou vedle sebe, např. $aa$ . Když se nyní procházíme po kružnici nějakým směrem, např. doprava, tak po čase musíme narazit na $b$ , takže máme $aab$ . Co z toho dostaneme?

3Nápověda

Trojice $aab$ nám dává $a \mid a+b$ , takže $a \mid b$ . Bylo by skvělé najít něco podobného ještě někde jinde.

4Nápověda

Abychom dostali $b \mid a$ , potřebujeme najít trojici $bba$ . Proč na kružnici musí existovat i $bb$ ? Zamysli se nad počtem střídavých skupin: pokud spojíš dvě $a$ do jedné skupiny, snížíš tím počet dostupných skupin pro $b$ . Kam se potom musí vejít všechna $b$ ?

5Nápověda

Pokud z trojice $aab$ zjistíme, že $a \mid b$ , a z trojice $bba$ zjistíme, že $b \mid a$ , jaký závěr z toho vyplývá pro dvě přirozená čísla $a, b$ ?

✓Řešení

Tvrzení úlohy dokážeme sporem. Připusťme tedy, že čísla $a$ , $b$ nejsou rozmístěna střídavě. To zřejmě znamená, že se v kruhu vedle sebe nacházejí někde dvě $a$ a současně někde dvě $b$ †. Vyberme dvě sousední $a$ . Pokud začneme od této dvojice $aa$ putovat po kruhu jedním směrem, narazíme na číslo $b$ (jinak by v kruhu byla samá $a$ ). Jakmile se to stane, budeme mít sousední trojici $aab$ . Podle zadání potom platí $a \mid a+b$ , odkud $a \mid b$ . Analogickou úvahou najdeme trojici $bba$ , ze které dostaneme $b \mid a$ . Pro přirozená čísla $a$ , $b$ tak platí $a \mid b$ i $b \mid a$ , a tedy $a = b$ , což je ve sporu s tím, že čísla $a$ , $b$ jsou různá. Tím je celé řešení úlohy hotové.

Poznámka 1. Bez újmy na obecnosti jsme od začátku důkazu sporem mohli předpokládat, že platí například $a < b$ . Potom bychom vystačili jen s úvahou o trojici $bba$ vedoucí ke spornému závěru $b \mid a$ .

Poznámka 2. Ukažme navíc, že pro čísla $a$ , $b$ splňující zadání úlohy musí platit buď $b = 2a$ , nebo $a = 2b$ . S ohledem na symetrii stačí v případě $a < b$ dokázat rovnost $b = 2a$ . Při střídavém rozmístění čísel z trojice $aba$ máme $b \mid 2a$ , takže $2a = kb$ pro vhodné přirozené číslo $k$ . Z předpokladu $a < b$ však vyplývá $kb = 2a < 2b$ , odkud $k < 2$ čili $k = 1$ , a proto $2a = kb = b$ , jak jsme chtěli dokázat.

Na závěr si ještě ukážeme snad nejznámější důkaz této všeobecně známé věci, kterou uměl dokázat už i Eukleides†.

Tvrzení 2

Dokažte, že prvočísel je nekonečně mnoho.

Důkaz

Postupujeme sporem. Předpokládejme, že existuje konečně mnoho prvočísel $p_1, p_2, \dots, p_n$ . Uvažujme číslo $N = p_1 \cdot p_2 \cdots p_n + 1$ . Toto číslo je větší než 1, proto musí mít alespoň jednoho prvočíselného dělitele $p$ . Tento dělitel $p$ musí být jedním z našich prvočísel $p_1, \dots, p_n$ . Zároveň však $N$ dává po dělení libovolným $p_i$ zbytek 1, tedy žádné $p_i$ ho nedělí. To je spor, prvočísel tedy musí být nekonečně mnoho.

Zkuste si podobným způsobem vyřešit další dvě úlohy:

Úloha 7^*

Dokažte, že existuje nekonečně mnoho prvočísel $p$ , která dělí $n^2+1$ pro vhodné přirozené $n$ .

1Nápověda

Jdeme sporem. Ať jich je konečně mnoho, označme je $p_1,p_2,\dots,p_k$ . Zkuste sestrojit vhodný výraz.

2Nápověda

Zamyslete se nad výrazem $(p_1\cdot p_2 \cdots p_k)^2+1$ .

✓Řešení

Předpokládejme, že takovýchto prvočísel je konečně mnoho, označme je $p_1, p_2, \dots, p_k$ . Uvažujme číslo

N = (p_1 \cdot p_2 \cdots p_k)^2 + 1.

Toto číslo je větší než 1, proto má nějakého prvočíselného dělitele $q$ . Jelikož $q$ dělí $N$ , dělí číslo tvaru $n^2+1$ , takže $q$ musí patřit do našeho seznamu $p_1, \dots, p_k$ . To ale znamená, že $q$ dělí součin $p_1 \cdots p_k$ , a tedy dělí i jeho druhou mocninu. Z toho vyplývá, že $q$ dělí rozdíl $N - (p_1 \cdots p_k)^2 = 1$ , což je spor.

Úloha 8^**

Dokažte, že existuje nekonečně mnoho prvočísel tvaru $3n+2$ , kde $n$ je přirozené číslo.

1Nápověda

Postupujeme jako v předešlých případech, označíme si prvočísla, sestrojujeme vhodný výraz. Je třeba si však dát pozor na speciální prvočíslo 2 (které je také našeho tvaru).

2Nápověda

Zamyslete se nad výrazem $3p_1\cdots p_k+2$ , kde $p_1,\dots,p_k$ jsou lichá prvočísla tvaru $3n+2$ .

3Nápověda

Klíčem je najít nějaké další prvočíslo tvaru $3n+2$ v prvočíselném rozkladu našeho výrazu. Mohlo by v tomto rozkladu nebýt žádné, co by to znamenalo?

✓Řešení

Předpokládejme, že existuje konečně mnoho prvočísel tvaru $3n+2$ . Označme $p_1, \dots, p_k$ všechna lichá prvočísla tohoto tvaru (číslo 2 vynecháváme). Uvažujme číslo

N = 3p_1 \cdots p_k + 2.

Jelikož $p_i$ jsou lichá, $N$ je součtem lichého čísla a čísla 2, takže $N$ je liché a není dělitelné 2. Zároveň $N$ dává po dělení třemi zbytek 2. Proto $N$ musí mít alespoň jednoho prvočíselného dělitele $q$ tvaru $3n+2$ (pokud by byli všichni dělitelé tvaru $3n+1$ , i $N$ by mělo tento tvar). Jelikož $N$ je liché, $q \neq 2$ . Zároveň $q$ nemůže být žádné z $p_i$ , protože jinak by dělilo $N$ i $3p_1 \cdots p_k$ , a tedy i jejich rozdíl 2. Našli jsme tedy nové prvočíslo $q$ tvaru $3n+2$ , což je spor.

Na závěr sekce se vraťme k slíbenému vysvětlení důkazu obměněné věty. V obecnosti jde o důkaz implikace $A \Rightarrow B$ , která je ekvivalentní implikaci $B' \Rightarrow A'$ , například implikace pokud $5$ nedělí $n$ , tak ani $25$ nedělí $n$ je ekvivalentní implikaci pokud $25$ dělí $n$ , tak $5$ dělí $n$ . My se tedy snažíme z negace tvrzení $B$ dokázat negaci předpokladu $A$ – technicky se tedy snažíme z předpokladu, že $B$ neplatí, přijít ke konkrétnímu sporu, a sice s předpokladem $A$ . Z toho je vidět, že takovýto důkaz je vlastně speciální případ důkazu sporem – při kterém nám jde o to přijít do sporu s jakýmkoli tvrzením, ne nutně předpokladem.

3Co jsme se naučili

Přímé dokazování používáme, když se snažíme z předpokladů odvodit co nejvíce věcí.
Důkaz sporem se hodí, když se z negace dokazovaného tvrzení dá něco odvodit, z negace už používáme přímé odvozování.
Důkaz obměněné věty je vlastně speciální případ důkazu sporem.

4Co dál

V dalších materiálech se budeme věnovat konkrétním důkazovým technikám, přičemž začneme matematickou indukcí, která je natolik důležitá, že si zaslouží samostatný materiál.

Komentáře

Základy důkazů

Autor

Patrik Bak

1Úvod

2Základní typy důkazů

V obecnosti rozlišujeme dva základní typy důkazů: přímý důkaz a důkaz sporem. V krátkosti:

Přímý důkaz: Z platných tvrzení odvodíme dokazované tvrzení.
Důkaz sporem: Předpokládáme, že dokazované tvrzení neplatí a snažíme se odvodit matematicky neplatné tvrzení, dojít ke sporu.

Přímý důkaz funguje tak, že do polévky postupně přidáváme nová a nová tvrzení, až tam přidáme to, které cílíme dokázat.
Na druhé straně, při důkazu sporem do polévky přidáme negaci dokazovaného tvrzení a pokračujeme, jako bychom dokazovali přímo. Nová tvrzení přidáváme, dokud se nám polévka nesrazí a nedostaneme nějaký nesmysl, jako např. $0=1$ , případně opak některého z předpokladů.

V následujících dvou sekcích si ukážeme konkrétní zajímavé příklady důkazů. Ještě předtím dvě poznámky:

Velmi důležitá technika je důkaz matematickou indukcí. Přísně vzato nejde o typ důkazu, jako spíše o recept na přidávání nových platných tvrzení do polévky.
Ve škole se zvyknou rozlišovat dva typy nepřímých důkazů: nepřímý důkaz sporem a důkaz obměněné implikace. Vysvětlíme, že druhý jmenovaný je vlastně speciálním případem důkazu sporem.

2.1Přímý důkaz

Příklad 1

Dokažte, že druhé mocniny lichých čísel dávají po dělení 8 zbytek 1.

✓Řešení

Nejprve si vezmeme tento ucelený zápis důkazu:

Než půjdeme dál, uvědomme si strukturu toho důkazu. Skládá se z těchto tvrzení:

$V_0$ : $m$ je liché celé číslo
$V_1$ : $m=2n+1$ pro nějaké celé $n$
$V_2$ : $n$ je celé, tedy $n$ je sudé nebo $n+1$ je sudé
$V_3$ : $n(n+1)$ je sudé
$V_4$ : $4n(n+1)$ je dělitelné 8
$V_5$ : $4n(n+1)+1$ dává po dělení 8 zbytek 1
$V_6$ : $(2n+1)^2$ dává po dělení 8 zbytek 1
$V_7$ : $m^2$ dává po dělení 8 zbytek 1

Důkaz spočívá v přechodech $V_0 \Rightarrow V_1$ a $V_2 \Rightarrow V_3 \Rightarrow V_4 \Rightarrow V_5 \Rightarrow V_6$ . Kombinací $V_1$ a $V_6$ dostáváme $V_7$ .

Cvičení 1

Dokažte, že pro prvočísla $p \ge 5$ platí, že $p^2-1$ je číslo dělitelné 24.

✓Řešení

p^2-1 = (3k \pm 1)^2 - 1 = 9k^2 \pm 6k = 3(3k^2 \pm 2k),

což je zřejmě dělitelné třemi.

V těžších úlohách nemusí být hned zřejmé, jak předpoklady ze zadání využít a je potřeba analyzovat situaci.

Příklad 2

Dokažte, že pokud je přirozené číslo $n$ druhou mocninou celého čísla, tak má lichý počet dělitelů.

✓Řešení

Předešlý příklad se dá vyřešit i pomocí obecně užitečného vzorce pro počet dělitelů:

Tvrzení 1

Nechť $n=p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$ , kde $p_1,p_2,\dots,p_k$ jsou navzájem různá prvočísla a $a_1,a_2,\dots,a_k$ jsou celá čísla. Potom má číslo $n$ právě

(a_1+1)(a_2+1)\cdots (a_k+1)

dělitelů.

Důkaz

(a_1+1)(a_2+1)\cdots (a_k+1).

Cvičení 2

Dokažte předešlý příklad, tedy větu o lichosti počtu dělitelů druhých mocnin, pomocí věty o počtu dělitelů. Dokažte také obrácenou implikaci této věty.

✓Řešení

Úloha 1

Je dáno složené číslo $n > 1$ . Dokažte, že je dělitelné prvočíslem nepřevyšujícím $\sqrt{n}$ .

1Nápověda

Číslo $n$ je složené, napišme si ho $ab$ , kde $1<a \leq b<n$ .

2Nápověda

✓Řešení

Úloha 2^*

Přirozené číslo $n$ má právě $k$ dělitelů. Dokažte, že součin dělitelů $n$ je roven $\sqrt{n^k}$ .

1Nápověda

Znovu použijte trik s párovým dělitelem.

2Nápověda

Rozlišete případy, kdy $n$ je a není čtverec.

✓Řešení

V řešení budeme uvažovat párování dělitelů: $d$ je dělitel $n$ právě tehdy když $n/d$ je dělitel $n$ . Součin takových dělitelů je $n$ .

Rozeberme dva případy:

Pokud $n$ není druhá mocnina, tak pro každý dělitel platí $d \neq n/d$ (jinak by $d^2=n$ ). Všech $k$ dělitelů tedy tvoří přesně $k/2$ takových párů. Celkový součin je $n^{k/2} = \sqrt{n^k}$ .
Pokud $n$ je druhá mocnina, tak $d=\sqrt{n}$ tvoří pár sám se sebou. Ostatních $k-1$ dělitelů tvoří $(k-1)/2$ párů se součinem $n$ . Celkový součin je proto $n^{\frac{k-1}2} \cdot \sqrt{n} = n^{\frac{k}2 - \frac12 + \frac12} = \sqrt{n^k}.$

Příklad 3

Kdy pro celá čísla $a,b$ platí, že $a \mid b$ a $b \mid a$ ?

✓Řešení

Vztah $a \mid b$ dává, že existuje celé $u$ takové, že $b=au$ . Podobně $b \mid a$ znamená, že existuje celé $v$ takové, že $a=bv$ . Vynásobením těchto rovností máme $ab=abuv$ .

Pokud $ab=0$ , tedy pokud např. $a=0$ , tak vztah $b=au$ dává $b=0$ . Potom oba vztahy znamenají $0 \mid 0$ , což je v pořádku† a platí $a=b$ .

Závěr je, že $a \mid b$ a $b \mid a$ právě tehdy, když $a=b$ nebo $a=-b$ , přičemž pro nezáporná čísla dokonce rovnou $a=b$ .

2.2Důkaz sporem

Příklad 4

Dokažte, že číslo $\sqrt{2}$ je iracionální.

✓Řešení

Cvičení 3

Tento důkaz by neprošel, pokud bychom měli $\sqrt{4}$ . Kde by selhal?

✓Řešení

Cvičení 4

✓Řešení

Úloha 3

Dokažte, že součet racionálního a iracionálního čísla je číslo iracionální.

1Nápověda

Postupujeme sporem. Co když pro racionální $r_1,r_2$ a iracionální $r'$ platí $r_1+r'=r_2$ ?

✓Řešení

Úloha 4

Dokažte, že číslo $\sqrt{2}+\sqrt{3}$ je iracionální.

1Nápověda

Postupujeme sporem. Nechť platí $\sqrt{2}+\sqrt{3}=r$ . Potřebujeme se zbavit odmocnin.

2Nápověda

Klíčem k zbavení se odmocnin je umocnění. Umocněním rovnosti z předešlé nápovědy budeme mít místo dvou odmocnin jednu.

✓Řešení

Poznámka. Typicky chybný důkaz může spočívat v argumentu, že součet dvou iracionálních čísel je vždy iracionální. Přesvědčte se ale, že to není pravda.

Následující příklady ukazují, že důkaz sporem je technicky i tehdy, pokud dokazujeme, že něco neplatí.

Úloha 5

Dokažte, že součet tří druhých mocnin lichých celých čísel nikdy není druhou mocninou celého čísla.

1Nápověda

Klíčem je podívat se na dělitelnost osmi.

2Nápověda

Vzpomeňte si na tvrzení dokázané v sekci s přímým důkazem, že druhé mocniny lichých čísel dávají po dělení 8 zbytek 1.

✓Řešení

Úloha 6

73-CSMO-B-II-1

1Nápověda

Dokazujeme, že něco nejde – co by znamenalo, kdyby to potenciálně šlo, tedy kdyby se čísla nestřídala? Co je vlastně opak tohoto tvrzení?

2Nápověda

3Nápověda

Trojice $aab$ nám dává $a \mid a+b$ , takže $a \mid b$ . Bylo by skvělé najít něco podobného ještě někde jinde.

4Nápověda

5Nápověda

Pokud z trojice $aab$ zjistíme, že $a \mid b$ , a z trojice $bba$ zjistíme, že $b \mid a$ , jaký závěr z toho vyplývá pro dvě přirozená čísla $a, b$ ?

✓Řešení

Na závěr si ještě ukážeme snad nejznámější důkaz této všeobecně známé věci, kterou uměl dokázat už i Eukleides†.

Tvrzení 2

Dokažte, že prvočísel je nekonečně mnoho.

Důkaz

Zkuste si podobným způsobem vyřešit další dvě úlohy:

Úloha 7^*

Dokažte, že existuje nekonečně mnoho prvočísel $p$ , která dělí $n^2+1$ pro vhodné přirozené $n$ .

1Nápověda

Jdeme sporem. Ať jich je konečně mnoho, označme je $p_1,p_2,\dots,p_k$ . Zkuste sestrojit vhodný výraz.

2Nápověda

Zamyslete se nad výrazem $(p_1\cdot p_2 \cdots p_k)^2+1$ .

✓Řešení

Předpokládejme, že takovýchto prvočísel je konečně mnoho, označme je $p_1, p_2, \dots, p_k$ . Uvažujme číslo

N = (p_1 \cdot p_2 \cdots p_k)^2 + 1.

Úloha 8^**

Dokažte, že existuje nekonečně mnoho prvočísel tvaru $3n+2$ , kde $n$ je přirozené číslo.

1Nápověda

Postupujeme jako v předešlých případech, označíme si prvočísla, sestrojujeme vhodný výraz. Je třeba si však dát pozor na speciální prvočíslo 2 (které je také našeho tvaru).

2Nápověda

Zamyslete se nad výrazem $3p_1\cdots p_k+2$ , kde $p_1,\dots,p_k$ jsou lichá prvočísla tvaru $3n+2$ .

3Nápověda

Klíčem je najít nějaké další prvočíslo tvaru $3n+2$ v prvočíselném rozkladu našeho výrazu. Mohlo by v tomto rozkladu nebýt žádné, co by to znamenalo?

✓Řešení

Předpokládejme, že existuje konečně mnoho prvočísel tvaru $3n+2$ . Označme $p_1, \dots, p_k$ všechna lichá prvočísla tohoto tvaru (číslo 2 vynecháváme). Uvažujme číslo

N = 3p_1 \cdots p_k + 2.

3Co jsme se naučili

Přímé dokazování používáme, když se snažíme z předpokladů odvodit co nejvíce věcí.
Důkaz sporem se hodí, když se z negace dokazovaného tvrzení dá něco odvodit, z negace už používáme přímé odvozování.
Důkaz obměněné věty je vlastně speciální případ důkazu sporem.

4Co dál

V dalších materiálech se budeme věnovat konkrétním důkazovým technikám, přičemž začneme matematickou indukcí, která je natolik důležitá, že si zaslouží samostatný materiál.