Cvičení 2 (2. 10. 2023)#

Příklad 1#

Dokažte, že pro každé \(n \in \mathbb{N}\) platí: číslo \(13\) dělí \(3^{n+1}+4^{2n-1}\).

Zobrazit řešení

Musíme dokázat, že \(3^{n+1}+4^{2n-1} \equiv 0 \pmod {13}\). Největším problémem je proměnná \(n\), se kterou nelze standardně počítat. Proto bude našim cílem upravit (s využitím kongruence) výraz na součin dvou činitelů tak, aby se proměnná \(n\) objevovala jen v první z nich a druhý činitel byl kongruentní s nulou. Pak už jen využijeme vlastnosti, že cokoliv násobeno nulou je nula a proto je i náš výraz kongruentní s nulou.

  • První činitel (obsahující proměnnou \(n\)) můžeme získat pomocí vytknutí. To ovšem momentálně není možné, protože obě mocniny mají odlišný základ. Pokusíme se tedy najít způsob, jak mocninu se základem \(3\) převést na mocninnu se základem \(4\) nebo naopak. S použitím kongruence lze dojít k následujícímu: \(4^2 \equiv 16 \equiv 3 \pmod {13}\).

Využijeme získaného poznatku a začneme s úpravou výrazu \(4^{2n-1}\):

\(4^{2n-1}\equiv\) \(4^{2n-2+1}\equiv\) \(4^{2(n-2)+1}\equiv\) \(4^{2(n-1)}\cdot4^1\equiv\) \(16^{(n-1)}\cdot 4\equiv\) \(3^{(n-1)}\cdot 4 \pmod {13}\)

V první kroku úpravy jsme využili toho, že k libovolnému číslu můžeme vždy přičíst nulu. K exponentu \(2n-1\) jsme tedy přičetli \(\underbrace{1-1}_{=0}\) a dostali jsme \(2n-1+1-1=\) \(2n-2+1\). To jsme udělali proto, abychom mohli vytknout dvojku a získat \(2(n-1)+1\).

POZOR: Pokud bychom tento krok neprovedli, úpravou bychom došli k \(4^{2n-1}\equiv\) \(4^{2n}\cdot 4^{-1}\equiv\) \(16^n\cdot 4^{-1}\equiv\) \(3^n\cdot 4^{-1} \pmod {13}\) a museli bychom řešit co udělat se \(4^{-1}\).

  • Nyní upravíme člen \(3^{n+1}\) tak, aby z něj bylo možné vytknout \(3^{n-1}\): \(3^{n+1}=\) \(3^{n-1+2}=\) \(3^{n-1}\cdot 3^2\). Použili jsme obdobný trik jako v předchozím bodě (v červeném textu).

  • Teď spojíme všechny poznatky dohromady:

\(3^{n+1}+4^{2n-1}\equiv\) \(3^{n-1}\cdot 3^2+3^{(n-1)}\cdot 4\equiv\) \(3^{n-1}\cdot(3^2+4)\equiv\) \(3^{n-1}\cdot13\equiv\) \(3^{n-1}\cdot 0\equiv\) \(0\pmod {13}\)

Dokázali jsme tedy, že číslo \(13\) dělí \(3^{n+1}+4^{2n-1}\) pro každé \(n \in \mathbb{N}\).

Příklad 2#

Dokažte, že pro každé \(n \in \mathbb{N}_0\) je číslo \(6^{n+1}+13\cdot 5^{2 n}\) násobkem čísla \(19\).

Zobrazit řešení

Budeme postupovat obdobně jako v předchozím příkladě:

  • Víme, že \(5^2\equiv 25 \equiv 6 \pmod{19}\). Toto využijeme obdobně jako v předchozím příkladě:

  • \(6^{n+1}+13\cdot 5^{2 n}\equiv\) \(6^{n}\cdot 6^1+13\cdot 25^{n}\equiv\) \(6^{n}\cdot 6+13\cdot 6^{n}\equiv\) \(6^{n}\cdot (6+13)\equiv\) \(6^n \cdot 19 \equiv\) \(6^n \cdot 0 \equiv\) \(0 \pmod {19}\).

