Základy dôkazov

Dôkazy

Autor

Patrik Bak

1Úvod

Bežná predstava o matematike je, že je o počítaní. V skutočnosti je však o porozumení všeobecne platných tvrdení. Aby sme mali istotu, že ide naozaj o platné tvrdenia, a nie nejakú chybu merania, tak tieto tvrdenia precízne zdôvodňujeme, resp. dokazujeme. Nemôže byť teda pre nás prekvapením, že dôkazy sú neoddeliteľnou súčasťou matematickej olympiády, ako aj vysokoškolských kurzov. V tomto materiáli si spravíme základný prehľad o tom, ako vyzerajú dôkazy v matematike. Ilustrujeme si ich na niekoľkých príkladoch. Ukážkové príklady budú hlavne o číslach, kde sa princípy najlepšie ilustrujú. Popísaná teória sa však samozrejme dá aplikovať aj v iných oblastiach – s dôkazmi sa stretneme vo všetkých materiáloch.

2Základné typy dôkazov

Vo všeobecnosti rozlišujeme dva základné typy dôkazov: priamy dôkaz a dôkaz sporom. V krátkosti:

Priamy dôkaz: Z platných tvrdení odvodíme dokazované tvrdenie.
Dôkaz sporom: Predpokladáme, že dokazované tvrdenie neplatí a snažíme sa odvodiť matematicky neplatné tvrdenie, dôjsť k sporu.

Toto si vieme predstaviť takto: Povedzme, že všetky tvrdenia, z ktorých vychádzame, sa nachádzajú vo veľkom hrnci s polievkou. Proces dokazovania spočíva v kombinovaní tvrdení z polievky a pridávaní nových z nich – ak napríklad máme v polievke $a^3=1$ , tak do polievky môžeme pridať $a=1$ , vďaka čomu môžeme do polievky pridať $a^4-2a+1=0$ , atď. Naše dva typy dôkazov potom vnímame nasledovne:

Priamy dôkaz funguje tak, že do polievky postupne pridávame nové a nové tvrdenia, až tam pridáme to, ktoré cielime dokázať.
Na druhej strane, pri dôkaze sporom do polievky pridáme negáciu dokazovaného tvrdenia a pokračujeme, akoby sme dokazovali priamo. Nové tvrdenia pridávame, až kým sa nám polievka nezrazí a nedostaneme nejaký nezmysel, ako napr. $0=1$ , prípadne opak nejakého z predpokladov.

V nasledujúcich dvoch sekciách si ukážeme konkrétne zaujímavé príklady dôkazov. Ešte predtým dve poznámky:

Veľmi dôležitá technika je dôkaz matematickou indukciou. Prísne vzaté nejde o typ dôkazu, ako skôr o recept na pridávanie nových platných tvrdení do polievky.
V škole sa zvyknú rozlišovať dva typy nepriamych dôkazov: nepriamy dôkaz sporom a dôkaz obmenenej implikácie. Vysvetlíme, že druhý menovaný je vlastne špeciálnym prípadom dôkazu sporom.

2.1Priamy dôkaz

Priame dôkazy sú vcelku prirodzené – kombinujeme predpoklady zo zadania s existujúcimi znalosťami, až kým nedôjdeme k dokazovanému tvrdeniu. Každý dôkaz sa teda dá zapísať ako séria reťazcov implikácií:

Príklad 1

Dokážte, že druhé mocniny nepárnych čísel dávajú po delení 8 zvyšok 1.

✓Riešenie

Najprv si vezmeme tento ucelený zápis dôkazu:

Nepárne čísla sa dajú napísať v tvare $m=2n+1$ pre celé $n$ . Dokazujeme, že $m^2=(2n+1)^2=4n(n+1)+1$ dáva po delení 8 zvyšok 1. Jedno z čísel $n$ , $n+1$ je párne, takže $n(n+1)$ je párne číslo, takže $4n(n+1)$ je deliteľné 8, takže $m^2=4n(n+1)+1$ dáva po delení 8 zvyšok 1, čo bolo treba dokázať.

Než pôjdeme ďalej, uvedomme si štruktúru toho dôkazu. Skladá sa z týchto tvrdení:

$V_0$ : $m$ je nepárne celé číslo
$V_1$ : $m=2n+1$ pre nejaké celé $n$
$V_2$ : $n$ je celé, teda $n$ je párne alebo $n+1$ je párne
$V_3$ : $n(n+1)$ je párne
$V_4$ : $4n(n+1)$ je deliteľné 8
$V_5$ : $4n(n+1)+1$ dáva po delení 8 zvyšok 1
$V_6$ : $(2n+1)^2$ dáva po delení 8 zvyšok 1
$V_7$ : $m^2$ dáva po delení 8 zvyšok 1

Dôkaz spočíva v prechodoch $V_0 \Rightarrow V_1$ a $V_2 \Rightarrow V_3 \Rightarrow V_4 \Rightarrow V_5 \Rightarrow V_6$ . Kombináciou $V_1$ a $V_6$ dostávame $V_7$ .

Slovný zápis je zjavne praktickejší ako odrážkový. Jeho problémom môže byť, že sa v ňom vedia stratiť komplikovanejšie úlohy: Zle spísané riešenia často pohoria na tom, že z textu nie sú jasné implikácie. Praktická rada: pri každom tvrdení si položiť otázku: je jasné, aké sú predpoklady a ako sa z nich niečo odvodilo? Pri takejto sebakontrole si človek neraz uvedomí, že jeho riešenie má chybu.

