{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Cvičení 1 (25. 9. 2023)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 1\n", "\n", "Určete zbytek po dělení čísla $142$ číslem $6$.\n", "\n", "```{admonition} Zobrazit řešení\n", ":class: dropdown warning\n", "* Nejprve si číslo $142$ vhodně upravíme na součet dvou čísel, přičemž se budeme snažit, aby první bylo co největší a dělitelné číslem $6$ beze zbytku: $142=\\underbrace{138}_{=6\\cdot 23}+4$.\n", "\n", "* Číslo $138$ je dělitelné číslem $6$ beze zbytku a tedy platí, že $138\\equiv 0 \\pmod 6$\n", "\n", "* Využijeme *vlastnost a)* *Důsledku 1.1*. Protože víme, že $138\\equiv 0 \\pmod 6$ a $4\\in \\mathbb{Z}$, můžeme psát $138 + 4 \\equiv 0+4 \\pmod 6$\n", "\n", "* Můžeme tedy psát $142 \\equiv 4 \\pmod 6$.\n", "\n", "Zbytek po dělení čísla $142$ číslem $6$ je tedy roven $4$.\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 2\n", "\n", "Určete zbytek po dělení čísla $122+171$ číslem 8.\n", "\n", "\n", "```{admonition} Zobrazit řešení\n", ":class: dropdown warning\n", "**Postup A:**\n", "\n", "S oběma čísly se vypořádáme zvlášť a budeme postupovat analogicky, jako v předchozím příkladě:\n", "\n", "* $122=8\\cdot12+2$ a tedy $122\\equiv 2 \\pmod 8$.\n", "\n", "* $171=8\\cdot21+3$ a tedy $171\\equiv 3 \\pmod 8$.\n", "\n", "* Nyní využijeme vlastnost *a)* *Věty 1.3*. Protože $122\\equiv 2 \\pmod 8$ a $171\\equiv 3 \\pmod 8$, můžeme psát $122+171 \\equiv \\underbrace{2 + 3}_{=5} \\equiv 5 \\pmod 8$.\n", "\n", "Zbytek po dělení čísla $122+171$ číslem $8$ je tedy roven $5$.\n", "\n", "**Postup B:**\n", "\n", "Nejprve obě čísla sečteme a následně budeme postupovat jako v prvním příkladě:\n", "\n", "* $122+171=293=8\\cdot 36 +5$ a tedy $293 \\equiv 5 \\pmod 8$.\n", "\n", "Zbytek po dělení čísla $122+171$ číslem $8$ je tedy roven $5$.\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 3\n", "\n", "Určete zbytek po dělení čísla $2^{30}$ číslem $15$.\n", "\n", "\n", "```{admonition} Zobrazit řešení\n", ":class: dropdown warning\n", "Pokusíme se najít nějakou vhodnou mocninou čísla $2$, která je kongruentní s číslem $0, 1$ nebo $-1$:\n", "\n", "* $2^4 =16$ a je zřejmé, že $16 \\equiv 1 \\pmod {15}$\n", "\n", "* Tohoto poznatku využijeme a upravíme si mocninu čísla $2$: $2^{30}=2^{4\\cdot7+2}=2^{4\\cdot7}\\cdot 2^2 = 16^7 \\cdot 4$\n", "\n", "* Nyní využijeme *vlastnost c)* *Důsledku 1.1*. Protože $16\\equiv 1 \\pmod {15}$, můžeme psát $16^{7} \\equiv \\underbrace{1^7}_{=1} \\equiv 1 \\pmod {15}$.\n", "\n", "* Na závěr využijeme *vlastnost b)* *Důsledku 1.1*. Protože $16^7\\equiv 1 \\pmod {15}$ a $4\\in \\mathbb{Z}$, můžeme psát $16^7 \\cdot 4 \\equiv \\underbrace{1 \\cdot 4}_{=4} \\equiv 4 \\pmod {15}$.\n", "\n", "Zbytek po dělení čísla $2^{30}$ číslem $15$ je tedy roven $4$.\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 4\n", "\n", "Určete zbytek po dělení čísla $181\\cdot 3^{70}$ číslem 13.\n", "\n", "\n", "\n", "```{admonition} Zobrazit řešení\n", ":class: dropdown warning\n", "S oběma čísly se vypořádáme zvlášť a budeme postupovat analogicky, jako v předchozích příkladech:\n", "\n", "* $181=13\\cdot13+12$ a tedy $181\\equiv 12 \\pmod{13}$.\n", "\n", "* Opět se pokusíme najít vhodnou mocninu čísla $3$: $3^3=27\\equiv 1 \\pmod{13}$. Upravíme si tedy mocninu $3^{70}=3^{3\\cdot23+1}=3^{3\\cdot 23}\\cdot 3=27^{23}\\cdot 3$. Využijeme *vlastností b)* a *c)* *Důsledku 1.1* a můžeme psát: $27^{23}\\cdot 3\\equiv 1 \\cdot 3 \\equiv 3 \\pmod{13}$.\n", "\n", "* Na závěr využijeme *vlastnost b) Věty 1.3*. Protože $181\\equiv 12 \\pmod{13}$ a $3^{70}\\equiv 1 \\pmod{13}$, platí: $181\\cdot 3^{70} \\equiv 12\\cdot3 \\equiv 36 \\equiv 10 \\pmod{13}$.\n", "\n", "Zbytek po dělení čísla $181\\cdot 3^{70}$ číslem 13 je tedy roven $10$.\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 5\n", "\n", "Dokažte, že číslo $23^{25}+25^{23}$ je dělitelné číslem $48$.\n", "\n", "```{admonition} Zobrazit řešení\n", ":class: dropdown warning\n", "S oběma čísly se vypořádáme zvlášť a budeme postupovat analogicky, jako v předchozích příkladech:\n", "\n", "* $23^{25}\\equiv$ $23^{24+1}\\equiv$ $23^{24}\\cdot 23^{1}\\equiv$ $23^{2\\cdot 12}\\cdot 23^{1}\\equiv$ $529^{12}\\cdot 23\\equiv$ $1^{12}\\cdot 23\\equiv$ $1\\cdot 23\\equiv$ $23 \\pmod{48}$\n", "\n", "* $25^{23}\\equiv$ $25^{22+1}\\equiv$ $25^{22}\\cdot 25^{1}\\equiv$ $25^{2\\cdot 11}\\cdot 25^{1}\\equiv$ $625^{11}\\cdot 25\\equiv$ $1^{11}\\cdot 25\\equiv$ $1\\cdot 25\\equiv$ $25 \\pmod{48}$\n", "\n", "* Nyní dáme obě zjištění dohromady:\n", "\n", "$23^{25}+25^{23}\\equiv$ $23+25\\equiv$ $48\\equiv$ $0 \\pmod {48}$.\n", "\n", "Tedy ano, dokázali jsme že číslo $23^{25}+25^{23}$ je dělitelné číslem $48$.\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 6\n", "\n", "Dokažte první dvě vlastnosti Věty 1.1.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 7\n", "\n", "Dokažte, že číslo $2^{70}+3^{70}$ je dělitelné číslem $13$.\n", "\n", "```{admonition} Zobrazit řešení\n", ":class: dropdown warning\n", "Je třeba ukázat, že $2^{70}+3^{70} \\equiv 0 \\pmod{13}$:\n", "\n", "\n", "**Postup A:**\n", "\n", "* Nejprve se vypořádáme s výrazem $2^{70}$. Při zkoumání mocnin čísla $2$ si můžeme všimnout, že $2^6=64$ a zbytek po dělení čísla $64$ číslem $13$ je $12$ $(64-4\\cdot 12=64-52=12)$. Můžeme tedy napsat, že $64 \\equiv 12 \\pmod {13}$. Platí ovšem také $12 \\equiv -1 \\pmod {13}$ protože $-1$ a $12$ patří do stejné zbytkové třídy. Nyní je třeba výraz $2^{70}$ vhodně upravit, abychom mohli nově získáný poznatek aplikovat: $2^{70}=2^{6\\cdot 11+4}=2^{6\\cdot 11}\\cdot 2^4=64^{11}\\cdot2^4$. S využitím výše zmíněné kongruence získáváme $64^{11}\\cdot2^4 \\equiv {-1}^{11}\\cdot 2^4 \\equiv -1 \\cdot 16 \\equiv -16 \\pmod{13}$. \n", "* Nyní se zaměříme na výraz $3^{70}$, tedy prozkoumáme mocniny čísla $3$. Je zřejmé, že $3^3=27$ a platí $27 \\equiv 1 \\pmod{13}$. Upravíme si tedy výraz $3^{70}=3^{3\\cdot 23+1}=3^{3\\cdot 23}\\cdot 3= 27^{23}\\cdot3$ a aplikujeme kongruenci $27^{23}\\cdot3 \\equiv 1^{27}\\cdot 3 = 3 \\pmod{13}$.\n", "\n", "Teď už zbývá jen získáné poznatky spojit: \n", "\n", "$2^{70}+3^{70} \\equiv -16 +3 \\equiv 0 \\pmod {13}$.\n", "\n", "Tedy ano, dokázali jsme, že číslo $2^{70}+3^{70}$ je beze zbytku dělitelném číslem $13$.\n", "\n", "**Postup B:**\n", "\n", "Alternativní postup, tentokrát již bez komentáře\n", "\n", "* $2^{70}+3^{70} \\equiv$ $(2^2)^{35}+(3^2)^{35}\\equiv$ $4^{35}+9^{35}\\equiv$ $4^{34+1}+9^{34+1}\\equiv$ $(4^2)^{17}\\cdot4+(9^2)^{17}\\cdot 9\\equiv$ $16^{17}\\cdot4+81^{17}\\cdot9\\equiv$ $3^{17}\\cdot 4+ 3^{17}\\cdot 9\\equiv$ $3^{17}\\cdot(4+9)\\equiv$ $3^{17}\\cdot13 \\equiv$ $3^{17}\\cdot 0\\equiv$ $0 \\pmod{13}$\n", "\n", "Tedy ano, dokázali jsme, že číslo $2^{70}+3^{70}$ je beze zbytku dělitelném číslem $13$.\n", "\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": 5 }