Nepřímý důkaz

Řešení příkladu:

Předpokládejme, že \( \sqrt{2} \) je racionální číslo. To znamená, že existují celá čísla \( a \) a \( b \), kde \( b \ne 0 \), taková že \( \sqrt{2} = \frac{a}{b} \) a zlomek \( \frac{a}{b} \) je v základním tvaru.

Umocněním obou stran dostaneme: \( 2 = \frac{a^2}{b^2} \Rightarrow a^2 = 2b^2 \).

To znamená, že \( a^2 \) je sudé, a tedy i \( a \) je sudé. Nechť \( a = 2k \), kde \( k \in \mathbb{Z} \).

Dosadíme zpět: \( (2k)^2 = 2b^2 \Rightarrow 4k^2 = 2b^2 \Rightarrow b^2 = 2k^2 \), tedy i \( b^2 \) je sudé a tedy i \( b \) je sudé.

Získali jsme, že \( a \) i \( b \) jsou sudá čísla, což odporuje předpokladu, že zlomek \( \frac{a}{b} \) je v základním tvaru.

Tím jsme dospěli ke sporu \Rightarrow \( \sqrt{2} \) není racionální.

Řešení příkladu:

Předpokládejme, že existuje nejmenší kladné racionální číslo, označme jej \( r \).

Pak číslo \( \frac{r}{2} \) je také racionální a kladné a menší než \( r \), protože \( \frac{r}{2} < r \).

Tím jsme dospěli ke sporu s předpokladem, že \( r \) je nejmenší kladné racionální číslo.

\Rightarrow Nejmenší kladné racionální číslo neexistuje.

Řešení příkladu:

Předpokládejme, že existuje celé číslo \( n \), takové že \( 5 \mid (n^2 + 3) \Rightarrow n^2 + 3 \equiv 0 \mod 5 \Rightarrow n^2 \equiv -3 \equiv 2 \mod 5 \).

Vyzkoušíme možné zbytky \( n \mod 5 \):

• \( n \equiv 0 \Rightarrow n^2 \equiv 0 \)
• \( n \equiv 1 \Rightarrow n^2 \equiv 1 \)
• \( n \equiv 2 \Rightarrow n^2 \equiv 4 \)
• \( n \equiv 3 \Rightarrow n^2 \equiv 9 \equiv 4 \)
• \( n \equiv 4 \Rightarrow n^2 \equiv 16 \equiv 1 \)

Žádný z těchto zbytků není roven \(2\) modulo \(5\).

Tím pádem není možné, aby \( n^2 \equiv 2 \mod 5 \) \Rightarrow číslo \( n^2 + 3 \) není dělitelné \(5\).

Řešení příkladu:

Provedeme důkaz sporem. Předpokládejme, že \( n^2 \) je sudé a \( n \) je liché.

Pak existuje \( k \in \mathbb{Z} \) takové, že \( n = 2k + 1 \Rightarrow n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1 \), což je liché číslo.

Tím jsme dospěli ke sporu s předpokladem, že \( n^2 \) je sudé.

\Rightarrow Pokud \( n^2 \) je sudé, pak i \( n \) je sudé.

Řešení příkladu:

Nechť \( a, b \in \mathbb{Q} \), \( a < b \). Uvažujme číslo \( x = a + (b - a)\cdot \frac{\sqrt{2}}{2} \).

Protože \( \sqrt{2} \notin \mathbb{Q} \), pak \( x \notin \mathbb{Q} \Rightarrow x \) je iracionální.

Dále: \( \frac{\sqrt{2}}{2} \in (0,1) \Rightarrow x \in (a, b) \).

Tím jsme nalezli iracionální číslo mezi dvěma racionálními \(\Rightarrow\) tvrzení platí.

Řešení příkladu:

Předpokládejme opak – že existuje konečně mnoho prvočísel: \( p_1, p_2, \ldots, p_n \).

Uvažujme číslo \( N = p_1 p_2 \cdots p_n + 1 \).

Toto číslo není dělitelné žádným z \( p_i \), protože po dělení zbyde \(1\).

Buď je \( N \) prvočíslo, nebo má nějaký prvočíselný dělitel, který není v našem seznamu.

V obou případech jsme našli prvočíslo, které není v původním seznamu \(\Rightarrow\) spor.

\Rightarrow Existuje nekonečně mnoho prvočísel.

Řešení příkladu:

Předpokládejme, že existuje \( n \in \mathbb{Z} \), pro které je \( n^2 + n \) liché.

Pak musí být \( n(n + 1) \) liché.

Jenže součin dvou po sobě jdoucích celých čísel vždy obsahuje jedno sudé číslo \(\Rightarrow\) součin je sudý.

Tím jsme dospěli ke sporu \Rightarrow výraz \( n^2 + n \) je vždy sudý.

Řešení příkladu:

Předpokládejme, že \( \sqrt{3} + \sqrt{2} \in \mathbb{Q} \).

Pak \( \sqrt{3} = (\sqrt{3} + \sqrt{2}) – \sqrt{2} \in \mathbb{Q} \), protože rozdíl racionálních čísel je racionální.