Cvičenie 1

Dokážte, že pre prvočísla $p \ge 5$ platí, že $p^2-1$ je číslo deliteľné 24.

✓Riešenie

Výraz rozložíme na súčin $(p-1)(p+1)$ . Keďže $p$ je prvočíslo väčšie ako 3, nie je deliteľné 3, teda dáva zvyšok 1 alebo 2. V prvom prípade delí 3 činiteľ $p-1$ , v druhom $p+1$ . Zároveň je $p$ nepárne, takže $p-1$ a $p+1$ sú dve po sebe idúce párne čísla. Jedno z nich je preto deliteľné 2 a druhé dokonca 4, ich súčin je teda deliteľný 8. Keďže je číslo $p^2-1$ deliteľné 3 aj 8, a tieto čísla sú nesúdeliteľné, je deliteľné aj 24.

Pre zaujímavosť uveďme ešte jedno riešenie, ktoré používa poznatok z predošlého príkladu: štvorce nepárnych čísel dávajú po delení 8 zvyšok 1: Vďaka tomu vlastne máme, že $p^2-1$ je deliteľné 8 – zostáva zdôvodniť, že $p^2-1$ je deliteľné 3. Keďže $p$ nie je 3, tak $p$ je v tvare buď $3k+1$ alebo $3k-1$ pre nejaké $k$ , v skratke $p=3k \pm 1$ . Potom

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

čo je zrejme deliteľné tromi.

V ťažších úlohách nemusí byť hneď zrejmé, ako predpoklady zo zadania využiť a je potrebné analyzovať situáciu.

Príklad 2

Dokážte, že ak je prirodzené číslo $n$ druhou mocninou celého čísla, tak má nepárny počet deliteľov.

✓Riešenie

Ako využiť, že $n$ je druhá mocnina celého čísla? Môžeme si zapísať $n=m^2$ , čo bol prvý krok v predošlom ukážkovom príklade – to nám ale dlho nepomôže. Kľúčom je zamyslieť sa nad deliteľmi, koniec koncov, o tých niečo dokazujeme. Základná myšlienka je:

Delitele prirodzeného čísla typicky chodia v pároch, $d$ je deliteľ $n$ práve vtedy, keď $n/d$ je deliteľ $n$ . Ak by sa nikdy nestalo, že ide o rovnaké delitele, tak počet deliteľov čísla $n$ je teda párny.

Kedy sa ale stane, že toto párovanie páruje deliteľ so sebou samým? Práve keď $d=n/d$ , teda keď $d^2=n$ . A to je presne náš predpoklad! Tým pádom sa všetky delitele až na deliteľa $\sqrt{n}$ s nejakým spárujú, dokopy teda budeme mať nepárny počet deliteľov, čo bolo treba dokázať.

Poznámka. Tento príklad v skutočnosti platí ako ekvivalencia. V skutočnosti by bol ľahší, ak by bola zadaná obrátená implikácia, lebo fakt, že je štvorec, sa v úvahovom reťazci používa až na konci. V súťažných úlohách je ale bežné, že autori sa snažia tieto kľúčové kroky zamaskovať.

Predošlý príklad sa dá vyriešiť aj pomocou všeobecne užitočného vzorca pre počet deliteľov:

Tvrdenie 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$ sú navzájom rôzne prvočísla a $a_1,a_2,\dots,a_k$ sú celé čísla. Potom má číslo $n$ práve

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

deliteľov.

Dôkaz

Uvažujme ľubovoľného deliteľa $d$ čísla $n$ . Keďže $d$ delí $n$ a prvočíselný rozklad $n$ obsahuje iba prvočísla $p_1,\dots,p_k$ , aj rozklad čísla $d$ musí obsahovať iba tieto prvočísla. Zapíšme teda $d = p_1^{b_1} \cdot p_2^{b_2} \cdots p_k^{b_k}$ . Pritom pre každé $i$ musí platiť $0 \leq b_i \leq a_i$ (horná hranica plynie z toho, že $d$ ako deliteľ $n$ by nemohol obsahovať vyššiu mocninu $p_i$ než $n$ ). Každý deliteľ teda vieme jednoznačne reprezentovať ako $k$ -ticu $(b_1,\dots,b_k)$ s vlastnosťou $0 \leq b_i \leq a_i$ . Počet deliteľov je preto rovný počtu takýchto $k$ -tíc.

Na určenie počtu $k$ -tíc použijeme kombinatorické pravidlo súčinu. Voľby jednotlivých exponentov $b_1,\dots,b_k$ sú na sebe nezávislé – hodnota $b_i$ nijako neobmedzuje hodnoty ostatných exponentov. Pre exponent $b_i$ máme $a_i+1$ možností, konkrétne všetky čísla od $0$ do $a_i$ . Podľa pravidla súčinu je celkový počet $k$ -tíc rovný

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

Cvičenie 2

Dokážte predošlý príklad, teda vetu o nepárnosti počtu deliteľov druhých mocnín, pomocou vety o počte deliteľov. Dokážte tiež obrátenú implikáciu tejto vety.