Dokázali jsme tedy, že číslo \(19\) dělí \(6^{n+1}+13\cdot 5^{2 n}\) pro každé \(n \in \mathbb{N}_0\).

Příklad 3#

Dokažte, že pro každé \(n \in \mathbb{N}\) platí: číslo \(31\) dělí \(5^{n+1}+6^{2 n-1}\).

Zobrazit výsledek

Budeme postupovat obdobně jako v předchozích příkladech:

*Víme, že \(6^2\equiv 36 \equiv 5 \pmod{31}\). Toto využijeme obdobně jako v předchozím příkladě:

\(5^{n+1}+6^{2 n-1}\equiv\) \(5^{(n-1)+2}+6^{(2 n-2)+1}\equiv\) \(5^{(n-1)}\cdot 5^2+6^{2(n-1)}\cdot 6\equiv\) \(5^{(n-1)}\cdot 25+36^{(n-1)}\cdot 6\equiv\) \(5^{(n-1)}\cdot 25+5^{(n-1)}\cdot 6\equiv\) \(5^{(n-1)}\cdot (25+ 6)\equiv\) \(5^{(n-1)}\cdot 31\equiv\) \(5^{(n-1)}\cdot 0\equiv\) \(0 \pmod {31}\).

Dokázali jsme tedy, že číslo \(31\) opravdu dělí \(5^{n+1}+6^{2 n-1}\) pro každé \(n \in \mathbb{N}\).

Příklad 4#

Dokažte, že \(3^n-2,\, n\in \mathbb{N}\) není dělitelné \(13\)

Zobrazit výsledek

Nyní řešíme jiný problém - chceme určit, že dané číslo není dělitelné číslem \(13\). Pro pochopení je vhodné se nejprve podívat, jak se výsledný výraz \(3^n\) bude měnit pro různé hodnoty \(n\) (\(-2\) zatím budeme ignorovat):

  • \(n=1\): \(\quad3^1 \equiv 3 \pmod {13}\)

  • \(n=2\): \(\quad3^2\equiv\) \(3^{1+1}\equiv\) \(3^1 \cdot 3^1 \equiv\) \(3\cdot 3 \equiv\) \(9 \pmod {13}\)

  • \(n=3\): \(\quad3^3\equiv\) \(3^{2+1}\equiv\) \(3^2 \cdot 3^1 \equiv\) \(9\cdot 3 \equiv\) \(27 \equiv\) \(1 \pmod {13}\)

  • \(n=4\): \(\quad3^4\equiv\) \(3^{3+1} \equiv\) \(3^3 \cdot 3^1 \equiv\) \(1\cdot 3 \equiv\) \(3 \pmod {13}\)

  • \(n=5\): \(\quad3^5\equiv\) \(3^{4+1} \equiv\) \(3^4 \cdot 3^1 \equiv\) \(3\cdot 3 \equiv\) \(9 \pmod {13}\)

  • \(n=6\): \(\quad3^6\equiv\) \(3^{5+1} \equiv\) \(3^5 \cdot 3^1 \equiv\) \(9\cdot 3 \equiv\) \(27\equiv\) \(1 \pmod {13}\)

  • \(\dots\)

Jak vidíme, můžeme dostat tři různé výsledky, které se nám opakují: \(3, 9\) a \(1\). Nyní stačí vzít opět do úvahy \(-2\) a podívat se, zda některý z našich výsledků bude po odečtení \(2\) kongruentní s \(0\) modulo \(13\). Protože není, můžeme říct, že číslo \(3^n-2\) není dělitelné číslem \(13\) pro každé \(n \in \mathbb{N}\).

Nicméně my si příklad rozebereme ještě více do hloubky:

  • Proč získáváme pouze tři různé výsledky pro různé hodnoty \(n\) (opět budeme ignorovat číslo \(-2\))?