To je ale spor, protože \( \sqrt{3} \notin \mathbb{Q} \).

\Rightarrow \( \sqrt{3} + \sqrt{2} \notin \mathbb{Q} \).

Řešení příkladu:

Předpokládejme, že součet lichého počtu lichých čísel je sudý.

Každé liché číslo má tvar \( 2k + 1 \). Součet \( 2k_1 + 1 + 2k_2 + 1 + \cdots + 2k_{2n+1} + 1 = 2(k_1 + k_2 + \cdots + k_{2n+1}) + (2n + 1) \).

Druhá část výrazu je lichá \(\Rightarrow\) celý součet je lichý.

Tím jsme došli ke sporu \(\Rightarrow\) součet lichého počtu lichých čísel je lichý.

Řešení příkladu:

Předpokládejme, že \( \sqrt{5} = \frac{a}{b} \), kde \( a, b \in \mathbb{Z} \), \( b \ne 0 \), a zlomek je v základním tvaru.

Pak \( 5 = \frac{a^2}{b^2} \Rightarrow a^2 = 5b^2 \).

To znamená, že \( a^2 \) je dělitelné \(5 \Rightarrow\) i \(a \) je dělitelné \(5\), tedy \( a = 5k \).

Dosadíme zpět: \( (5k)^2 = 25k^2 = 5b^2 \Rightarrow b^2 = 5k^2 \Rightarrow b \) je také dělitelné 5.

Pak \( a \) i \( b \) jsou dělitelné \(5 \Rightarrow\) spor s tím, že zlomek je v základním tvaru.

\Rightarrow \( \sqrt{5} \) není racionální číslo.

Řešení příkladu:

Předpokládejme opak, tedy že všechna tři po sobě jdoucí čísla jsou dělitelná třemi.

Nechť tato čísla jsou \( n, n+1, n+2 \). Pokud by všechna byla dělitelná třemi, pak platí:

\( 3 \mid n \), \( 3 \mid (n+1) \), \( 3 \mid (n+2) \).

Pak existují \( a, b, c \in \mathbb{Z} \), že \( n = 3a \), \( n+1 = 3b \), \( n+2 = 3c \).

Z toho plyne: \( 3a + 1 = 3b \Rightarrow 1 = 3b – 3a = 3(b – a) \Rightarrow 3 \mid 1 \), což je spor.

\(\Rightarrow\) Mezi třemi po sobě jdoucími čísly není možné, aby všechna byla dělitelná třemi.

Řešení příkladu:

Provedeme důkaz sporem. Předpokládejme, že \( n^3 \) je sudé a \( n \) je liché.

Pak existuje \( k \in \mathbb{Z} \), že \( n = 2k + 1 \Rightarrow n^3 = (2k + 1)^3 = 8k^3 + 12k^2 + 6k + 1 = 2(4k^3 + 6k^2 + 3k) + 1 \), což je liché.

Spor s předpokladem \(\Rightarrow n \) musí být sudé.

Řešení příkladu:

Předpokládejme, že existuje celé číslo \( n \), takové že \( 6 \mid n \) a zároveň \( n \equiv 1 \mod 3 \).

Z prvního plyne, že \( n = 6k \Rightarrow n \equiv 0 \mod 3 \).

Současně ale \( n \equiv 1 \mod 3 \Rightarrow 0 \equiv 1 \mod 3 \Rightarrow \) spor.

\(\Rightarrow\) Takové číslo neexistuje.

Řešení příkladu:

Nechť \( n \) je liché číslo, tedy \( n = 2k + 1 \Rightarrow n^2 = (2k+1)^2 = 4k^2 + 4k + 1 \).

\( n^2 – 3 = 4k^2 + 4k + 1 – 3 = 4k^2 + 4k – 2 = 2(2k^2 + 2k – 1) \), což je sudé, ale ne dělitelné \(4\).

Předpokládejme, že \( 4 \mid (n^2 – 3) \Rightarrow n^2 – 3 \equiv 0 \mod 4 \Rightarrow n^2 \equiv 3 \mod 4 \).

Vyzkoušíme možné liché zbytky modulo 4: \( n \equiv 1 \Rightarrow n^2 \equiv 1 \), \( n \equiv 3 \Rightarrow n^2 \equiv 9 \equiv 1 \mod 4 \).

Nikdy \( n^2 \equiv 3 \mod 4 \Rightarrow \) spor.

\(\Rightarrow\) Takové \( n \) neexistuje.

Řešení příkladu:

Předpokládejme, že \( ab \) je liché, ale alespoň jedno z čísel \( a, b \) je sudé.

Pak jeden z činitelů je sudý, řekněme \( a = 2k \Rightarrow ab = 2k \cdot b = 2(kb) \), což je sudé.

Spor s předpokladem, že \( ab \) je liché \(\Rightarrow\) oba činitelé musí být liché.

Řešení příkladu:

Předpokládejme, že mezi \( a < b \in \mathbb{R} \) neexistuje žádné racionální číslo.