✓Riešenie

Nech $n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$ . Keďže $n$ je druhá mocnina celého čísla, všetky exponenty $a_1, \dots, a_k$ musia byť párne. Podľa vety je počet deliteľov rovný súčinu $(a_1+1)(a_2+1)\cdots(a_k+1)$ . Keďže každé $a_i$ je párne, každá zátvorka predstavuje nepárne číslo. Súčin nepárnych čísel je vždy nepárny, teda počet deliteľov je nepárny.

Úloha 1

Je dané zložené číslo $n > 1$ . Dokážte, že je deliteľné prvočíslom neprevyšujúcim $\sqrt{n}$ .

1Nápoveda

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

2Nápoveda

Idea je povedať, že menšie z čísel $a,b$ , teda $a$ , je deliteľné dosť malým prvočíslom. Na to stačí povedať, že samo osebe je dosť malé (v najtesnejšom prípade je samo prvočíslom).

✓Riešenie

Keďže $n$ je zložené, môžeme ho napísať ako $n=ab$ , kde $1 < a \le b < n$ . Vynásobením nerovnosti $a \le b$ číslom $a$ dostaneme $a^2 \le ab = n$ , odkiaľ $a \le \sqrt{n}$ . Číslo $a>1$ má aspoň jedného prvočíselného deliteľa $p$ . Zrejme $p \le a \le \sqrt{n}$ . Keďže $p$ delí $a$ a $a$ delí $n$ , tak $p$ delí $n$ , čo sme chceli dokázať.

Úloha 2^*

Prirodzené číslo $n$ má práve $k$ deliteľov. Dokážte, že súčin deliteľov $n$ je rovný $\sqrt{n^k}$ .

1Nápoveda

Znova použite trik s párovým deliteľom.

2Nápoveda

Rozlíšte prípady, kedy $n$ je a nie je štvorec.

✓Riešenie

V riešení budeme uvažovať párovanie deliteľov: $d$ je deliteľ $n$ práve vtedy keď $n/d$ je deliteľ $n$ . Súčin takýchto deliteľov je $n$ .

Rozoberme dva prípady:

Ak $n$ nie je druhá mocnina, tak pre každý deliteľ platí $d \neq n/d$ (inak by $d^2=n$ ). Všetkých $k$ deliteľov teda tvorí presne $k/2$ takýchto párov. Celkový súčin je $n^{k/2} = \sqrt{n^k}$ .
Ak $n$ je druhá mocnina, tak $d=\sqrt{n}$ tvorí pár sám so sebou. Ostatných $k-1$ deliteľov tvorí $(k-1)/2$ párov so súčinom $n$ . Celkový súčin je preto $n^{\frac{k-1}2} \cdot \sqrt{n} = n^{\frac{k}2 - \frac12 + \frac12} = \sqrt{n^k}.$

Na záver sekcie si jedno upozornenie. Pri spisovaní dôkazov je často vidieť nepresnosť typu vynechanie predpokladov, napríklad niekto môže napísať $x^2=1$ , takže nutne $x=1$ . To môže byť správna časť riešenia, ak v zadaní máme, že $x$ je kladné. Ak však tento predpoklad do riešenia nenapíšeme, tak to znie podozrivo, lebo nie je jasné, či si to riešiteľ uvedomil, a preto to môže viesť k strate bodov. Správne by sme písali niečo ako $x^2=1$ a $x$ je kladné, takže nutne $x=1$ . Ukážeme si veľmi bežnú situáciu, kedy sa toto stáva:

Príklad 3

Kedy pre celé čísla $a,b$ platí, že $a \mid b$ a $b \mid a$ ?

✓Riešenie

Intuitívna odpoveď je, že nutne $a=b$ . V riešenie občas naozaj vidieť úvahu, že $a \mid b$ a $b \mid a$ , takže $a=b$ . To naozaj platí, ak vieme, že čísla $a,b$ sú nezáporné. Situáciu si zanalyzujeme podrobne:

Vzťah $a \mid b$ dáva, že existuje celé $u$ také, že $b=au$ . Podobne $b \mid a$ znamená, že existuje celé $v$ také, že $a=bv$ . Vynásobením týchto rovností máme $ab=abuv$ .

Ak $ab=0$ , teda ak napr. $a=0$ , tak vzťah $b=au$ dáva $b=0$ . Potom oba vzťahy znamenajú $0 \mid 0$ , čo je v pohode† a platí $a=b$ .

Ak $ab\neq 0$ , tak $ab=abuv$ dáva $1=uv$ . Číslo $1$ sa dá zapísať ako súčin celých čísel práve dvoma spôsobmi: $1 \cdot 1$ a $(-1) \cdot (-1)$ . To nám dáva dve riešenia $(u,v)=(1,1)$ a $(u,v)=(-1,-1)$ , ktoré spätne znamenajú $a=b$ a $a=-b$ . Ak by sme však mali, že $a,b$ sú nezáporné, tak buď je nejaké nulové, to bolo vyriešené hore, alebo sú oba kladné, čo ale pri $a=-b$ nenastane – vtedy by sme teda naozaj mali, že nutne $a=b$ .

Záver je, že $a \mid b$ a $b \mid a$ práve vtedy, keď $a=b$ alebo $a=-b$ , pričom pre nezáporné čísla dokonca rovno $a=b$ .

