{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Cvičení 2 (2. 10. 2023)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 1\n", "\n", "Dokažte, že pro každé $n \\in \\mathbb{N}$ platí: číslo $13$ dělí $3^{n+1}+4^{2n-1}$.\n", "\n", "\n", "\n", "\n", "\n", "\n", "```{admonition} Zobrazit řešení\n", ":class: dropdown warning\n", "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.\n", "\n", "* 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}$.\n", "\n", "Využijeme získaného poznatku a začneme s úpravou výrazu $4^{2n-1}$:\n", "\n", "$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}$\n", "\n", "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$. \n", "\n", "**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}$.\n", "\n", "* 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).\n", "\n", "* Teď spojíme všechny poznatky dohromady:\n", "\n", "$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}$\n", "\n", "Dokázali jsme tedy, že číslo $13$ dělí $3^{n+1}+4^{2n-1}$ pro každé $n \\in \\mathbb{N}$.\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 2\n", "\n", "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$.\n", "\n", "```{admonition} Zobrazit řešení\n", ":class: dropdown warning\n", "Budeme postupovat obdobně jako v předchozím příkladě:\n", "\n", "* Víme, že $5^2\\equiv 25 \\equiv 6 \\pmod{19}$. Toto využijeme obdobně jako v předchozím příkladě:\n", "\n", "* $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}$.\n", "\n", "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$.\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 3\n", "\n", "Dokažte, že pro každé $n \\in \\mathbb{N}$ platí: číslo $31$ dělí $5^{n+1}+6^{2 n-1}$.\n", "\n", "```{admonition} Zobrazit výsledek\n", ":class: dropdown warning\n", "Budeme postupovat obdobně jako v předchozích příkladech:\n", "\n", "*Víme, že $6^2\\equiv 36 \\equiv 5 \\pmod{31}$. Toto využijeme obdobně jako v předchozím příkladě:\n", "\n", "$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}$.\n", "\n", "Dokázali jsme tedy, že číslo $31$ opravdu dělí $5^{n+1}+6^{2 n-1}$ pro každé $n \\in \\mathbb{N}$.\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 4\n", "\n", "Dokažte, že $3^n-2,\\, n\\in \\mathbb{N}$ není dělitelné $13$\n", "\n", "```{admonition} Zobrazit výsledek\n", ":class: dropdown warning\n", "\n", "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", "\n", "* $n=1$: $\\quad3^1 \\equiv 3 \\pmod {13}$\n", "* $n=2$: $\\quad3^2\\equiv$ $3^{1+1}\\equiv$ $3^1 \\cdot 3^1 \\equiv$ $3\\cdot 3 \\equiv$ $9 \\pmod {13}$\n", "* $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", "* $n=4$: $\\quad3^4\\equiv$ $3^{3+1} \\equiv$ $3^3 \\cdot 3^1 \\equiv$ $1\\cdot 3 \\equiv$ $3 \\pmod {13}$\n", "* $n=5$: $\\quad3^5\\equiv$ $3^{4+1} \\equiv$ $3^4 \\cdot 3^1 \\equiv$ $3\\cdot 3 \\equiv$ $9 \\pmod {13}$\n", "* $n=6$: $\\quad3^6\\equiv$ $3^{5+1} \\equiv$ $3^5 \\cdot 3^1 \\equiv$ $9\\cdot 3 \\equiv$ $27\\equiv$ $1 \\pmod {13}$\n", "* $\\dots$\n", "\n", "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}$.\n", "\n", "**Nicméně my si příklad rozebereme ještě více do hloubky:**\n", "\n", "* *Proč získáváme pouze tři různé výsledky pro různé hodnoty $n$ (opět budeme ignorovat číslo $-2$)?*\n", "\n", "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í. \n", "\n", "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", "\n", "* $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", "\n", "\n", "* $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", "\n", "\n", "* $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}$\n", "\n", "\n", "Dokázali jsme, že v žádném z uvedených tří případů není číslo $3^n-2$ dělitélné číslem $13$.\n", "\n", "Můžeme tedy říct, že číslo $3^n-2$ opravdu není dělitelné číslem $13$ pro každé $n \\in \\mathbb{N}$.\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 5\n", "\n", "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.\n", "\n", "\n", "\n", "```{admonition} Zobrazit řešení\n", ":class: dropdown warning\n", "Cayleyho tabulka:\n", "\n", "| $\\circ$ | Kámen | Nůžky | Papír |\n", "|:-------|:-------:|:-------:|:-------:|\n", "| **Kámen** | Kámen | Kámen | Papír |\n", "| **Nůžky** | Kámen | Nůžky | Nůžky |\n", "| **Papír** | Papír | Nůžky | Papír |\n", "\n", "Z tabulky je zřejmé, že operace $\\circ$ je uzavřená na množině $M$ a tedy $(M,\\circ)$ tvoří grupoid.\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 6\n", "\n", "Nechť $(A,*)$ tvoří grupoid. Vysvětlete základní vlastnosti grupoidu: komutativita, asociativita, existence neutrálního prvku a existence inverzního prvku.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 7\n", "\n", "Dokažte, že v grupoidu nemohou existovat dva neutrální prvky.\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.11.5" } }, "nbformat": 4, "nbformat_minor": 4 }