To by znamenalo, že množina racionálních čísel je disjunktní s intervalem \( (a,b) \), což je nemožné, protože \( \mathbb{Q} \) je hustá v \( \mathbb{R} \).

Formálně: zvolme přirozené číslo \( n \), tak aby \( \frac{1}{n} < b - a \). Potom existuje \( k \in \mathbb{Z} \), že \( \frac{k}{n} \in (a,b) \).

\(\Rightarrow\) Spor s předpokladem \(\Rightarrow\) mezi každými dvěma reálnými čísly existuje racionální číslo.

Řešení příkladu:

Předpokládejme, že \( a^2 \) je dělitelné \(7\), ale \( a \) není.

Pak \( a \not\equiv 0 \mod 7 \Rightarrow a \in \{1,2,3,4,5,6\} \mod 7 \).

Spočítáme \( a^2 \mod 7 \):

• \( 1^2 \equiv 1 \)
• \( 2^2 \equiv 4 \)
• \( 3^2 \equiv 2 \)
• \( 4^2 \equiv 2 \)
• \( 5^2 \equiv 4 \)
• \( 6^2 \equiv 1 \)

V žádném případě \( a^2 \not\equiv 0 \mod 7 \Rightarrow \) spor.

\(\Rightarrow\) Pokud \( a^2 \) je dělitelné \(7\), pak i \( a \) je dělitelné \(7\).

Řešení příkladu:

Předpokládejme, že existuje \( n \in \mathbb{Z} \), takové že \( n^2 = 4k + 2 \Rightarrow n^2 \equiv 2 \mod 4 \).

Vyzkoušíme možné zbytky \( n \mod 4 \):

• \( 0^2 \equiv 0 \)
• \( 1^2 \equiv 1 \)
• \( 2^2 \equiv 0 \)
• \( 3^2 \equiv 1 \)

Žádná druhá mocnina celého čísla nemůže být kongruentní \(2\) modulo \(4 \Rightarrow \) spor.

\(\Rightarrow\) Takové číslo neexistuje.

Řešení příkladu:

Nechť \( a, b \in \mathbb{R} \setminus \mathbb{Q} \), \( a < b \).

Víme, že \( \mathbb{Q} \) je hustá v \( \mathbb{R} \), takže existuje \( q \in \mathbb{Q} \) takové, že \( a < q < b \).

Spor nastane, pokud předpokládáme, že mezi nimi není racionální číslo, což je v rozporu s vlastností hustoty \( \mathbb{Q} \).

\(\Rightarrow\) Tvrzení platí.

Řešení příkladu:

Předpokládejme, že existuje \( n \in \mathbb{Z} \), takové že je sudé i liché zároveň.

Pak \( n = 2k \) i \( n = 2m + 1 \) pro nějaká \( k, m \in \mathbb{Z} \).

Získáme: \( 2k = 2m + 1 \Rightarrow 2(k – m) = 1 \Rightarrow k – m = \frac{1}{2} \in \mathbb{Q} \setminus \mathbb{Z} \Rightarrow \) spor.

\(\Rightarrow\) Takové číslo nemůže existovat.

Řešení příkladu:

Předpokládejme opak, tedy že existují celá čísla \( x, y \), pro která platí:

\( x^2 – 4y^2 = 3 \).

Vyjádříme rovnici jako:

\( x^2 = 4y^2 + 3 \Rightarrow x^2 \equiv 3 \mod 4 \).

Zkoumáme kvadratické zbytky modulo 4. Pro libovolné celé číslo \( n \) platí:

• \( n \equiv 0 \mod 4 \Rightarrow n^2 \equiv 0 \mod 4 \)
• \( n \equiv 1 \mod 4 \Rightarrow n^2 \equiv 1 \mod 4 \)
• \( n \equiv 2 \mod 4 \Rightarrow n^2 \equiv 0 \mod 4 \)
• \( n \equiv 3 \mod 4 \Rightarrow n^2 \equiv 1 \mod 4 \)

Možné hodnoty \( x^2 \mod 4 \) jsou tedy \(0\) nebo \(1\), nikdy však \(3\).

Tedy předpoklad, že \( x^2 \equiv 3 \mod 4 \), vede ke sporu.

\(\Rightarrow\) Neexistují taková celá čísla \( x, y \), která by splňovala zadanou rovnici.

Řešení příkladu:

Nechť \( n, n+1, n+2 \) jsou tři po sobě jdoucí celá čísla.

Předpokládejme, že všechny tři druhé mocniny jsou dělitelné \(3\):

\( 3 \mid n^2 \), \( 3 \mid (n+1)^2 \), \( 3 \mid (n+2)^2 \).

Vzhledem k prvočíselnosti \(3\) platí, že pokud \( 3 \mid a^2 \), pak \( 3 \mid a \).

Tedy \( 3 \mid n \), \( 3 \mid (n+1) \), \( 3 \mid (n+2) \).

To však není možné, protože tři po sobě jdoucí čísla nemohou být všechna dělitelná \(3\).

\(\Rightarrow\) Předpoklad je sporný, tedy alespoň jedna z druhých mocnin není dělitelná \(3\).