2.2Dôkaz sporom

Takýto typ dôkazu je obzvlášť užitočný v prípade, kedy je dokazované ťažké uchopiť a ďaleko jednoduchšie je niečo povedať o jeho negácii. Veľmi bežný príklad, kde sa to ilustruje:

Príklad 4

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

✓Riešenie

Postupujeme sporom. Predpokladajme, že $\sqrt{2}$ je racionálne číslo, teda sa dá zapísať ako zlomok $\frac pq$ v základnom tvare (čísla $p, q$ sú nesúdeliteľné). Po umocnení na druhú a vynásobení menovateľom dostaneme $p^2=2q^2$ .

Pravá strana je deliteľná dvomi, takže aj $p^2$ a následne $p$ musí byť párne, teda $p=2k$ . Dosadením máme $(2k)^2=2q^2$ , čo sa upraví na $2k^2=q^2$ . Teraz vidíme, že aj $q$ musí byť párne. Čísla $p$ a $q$ sú teda obe deliteľné dvomi, čo je spor s predpokladom, že sú nesúdeliteľné.

Cvičenie 3

Tento dôkaz by neprešiel, ak by sme mali $\sqrt{4}$ . Kde by zlyhal?

✓Riešenie

Zlyhal by v kroku, kde sa snažíme ukázať, že aj $q$ je deliteľné. Mali by sme rovnicu $p^2=4q^2$ , z ktorej vyplýva, že $p$ je párne, teda $p=2k$ . Dosadením však dostaneme $4k^2=4q^2$ , čo sa po krátení upraví na $k^2=q^2$ . Z tejto rovnosti už nevyplýva, že $q$ je párne (ani deliteľné 4). Nedostaneme tak spor s nesúdeliteľnosťou $p, q$ .

Cvičenie 4

Dokážte zovšeobecnenie tvrdenia o iracionalite $\sqrt{2}$ : Nech $n$ je prirodzené číslo. Číslo $\sqrt{n}$ je iracionálne práve keď existuje prvočíslo $p$ , ktoré sa v prvočíselnom rozklade $n$ nachádza v nepárnej mocnine.

✓Riešenie

Postupujeme sporom. Nech $\sqrt{n} = \frac ab$ pre nesúdeliteľné $a, b$ . Rovnicu upravíme na $nb^2 = a^2$ . V prvočíselnom rozklade štvorca ( $a^2$ aj $b^2$ ) má každé prvočíslo párny exponent. Na ľavej strane je exponent ľubovoľného prvočísla súčtom jeho exponentu v $n$ a v $b^2$ . Aby nastala rovnosť, musí byť tento súčet párny, čo znamená, že exponent každého prvočísla v $n$ musí byť párny. Ak teda $n$ obsahuje prvočíslo v nepárnej mocnine, dostávame spor. Naopak, ak sú všetky exponenty párne, $n$ je druhou mocninou a $\sqrt{n}$ je racionálne číslo.

Úloha 3

Dokážte, že súčet racionálneho a iracionálneho čísla je číslo iracionálne.

1Nápoveda

Postupujeme sporom. Čo ak pre racionálne $r_1,r_2$ a iracionálne $r'$ platí $r_1+r'=r_2$ ?

✓Riešenie

Postupujeme sporom. Nech $r_1$ je racionálne a $r'$ iracionálne číslo. Predpokladajme, že ich súčet $r_2 = r_1 + r'$ je racionálny. Potom môžeme vyjadriť $r' = r_2 - r_1$ . Keďže rozdiel dvoch racionálnych čísel je vždy racionálne číslo, musí byť aj $r'$ racionálne. To je však spor s predpokladom, že $r'$ je iracionálne.

Úloha 4

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

1Nápoveda

Postupujeme sporom. Nech platí $\sqrt{2}+\sqrt{3}=r$ . Potrebujeme sa zbaviť odmocnín.

2Nápoveda

Kľúčom k zbaveniu sa odmocnín je umocnenie. Umocnením rovnosti z predošlej nápovedy budeme mať namiesto dvoch odmocnín jednu.

✓Riešenie

Postupujeme sporom. Nech $r = \sqrt{2}+\sqrt{3}$ je racionálne číslo. Umocnením rovnosti dostaneme $r^2 = 5 + 2\sqrt{6}$ , z čoho vyjadríme $\sqrt{6} = \frac{r^2-5}{2}$ . Keďže $r$ je racionálne, je racionálna aj pravá strana. To by znamenalo, že $\sqrt{6}$ je racionálne číslo, čo je spor (dôkaz je analogický ako pre $\sqrt{2}$ ).

Poznámka. Typicky chybný dôkaz môže spočívať v argumente, že súčet dvoch iracionálnych čísel je vždy iracionálny. Presvedčte sa ale, že to nie je pravda.

Nasledovné príklady ukazujú, že dôkaz sporom je technicky aj vtedy, ak dokazujeme, že niečo neplatí.

Úloha 5

Dokážte, že súčet troch druhých mocnín nepárnych celých čísel nikdy nie je druhou mocninou celého čísla.

1Nápoveda

Kľúčom je pozrieť sa na deliteľnosť ôsmimi.

2Nápoveda

