{ "cells": [ { "cell_type": "markdown", "id": "b5e868a7", "metadata": { "editable": true, "slideshow": { "slide_type": "" }, "tags": [] }, "source": [ "# Kapitola 1 - Zbytkové třídy celých čísel" ] }, { "cell_type": "markdown", "id": "88d46b75", "metadata": { "editable": true, "slideshow": { "slide_type": "" }, "tags": [] }, "source": [ "## Teorie" ] }, { "cell_type": "markdown", "id": "cde90581", "metadata": { "editable": true, "slideshow": { "slide_type": "" }, "tags": [] }, "source": [ "```{prf:definition}\n", ":label: pokus2\n", "Nechť $a,b,m \\in \\mathbb{Z}, m>1$. Řekneme, že číslo $a$ je kongruentní s číslem $b$ modulo $m$ (případně podle modulu $m$), jestliže $m | a-b$.\n", "```" ] }, { "cell_type": "markdown", "id": "7a5c2003", "metadata": {}, "source": [ "Skutečnost, že jsou dvě čísla $a$ a $b$ kongruentní modulo $m$ zapisujeme pomocí $a \\equiv b \\pmod m$ případně zkráceně jako $a \\equiv_m b$." ] }, { "cell_type": "markdown", "id": "a9a39360", "metadata": {}, "source": [ "```{prf:theorem}\n", "Nechť $m \\in \\mathbb{Z}, m>1$. Pak pro každé $a, b, c \\in \\mathbb{Z}$ platí:\n", "\n", "a) $a \\equiv a \\pmod m$,\n", "\n", "b) pokud $a \\equiv b \\pmod m$, pak $b \\equiv a \\pmod m$,\n", "\n", "c) pokud $a \\equiv b \\pmod m$ a $b \\equiv c \\pmod m$, pak $a \\equiv c \\pmod m$.\n", "```" ] }, { "cell_type": "markdown", "id": "7f8d5788", "metadata": {}, "source": [ "```{prf:theorem}\n", "Celá čísla $a$ a $b$ jsou kongruentní modulo $m$ právě tehdy, když mají po dělení číslem $m$ stejný zbytek.\n", "```" ] }, { "cell_type": "markdown", "id": "82ce7ccc", "metadata": {}, "source": [ "```{prf:theorem}\n", "Nechť $a, b, c, d, m \\in \\mathbb{Z}, m>1$. Jestliže $a \\equiv b \\pmod m$ a $c \\equiv d \\pmod m$, pak \n", "\n", "a) $a+c \\equiv b+d \\pmod m$,\n", "\n", "b) $a\\cdot c \\equiv b\\cdot d \\pmod m$.\n", "```" ] }, { "cell_type": "markdown", "id": "78a84cf3", "metadata": {}, "source": [ "```{prf:corollary}\n", "Nechť $a \\equiv b\\pmod m, c \\in \\mathbb{Z}, n \\in \\mathbb{N}$. Pak\n", "\n", "a) $a+c \\equiv b+c \\pmod m$,\n", "\n", "b) $a\\cdot c \\equiv b\\cdot c \\pmod m$.\n", "\n", "c) $a^n \\equiv b^n \\pmod m$.\n", "```" ] }, { "cell_type": "markdown", "id": "6e98bbb0", "metadata": {}, "source": [ "```{prf:theorem}\n", "Nechť $a,b,c \\in \\mathbb{Z}, m>1$. Pokud $a \\cdot c \\equiv b \\cdot c \\pmod m$ a zároveň $\\textrm{D}(m,c)=1$, pak $a \\equiv b \\pmod m$.\n", "```" ] }, { "cell_type": "markdown", "id": "3f1f6e42", "metadata": {}, "source": [ "$\\textrm{D}(a,b)$ značí nejmenší společní dělitel čísel $a$ a $b$." ] }, { "cell_type": "markdown", "id": "444d589a", "metadata": {}, "source": [ "```{prf:theorem}\n", "Nechť $\\oplus$ a $\\odot$ jsou operace sčítání a násobení na systému zbytkových tříd $\\overline{\\mathbb{Z}}_m$. Pak\n", "\n", "a) obě operace jsou komutativní a asociativní,\n", "\n", "b) v $\\overline{\\mathbb{Z}}_m$ existuje nulový prvek (neutrální prvek operace $\\oplus$) a jednotkový prvek (neutrální prvek operace $\\odot$),\n", "\n", "c) ke každému prvku ze $\\overline{\\mathbb{Z}}_m$ existuje prvek opačný (inverzní prvek vzhledem k operaci $\\oplus$),\n", "\n", "d) operace $\\odot$ je distributivní vzhledem k operaci $\\oplus$.\n", "```" ] }, { "cell_type": "markdown", "id": "bc787fde", "metadata": {}, "source": [ "## Cvičení" ] }, { "cell_type": "markdown", "id": "673452af", "metadata": {}, "source": [ "````{prf:example}\n", "\n", "a) 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", "```\n", "\n", "b) 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", "```\n", "\n", "c) 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", "```\n", "\n", "d) 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", "```\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "2ae3f81e", "metadata": {}, "source": [ "````{prf:example}\n", "\n", "Nechť $a=352 \\cdot 71 + 55^2 \\cdot 86 + 15 \\cdot 39$. Určete\n", "\n", "a) paritu čísla $a$:\n", "\n", "\n", "```{admonition} Zobrazit řešení\n", ":class: dropdown warning\n", "Problém vyřešíme tak, že spočítáme zbytek výrazu $a$ po dělení číslem 2. Pokud bude zbytek roven 0, jedná se o sudé číslo, pokud bude roven $1$ půjde o číslo liché.\n", "\n", "* Číslo $352$ je sudé, tedy dělitelné číslem $2$ beze zbytku. Můžeme proto psát $352 \\equiv 0 \\pmod 2$\n", "* Naopak číslo $71$ je liché, tedy po dělení číslem $2$ nám zůstane zbytek $1$. Můžeme tedy psát $71 \\equiv 1 \\pmod 2$ \n", "* Číslo $55$ je liché, tedy opět bude zbytek po dělení roven jedné, tj. $55 \\equiv 1 \\pmod 2$ a tedy s využitím *Důsledku 1.1* můžeme psát $55^2 \\equiv 1^2 \\pmod 2$\n", "* Analogicky lze odvodit, že $86 \\equiv 0 \\pmod 2$, $15 \\equiv 1 \\pmod 2$ a $39 \\equiv 1 \\pmod 2$\n", "\n", "Nyní můžeme získané poznatky spojit dohromady:\n", "\n", "$352 \\cdot 71 + 55^2 \\cdot 86 + 15 \\cdot 39 \\equiv \\underbrace{0 \\cdot 1 + 1^2 \\cdot 0+1\\cdot 1}_{=1} \\equiv 1 \\pmod 2$\n", "\n", "Výraz $a$ je tedy kongruentní s $1$ modulo $2$. A protože zbytek po dělení čísla $1$ číslem $2$ je roven $1$, je i zbytek po dělení výrazu $a$ číslem $2$ roven $1$. $a$ je tedy liché číslo.\n", "```\n", "\n", "b) poslední číslici čísla $a$:\n", "\n", "```{admonition} Zobrazit výsledek\n", ":class: dropdown warning\n", "Poslední číslice čísla $a$ je $7$.\n", "```\n", "\n", "c) zbytek po dělení čísla $a$ číslem 7:\n", "\n", "```{admonition} Zobrazit výsledek\n", ":class: dropdown warning\n", "Zbytek po dělení je roven $1$.\n", "```\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "4d8c1193", "metadata": {}, "source": [ "````{prf:example}\n", "Dokažte, že \n", "\n", "a) čí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", "```\n", "\n", "\n", "b) číslo $23^{25}+25^{23}$ je dělitelné číslem $48$,\n", "\n", "```{admonition} Zobrazit výsledek\n", ":class: dropdown warning\n", "Ano, je dělitelné.\n", "```\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "aa5fd3e4", "metadata": {}, "source": [ "````{prf:example}\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 výsledek\n", ":class: dropdown warning\n", "Ano, číslo $6^{n+1}+13\\cdot 5^{2 n}$ je násobkem čísla $19$ pro každé $n \\in \\mathbb{N_0}$.\n", "```\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "0e65878f", "metadata": { "editable": true, "slideshow": { "slide_type": "" }, "tags": [] }, "source": [ "````{prf:example}\n", "\n", "Dokažte, že pro každé $n \\in \\mathbb{N_0}$ platí: číslo $7$ nedělí $3^n + 5^{3 n+4}$.\n", "\n", "```{admonition} Zobrazit výsledek\n", ":class: dropdown warning\n", "Ano, číslo $7$ opravdu nedělí číslo $3^n + 5^{3 n+4}$.\n", "```\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "d76f6089", "metadata": {}, "source": [ "````{prf:example}\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", "Ano, číslo $31$ opravdu dělí $5^{n+1}+6^{2 n-1}$ pro každé $n \\in \\mathbb{N}$.\n", "```\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.6" } }, "nbformat": 4, "nbformat_minor": 5 }