Všimněme si, že hodnotu \(3^{n+1}\) můžeme jednoduše zjistit tak, že výsledek \(3^n\) vynásobíme číslem \(3\) (jak je znázorněno výše). Dále je třeba si uvědomit, že pokud je \(n=3\), dostáváme \(3^3 \equiv 27 \equiv 1 \pmod {13}\). Toto je velmi důležité, protože tím dochází „jakoby k restartu“ našich výpočtů. Proto \(3^4\equiv \underbrace{3^3}_{\equiv 1} \cdot 3 \equiv 3 \pmod {13}\). Tedy místo \(3^4\) můžeme uvažovat \(3^1\). Z uvedeného lze vyvodit, že pokud je exponent vyšší než \(3\), můžeme ho zmenšit o \(3\) a výsledek to neovlivní.

Z toho co jsme si řekli plyne, že není třeba příklad vyšetřovat pro každou hodnotu \(n\) zvlášť (to by ani nebylo možné), ale stačí se soustředit na situace, kdy je \(n\) rovno násobku tří (tj. lze zapsat jako \(n=3 \cdot k\) pro \(k\in \mathbb{N}\)), kdy je zbytek po dělení \(n\) číslem \(3\) roven jedné (tj. lze zapsat jako \(n=3\cdot k+1\) pro \(k\in \mathbb{N}\)) a kdy je zbytek po dělení \(n\) číslem \(3\) roven dvěma (tj. lze zapsat jako \(n=3\cdot k+1\) pro \(k\in \mathbb{N}\)). Tedy:

  • \(n=3\cdot k:\) \(\quad3^n-2\equiv\) \(3^{3 k}-2\equiv\) \(27^k-2\equiv\) \(1^k-2\equiv\) \(1-2\equiv\) \(-1\equiv\) \(12 \pmod {13}\)

  • \(n=3\cdot k+1:\) \(\quad3^n-2\equiv\) \(3^{3 k+1}-2\equiv\) \(3^{3 k}\cdot 3-2\equiv\) \(27^k\cdot3-2\equiv\) \(1^k\cdot 3-2\equiv\) \(1\cdot 3-2\equiv\) \(1 \pmod {13}\)

  • \(n=3\cdot k+2:\) \(\quad3^n-2\equiv\) \(3^{3 k+2}-2\equiv\) \(3^{3 k}\cdot 3^2-2\equiv\) \(27^k\cdot9-2\equiv\) \(1^k\cdot 9-2\equiv\) \(7 \pmod {13}\)

Dokázali jsme, že v žádném z uvedených tří případů není číslo \(3^n-2\) dělitélné číslem \(13\).

Můžeme tedy říct, že číslo \(3^n-2\) opravdu není dělitelné číslem \(13\) pro každé \(n \in \mathbb{N}\).

Příklad 5#

Nechť \(M=\lbrace \textrm{Kámen}, \textrm{Nůžky}, \textrm{Papír}\rbrace\) a nechť \(\circ\) je binární operace, která libolvolným dvěma prvkům z množiny \(M\) přiřadí takový prvek, který vyhrává dle pravidel známé hry Kámen, nůžky papír. Pokud byl vybrán dvakrát stejný prvek (tj. došlo k remíze), vyhrává právě tento prvek. Sestrojte Cayleyho tabulku a rozhodněte, zda uspořádaná dvojice \((M,\circ)\) tvoří grupoid.

Zobrazit řešení

Cayleyho tabulka:

\(\circ\)

Kámen

Nůžky

Papír

Kámen

Kámen

Kámen

Papír

Nůžky

Kámen

Nůžky

Nůžky

Papír

Papír

Nůžky

Papír

Z tabulky je zřejmé, že operace \(\circ\) je uzavřená na množině \(M\) a tedy \((M,\circ)\) tvoří grupoid.

Příklad 6#

Nechť \((A,*)\) tvoří grupoid. Vysvětlete základní vlastnosti grupoidu: komutativita, asociativita, existence neutrálního prvku a existence inverzního prvku.

Příklad 7#

Dokažte, že v grupoidu nemohou existovat dva neutrální prvky.