Spomeňte si na tvrdenie dokázané v sekcii s priamym dôkazom, že druhé mocniny nepárnych čísel dávajú po delení 8 zvyšok 1.

✓Riešenie

Podľa predošlého dokázaného tvrdenia dáva druhá mocnina nepárneho čísla po delení 8 zvyšok 1. Súčet troch takýchto čísel preto dáva zvyšok 3. Potom ale nemôže byť štvorec, keďže to by musel byť nepárny a znova podľa nášho tvrdenia dávať zvyšok 1.

Úloha 6

73-CSMO-B-II-1

Patrik vybral dve rôzne kladné celé čísla $a$ , $b$ , každé napísal na 10 kariet a všetkých 20 kariet rozmiestnil po obvode kruhu. Všimol si, že každé číslo je teraz deliteľom súčtu dvoch čísel na susedných kartách. Dokážte, že čísla na kartách sa ob jedno striedajú.

1Nápoveda

Dokazujeme, že niečo nejde – čo by znamenalo, ak by to potenciálne išlo, teda ak by sa čísla nestriedali? Čo je vlastne opak tohto tvrdenia?

2Nápoveda

Ak by sa čísla nestriedali, tak nejaké dve rovnaké sú vedľa seba, napr. $aa$ . Keď sa teraz prechádzame po kružnici nejakým smerom, napr. doprava, tak po čase musíme naraziť na $b$ , takže máme $aab$ . Čo z toho dostaneme?

3Nápoveda

Trojica $aab$ nám dáva $a \mid a+b$ , takže $a \mid b$ . Bolo by skvelé nájsť niečo podobné ešte niekde inde.

4Nápoveda

Aby sme dostali $b \mid a$ , potrebujeme nájsť trojicu $bba$ . Prečo na kružnici musí existovať aj $bb$ ? Zamysli sa nad počtom striedavých skupín: ak spojíš dve $a$ do jednej skupiny, znížiš tým počet dostupných skupín pre $b$ . Kam sa potom musia zmestiť všetky $b$ ?

5Nápoveda

Ak z trojice $aab$ zistíme, že $a \mid b$ , a z trojice $bba$ zistíme, že $b \mid a$ , aký záver z toho vyplýva pre dve prirodzené čísla $a, b$ ?

✓Riešenie

Tvrdenie úlohy dokážeme sporom. Pripusťme teda, že čísla $a$ , $b$ nie sú rozmiestnené striedavo. To zrejme znamená, že sa v kruhu vedľa seba nachádzajú niekde dve $a$ a súčasne niekde dve $b$ †. Vyberme dve susedné $a$ . Ak začneme od tejto dvojice $aa$ putovať po kruhu jedným smerom, narazíme na číslo $b$ (inak by v kruhu boli samé $a$ ). Akonáhle sa to stane, budeme mať susednú trojicu $aab$ . Podľa zadania potom platí $a \mid a+b$ , odkiaľ $a \mid b$ . Analogickou úvahou nájdeme trojicu $bba$ , z ktorej dostaneme $b \mid a$ . Pre prirodzené čísla $a$ , $b$ tak platí $a \mid b$ aj $b \mid a$ , a teda $a = b$ , čo je v spore s tým, že čísla $a$ , $b$ sú rôzne. Tým je celé riešenie úlohy hotové.

Poznámka 1. Bez ujmy na všeobecnosti sme od začiatku dôkazu sporom mohli predpokladať, že platí napríklad $a < b$ . Potom by sme vystačili len s úvahou o trojici $bba$ vedúcej k spornému záveru $b \mid a$ .

Poznámka 2. Ukážme navyše, že pre čísla $a$ , $b$ spĺňajúce zadanie úlohy musí platiť buď $b = 2a$ , alebo $a = 2b$ . S ohľadom na symetriu stačí v prípade $a < b$ dokázať rovnosť $b = 2a$ . Pri striedavom rozmiestnení čísel z trojice $aba$ máme $b \mid 2a$ , takže $2a = kb$ pre vhodné prirodzené číslo $k$ . Z predpokladu $a < b$ však vyplýva $kb = 2a < 2b$ , odkiaľ $k < 2$ čiže $k = 1$ , a preto $2a = kb = b$ , ako sme chceli dokázať.

Na záver si ešte ukážeme azda najznámejší dôkaz tejto všeobecne známej veci, ktorú vedel dokázať už aj Euklides†.

Tvrdenie 2

Dokážte, že prvočísel je nekonečne veľa.

Dôkaz

Postupujeme sporom. Predpokladajme, že existuje konečne veľa 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äčšie ako 1, preto musí mať aspoň jedného prvočíselného deliteľa $p$ . Tento deliteľ $p$ musí byť jedným z našich prvočísel $p_1, \dots, p_n$ . Zároveň však $N$ dáva po delení ľubovoľným $p_i$ zvyšok 1, teda žiadne $p_i$ ho nedelí. To je spor, prvočísel teda musí byť nekonečne veľa.

Skúste si podobným spôsobom vyriešiť ďalšie dve úlohy:

Úloha 7^*

Dokážte, že existuje nekonečne veľa prvočísel $p$ , ktoré delia $n^2+1$ pre vhodné prirodzené $n$ .

1Nápoveda

Ideme sporom. Ak by ich bolo konečne veľa, označme ich $p_1,p_2,\dots,p_k$ . Skúste zostrojiť vhodný výraz.

2Nápoveda

Zamyslite sa nad výrazom $(p_1\cdot p_2 \cdots p_k)^2+1$ .

✓Riešenie

Predpokladajme, že takýchto prvočísel je konečne veľa, označme ich $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äčšie ako 1, preto má nejakého prvočíselného deliteľa $q$ . Keďže $q$ delí $N$ , delí číslo tvaru $n^2+1$ , takže $q$ musí patriť do nášho zoznamu $p_1, \dots, p_k$ . To ale znamená, že $q$ delí súčin $p_1 \cdots p_k$ , a teda delí aj jeho druhú mocninu. Z toho vyplýva, že $q$ delí rozdiel $N - (p_1 \cdots p_k)^2 = 1$ , čo je spor.

Úloha 8^**

Dokážte, že existuje nekonečne veľa prvočísel tvaru $3n+2$ , kde $n$ je prirodzené číslo.

1Nápoveda

Postupujeme ako v predošlých prípadoch, označíme si prvočísla, zostrojujeme vhodný výraz. Je treba si však dať pozor na špeciálne prvočíslo 2 (ktoré je tiež nášho tvaru).

2Nápoveda

Zamyslite sa nad výrazom $3p_1\cdots p_k+2$ , kde $p_1,\dots,p_k$ sú nepárne prvočísla tvaru $3n+2$ .

3Nápoveda

Kľúčom je nájsť nejaké ďalšie prvočíslo tvaru $3n+2$ v prvočíselnom rozklade nášho výrazu. Mohlo by v tomto rozklade nebyť žiadne, čo by to znamenalo?

✓Riešenie

Predpokladajme, že existuje konečne veľa prvočísel tvaru $3n+2$ . Označme $p_1, \dots, p_k$ všetky nepárne prvočísla tohto tvaru (číslo 2 vynechávame). Uvažujme číslo

N = 3p_1 \cdots p_k + 2.

Keďže $p_i$ sú nepárne, $N$ je súčtom nepárneho čísla a čísla 2, takže $N$ je nepárne a nie je deliteľné 2. Zároveň $N$ dáva po delení tromi zvyšok 2. Preto $N$ musí mať aspoň jedného prvočíselného deliteľa $q$ tvaru $3n+2$ (ak by boli všetky delitele tvaru $3n+1$ , aj $N$ by malo tento tvar). Keďže $N$ je nepárne, $q \neq 2$ . Zároveň $q$ nemôže byť žiadne z $p_i$ , pretože inak by delilo $N$ aj $3p_1 \cdots p_k$ , a teda aj ich rozdiel 2. Našli sme teda nové prvočíslo $q$ tvaru $3n+2$ , čo je spor.

Na záver sekcie sa vráťme k sľúbenému vysvetleniu dôkazu obmenenej vety. Vo všeobecnosti ide o dôkaz implikácie $A \Rightarrow B$ , ktorá je ekvivalentná implikácii $B' \Rightarrow A'$ , napríklad implikácia ak $5$ nedelí $n$ , tak ani $25$ nedelí $n$ je ekvivalentná implikácii ak $25$ delí $n$ , tak $5$ delí $n$ . My sa teda snažíme z negácie tvrdenia $B$ dokázať negáciu predpokladu $A$ – technicky sa teda snažíme z predpokladu, že $B$ neplatí, prísť ku konkrétnemu sporu, a síce s predpokladom $A$ . Z toho vidieť, že takýto dôkaz je vlastne špeciálny prípad dôkazu sporom – pri ktorom nám ide o to prísť do sporu s akýmkoľvek tvrdením, nie nutne predpokladom.

3Čo sme sa naučili

Priame dokazovanie používame, keď sa snažíme z predpokladov odvodiť čo najviac vecí.
Dôkaz sporom sa hodí, keď sa z negácie dokazovaného tvrdenia dá niečo odvodiť, z negácie už používame priame odvodzovanie.
Dôkaz obmenenej vety je vlastne špeciálny prípad dôkazu sporom.

4Čo ďalej

V ďalších materiáloch sa budeme venovať konkrétnym dôkazovým technikám, pričom začneme matematickou indukciou, ktorá je natoľko dôležitá, že si zaslúži samostatný materiál.

Komentáre

Základy dôkazov

Dôkazy

Autor

Patrik Bak

1Úvod

2Základné typy dôkazov

Vo všeobecnosti rozlišujeme dva základné typy dôkazov: priamy dôkaz a dôkaz sporom. V krátkosti:

Priamy dôkaz: Z platných tvrdení odvodíme dokazované tvrdenie.
Dôkaz sporom: Predpokladáme, že dokazované tvrdenie neplatí a snažíme sa odvodiť matematicky neplatné tvrdenie, dôjsť k sporu.

Priamy dôkaz funguje tak, že do polievky postupne pridávame nové a nové tvrdenia, až tam pridáme to, ktoré cielime dokázať.
Na druhej strane, pri dôkaze sporom do polievky pridáme negáciu dokazovaného tvrdenia a pokračujeme, akoby sme dokazovali priamo. Nové tvrdenia pridávame, až kým sa nám polievka nezrazí a nedostaneme nejaký nezmysel, ako napr. $0=1$ , prípadne opak nejakého z predpokladov.

V nasledujúcich dvoch sekciách si ukážeme konkrétne zaujímavé príklady dôkazov. Ešte predtým dve poznámky:

Veľmi dôležitá technika je dôkaz matematickou indukciou. Prísne vzaté nejde o typ dôkazu, ako skôr o recept na pridávanie nových platných tvrdení do polievky.
V škole sa zvyknú rozlišovať dva typy nepriamych dôkazov: nepriamy dôkaz sporom a dôkaz obmenenej implikácie. Vysvetlíme, že druhý menovaný je vlastne špeciálnym prípadom dôkazu sporom.

2.1Priamy dôkaz

Príklad 1

Dokážte, že druhé mocniny nepárnych čísel dávajú po delení 8 zvyšok 1.

✓Riešenie

Najprv si vezmeme tento ucelený zápis dôkazu:

Než pôjdeme ďalej, uvedomme si štruktúru toho dôkazu. Skladá sa z týchto tvrdení:

$V_0$ : $m$ je nepárne celé číslo
$V_1$ : $m=2n+1$ pre nejaké celé $n$
$V_2$ : $n$ je celé, teda $n$ je párne alebo $n+1$ je párne
$V_3$ : $n(n+1)$ je párne
$V_4$ : $4n(n+1)$ je deliteľné 8
$V_5$ : $4n(n+1)+1$ dáva po delení 8 zvyšok 1
$V_6$ : $(2n+1)^2$ dáva po delení 8 zvyšok 1
$V_7$ : $m^2$ dáva po delení 8 zvyšok 1

Dôkaz spočíva v prechodoch $V_0 \Rightarrow V_1$ a $V_2 \Rightarrow V_3 \Rightarrow V_4 \Rightarrow V_5 \Rightarrow V_6$ . Kombináciou $V_1$ a $V_6$ dostávame $V_7$ .

Cvičenie 1

Dokážte, že pre prvočísla $p \ge 5$ platí, že $p^2-1$ je číslo deliteľné 24.

✓Riešenie

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

čo je zrejme deliteľné tromi.

V ťažších úlohách nemusí byť hneď zrejmé, ako predpoklady zo zadania využiť a je potrebné analyzovať situáciu.

Príklad 2

Dokážte, že ak je prirodzené číslo $n$ druhou mocninou celého čísla, tak má nepárny počet deliteľov.

✓Riešenie

Predošlý príklad sa dá vyriešiť aj pomocou všeobecne užitočného vzorca pre počet deliteľov:

Tvrdenie 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$ sú navzájom rôzne prvočísla a $a_1,a_2,\dots,a_k$ sú celé čísla. Potom má číslo $n$ práve

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

deliteľov.

Dôkaz

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

Cvičenie 2

Dokážte predošlý príklad, teda vetu o nepárnosti počtu deliteľov druhých mocnín, pomocou vety o počte deliteľov. Dokážte tiež obrátenú implikáciu tejto vety.

✓Riešenie

Úloha 1

Je dané zložené číslo $n > 1$ . Dokážte, že je deliteľné prvočíslom neprevyšujúcim $\sqrt{n}$ .

1Nápoveda

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

2Nápoveda

✓Riešenie

Úloha 2^*

Prirodzené číslo $n$ má práve $k$ deliteľov. Dokážte, že súčin deliteľov $n$ je rovný $\sqrt{n^k}$ .

1Nápoveda

Znova použite trik s párovým deliteľom.

2Nápoveda

Rozlíšte prípady, kedy $n$ je a nie je štvorec.

✓Riešenie

V riešení budeme uvažovať párovanie deliteľov: $d$ je deliteľ $n$ práve vtedy keď $n/d$ je deliteľ $n$ . Súčin takýchto deliteľov je $n$ .

Rozoberme dva prípady:

Ak $n$ nie je druhá mocnina, tak pre každý deliteľ platí $d \neq n/d$ (inak by $d^2=n$ ). Všetkých $k$ deliteľov teda tvorí presne $k/2$ takýchto párov. Celkový súčin je $n^{k/2} = \sqrt{n^k}$ .
Ak $n$ je druhá mocnina, tak $d=\sqrt{n}$ tvorí pár sám so sebou. Ostatných $k-1$ deliteľov tvorí $(k-1)/2$ párov so súčinom $n$ . Celkový súčin je preto $n^{\frac{k-1}2} \cdot \sqrt{n} = n^{\frac{k}2 - \frac12 + \frac12} = \sqrt{n^k}.$

Príklad 3

Kedy pre celé čísla $a,b$ platí, že $a \mid b$ a $b \mid a$ ?

✓Riešenie

Vzťah $a \mid b$ dáva, že existuje celé $u$ také, že $b=au$ . Podobne $b \mid a$ znamená, že existuje celé $v$ také, že $a=bv$ . Vynásobením týchto rovností máme $ab=abuv$ .

Ak $ab=0$ , teda ak napr. $a=0$ , tak vzťah $b=au$ dáva $b=0$ . Potom oba vzťahy znamenajú $0 \mid 0$ , čo je v pohode† a platí $a=b$ .

Záver je, že $a \mid b$ a $b \mid a$ práve vtedy, keď $a=b$ alebo $a=-b$ , pričom pre nezáporné čísla dokonca rovno $a=b$ .

2.2Dôkaz sporom

Príklad 4

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

✓Riešenie

Cvičenie 3

Tento dôkaz by neprešiel, ak by sme mali $\sqrt{4}$ . Kde by zlyhal?

✓Riešenie

Cvičenie 4

✓Riešenie

Úloha 3

Dokážte, že súčet racionálneho a iracionálneho čísla je číslo iracionálne.

1Nápoveda

Postupujeme sporom. Čo ak pre racionálne $r_1,r_2$ a iracionálne $r'$ platí $r_1+r'=r_2$ ?

✓Riešenie

Úloha 4

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

1Nápoveda

Postupujeme sporom. Nech platí $\sqrt{2}+\sqrt{3}=r$ . Potrebujeme sa zbaviť odmocnín.

2Nápoveda

Kľúčom k zbaveniu sa odmocnín je umocnenie. Umocnením rovnosti z predošlej nápovedy budeme mať namiesto dvoch odmocnín jednu.

✓Riešenie

Poznámka. Typicky chybný dôkaz môže spočívať v argumente, že súčet dvoch iracionálnych čísel je vždy iracionálny. Presvedčte sa ale, že to nie je pravda.

Nasledovné príklady ukazujú, že dôkaz sporom je technicky aj vtedy, ak dokazujeme, že niečo neplatí.

Úloha 5

Dokážte, že súčet troch druhých mocnín nepárnych celých čísel nikdy nie je druhou mocninou celého čísla.

1Nápoveda

Kľúčom je pozrieť sa na deliteľnosť ôsmimi.

2Nápoveda

Spomeňte si na tvrdenie dokázané v sekcii s priamym dôkazom, že druhé mocniny nepárnych čísel dávajú po delení 8 zvyšok 1.

✓Riešenie

Úloha 6

73-CSMO-B-II-1

1Nápoveda

Dokazujeme, že niečo nejde – čo by znamenalo, ak by to potenciálne išlo, teda ak by sa čísla nestriedali? Čo je vlastne opak tohto tvrdenia?

2Nápoveda

3Nápoveda

Trojica $aab$ nám dáva $a \mid a+b$ , takže $a \mid b$ . Bolo by skvelé nájsť niečo podobné ešte niekde inde.

4Nápoveda

5Nápoveda

Ak z trojice $aab$ zistíme, že $a \mid b$ , a z trojice $bba$ zistíme, že $b \mid a$ , aký záver z toho vyplýva pre dve prirodzené čísla $a, b$ ?

✓Riešenie

Na záver si ešte ukážeme azda najznámejší dôkaz tejto všeobecne známej veci, ktorú vedel dokázať už aj Euklides†.

Tvrdenie 2

Dokážte, že prvočísel je nekonečne veľa.

Dôkaz

Skúste si podobným spôsobom vyriešiť ďalšie dve úlohy:

Úloha 7^*

Dokážte, že existuje nekonečne veľa prvočísel $p$ , ktoré delia $n^2+1$ pre vhodné prirodzené $n$ .

1Nápoveda

Ideme sporom. Ak by ich bolo konečne veľa, označme ich $p_1,p_2,\dots,p_k$ . Skúste zostrojiť vhodný výraz.

2Nápoveda

Zamyslite sa nad výrazom $(p_1\cdot p_2 \cdots p_k)^2+1$ .

✓Riešenie

Predpokladajme, že takýchto prvočísel je konečne veľa, označme ich $p_1, p_2, \dots, p_k$ . Uvažujme číslo

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

Úloha 8^**

Dokážte, že existuje nekonečne veľa prvočísel tvaru $3n+2$ , kde $n$ je prirodzené číslo.

1Nápoveda

Postupujeme ako v predošlých prípadoch, označíme si prvočísla, zostrojujeme vhodný výraz. Je treba si však dať pozor na špeciálne prvočíslo 2 (ktoré je tiež nášho tvaru).

2Nápoveda

Zamyslite sa nad výrazom $3p_1\cdots p_k+2$ , kde $p_1,\dots,p_k$ sú nepárne prvočísla tvaru $3n+2$ .

3Nápoveda

Kľúčom je nájsť nejaké ďalšie prvočíslo tvaru $3n+2$ v prvočíselnom rozklade nášho výrazu. Mohlo by v tomto rozklade nebyť žiadne, čo by to znamenalo?

✓Riešenie

Predpokladajme, že existuje konečne veľa prvočísel tvaru $3n+2$ . Označme $p_1, \dots, p_k$ všetky nepárne prvočísla tohto tvaru (číslo 2 vynechávame). Uvažujme číslo

N = 3p_1 \cdots p_k + 2.

3Čo sme sa naučili

Priame dokazovanie používame, keď sa snažíme z predpokladov odvodiť čo najviac vecí.
Dôkaz sporom sa hodí, keď sa z negácie dokazovaného tvrdenia dá niečo odvodiť, z negácie už používame priame odvodzovanie.
Dôkaz obmenenej vety je vlastne špeciálny prípad dôkazu sporom.

4Čo ďalej

V ďalších materiáloch sa budeme venovať konkrétnym dôkazovým technikám, pričom začneme matematickou indukciou, ktorá je natoľko dôležitá, že si zaslúži samostatný materiál.