Úvod do diskrétní matematiky

V kontextu diskrétní matematiky je význam slova diskrétní zaměnitelný se slovem nespojitý, neboli se zabývá strukturami, které lze považovat za nespojité.

Pro nespojité struktury existuje [[Typy zobrazení#Bijektivní zobrazení|bijektivní zobrazení]] s [[Číselné množiny#Přirozená čísla|množinou přirozených čísel]].

Řešení vzorových testů

Řešení příkladů z PDF

Úloha 1

Úloha 2

Úloha 3

Úloha 4

Úloha 5

Úloha 6

Úloha 7

Úloha 8

Úloha 9

!!! "Zadání" Určete \(\varphi{(n)}\), kde

1. $\varphi{(2478175)}$
2. $\varphi{(367)}$

Úloha 10

Řešení k testu 6.2.2020

Úloha 1

Rozklady čísel na prvočísla

• \(210600 = 2^3 \cdot 3^4 \cdot 5^2 \cdot 13\)
• \(117000 = 2^3 \cdot 3^2 \cdot 5^3 \cdot 13\)
• \(238125 = 3^1 \cdot 5^4 \cdot 11 \cdot 13\)

flowchart LR
    r1(210 600)
    r1 --> r2(100)
    r2 --> r4([5])
    r2 --> r5(20)
    r5 --> r6([5])
    r5 --> r7(4)
    r7 --> r8([2])
    r7 --> r9([2])

    r1 --> r3(2106)
    r3 --> r10([2])
    r3 --> r11(1053)
    r11 --> r12([3])
    r11 --> r13(351)
    r13 --> r14([3])
    r13 --> r15(117)
    r15 --> r16([3])
    r15 --> r17(39)
    r17 --> r18([3])
    r17 --> r19([13])

flowchart LR
    r1(117 000)
    r1 --> r2(1000)
    r2 --> r4([5])
    r2 --> r5(200)
    r5 --> r6([5])
    r5 --> r7(40)
    r7 --> r8(5)
    r7 --> r9(8)
    r9 --> r10([2])
    r9 --> r11(4)
    r11 --> r12([2])
    r11 --> r13([2])

    r1 --> r14(117)
    r14 --> r15([3])
    r14 --> r16(39)
    r16 --> r17([13])
    r16 --> r18([3])

flowchart LR
    r1(268125)
    r1 --> r3([5])
    r1 --> r2(53625)
    r2 --> r5([5])
    r2 --> r4(10725)
    r4 --> r7([5])
    r4 --> r8(2145)
    r8 --> r9([5])
    r8 --> r10(429)
    r10 --> r11([3])
    r10 --> r12(143)
    r12 --> r13([13])
    r12 --> r14([11])

Určení NSD

Pokud máme čísla \(a, b, c\) v jejich prvočíselném rozkladu, můžeme určit největšího společného dělitele. Ten se spočítá jako součin nejvyšších společných mocnic. To znamená, že musíme najít taková čísla a jejich mocniny, která jsou obsažena v každém zkoumaném čísle.

Pro názornost udělám tabulku četností prvočísel. Vybíráme takové číslo, které je ve sloupci nejmenší (samozřejmě kromě čísla označující prvočíslo, jehož četnost je popisována). Výsledný nejmenší společný dělitel \(NSD(a, b, c) = 3 \cdot 5^2 \cdot 13\).

Počet společných dělitelů

Počet společných dělitelů čísla lze vypočítat pomocí vztahu:

Určení všech dělitelů čísla

Určení NSN

K další úloze bude potřeba spočítat nejmenší společný násobek. Ten se spočítá jako podíl součinu všech čísel a největšího společného dělitele.

Konkrétní číslo nebudeme dopočítávat, protože se na něj zadání neptá a v další části, kde počítáme výsledek Eulerovy funkce, není potřeba.

Výpočet Eulerovy funkce

Úloha 2

Ověření řešení diofantické rovnice

Než začneme s výpočtem, je potřeba ověřit, zda má diofantická rovnice nějaké celočíselné řešení. Pokud rozložíme všechna čísla na prvočinitele, zjistíme, že mají společný faktor 11. Platí, že \(NSD(a, b) = 11\). Protože číslo 11 je také součástí prvočíselného rozkladu čísla \(c\), znamená to, že největší společný dělitel \(a\) a \(b\) dělí i číslo \(c\). Z toho vyplývá, že diofantická rovnice má řešení.

flowchart LR
    r1(803)
    r1 --> r3([11])
    r1 --> r2(73)

flowchart LR
    r1(1397)
    r1 --> r3([11])
    r1 --> r2(127)

flowchart LR
    r1(1397)
    r1 --> r3([11])
    r1 --> r2(179)

Řešení rovnice přes vzorečky

Řešení lineární diofantické rovnice začíná zjednodušením rovnice vydělením všech koeficientů jejich největším společným dělitelem (zde 11), což vede k jednodušší rovnici. Dále pomocí rozšířeného Eukleidova algoritmu a tabulky rozvoje v řetězové zlomky najdeme základní řešení rovnice, konkrétně \(x=−40\) a \(y=−23\). Tyto hodnoty platí pro pravou stranu upravené rovnice \(73x - 127y = 1\), nyní je potřeba je upravit, aby byly pro rovnici \(73x - 127y = -179\). Nalezené Bezoutovy koeficienty tak vynásobíme pravou stranou, což tady je \(-179\) a tím získáme partikulární řešení \(x_0 = 7160\) a \(y = 4117\).

Řešení pomocí kongruencí

Teď musíme najít celočíselná řešení této rovnice, což znamená, že hledáme hodnoty \(y\), pro které bude čitatel \(−179+127y\) dělitelný číslem 73. Jinými slovy, potřebujeme zjistit, pro které hodnoty \(y\) platí, že zbytek po dělení \(−179+127y\) číslem 73 je nula. K tomu používáme kongruence, protože kongruence nám umožňují zjistit, které hodnoty dávají konkrétní zbytek po dělení.

Nyní už postupujeme standardně jako u řešení každé jiné lineární kongruence. Pomocí euklidova algoritmu najdeme multiplikativní inverzi k číslu 54 a následně dostaneme upravenou kongruenci tak, abychom ji měli ve tvaru \(y = ? \pmod{73}\).

Našli jsme obecné řešení pro \(y\) - nyní nám zbývá akorát nalézt \(x\). To můžeme provést buďto dosazením do původní rovnice, a nebo do výrazu, kdy jsme si už \(x\) z rovnice vyjadřovali.

Ve výsledku máme tedy následující řešení rovnice:

• Obecné řešení \(x = 48 + 127k\), \(y = 29 + 73k\), \(k \in \mathbb{Z}\)
• Partikulární řešení \(k = 0\), \(x = 48\), \(y = 29\)

Nalezení největšího celého x menší než -2020

Úloha 3

Řešení soustavy

Kolik celých čísel soustavě vyhovuje?

Nekonečně mnoho - ta, pro která je zbytek po dělení 360 roven 267.

Najděte největší x, které vyhovuje podmínce

Úloha 4

Výpočet součinu

Výsledek součinu \(f(x) \cdot g(x)\) v \(\mathbb{Z}_7 \mod{(2x^4 + 4x^2 + 5x + 1)}\) je \(6x^3 + 2x^2 + x + 3\).

Je polynom ireducibilní?

Polynom je ireducibilní v \(\mathbb{Z}_7\), pokud nemá v \(\mathbb{Z}_7\) ani jeden kořen. To znamená, že musí platit \(f(x)\neq 0, x \in \mathbb{Z}\).

Dále nemusíme počítat, protože jsme nalezli kořen polynomu \(f(x) = 6x^3 + 2x^2 + 4\) v \(\mathbb{Z}_7\). Polynom je tedy reducibilní, protože lze dále rozložit na součin polynomů.

Úloha 5

Multiplikativní grupa

Uvažujme grupu \(G(M, \cdot)\).

Uzavřenost operace

Operace násobení je pro celá čísla uzavřená, což znamená, že součin \(m \cdot n\) také patří mezi celá čísla. Platí ale, že součin tohoto výrazu s číslem \(2020^2\) náleží do množiny \(M\)? Ano, protože prvky množiny \(M\) jsou definovány jako násobky čísla 2020, a \(2020^2\) je rovněž násobkem 2020. Výsledkem je tedy násobek čísla 2020 vynásobený celým číslem, což odpovídá definici prvků množiny \(M\). Proto je operace násobení uzavřená i vůči množině \(M\).

Asociativita

Existence neutrálního prvku

Neutrální prvek v grupě \(G(M, \cdot)\) neexistuje, protože \(\frac{1}{2020 \cdot n}\) není celé číslo.

Existence inverzního prvku

Dokazovat existenci inverzního prvku \(i\) nemá smysl, protože jeho definice spoléhá na existenci neutrálního prvku \(e\). Ovšem pro názornost zde předvedu, že opravdu neexistuje. Pro násobení v celých číslech je neutrálním prvkem číslo \(1\), tudíž budeme uvažovat, že tohle je i neutrální prvek naší množiny \(M\) (jak jsme ale dokázali v předchozím odstavci, není to pravda!).

Aditivní grupa

Uvažujme grupu \(G(M, +)\).

Uzavřenost operace

Operace sčítání je pro celá čísla uzavřená, což znamená, že součet \(m+n\) také patří mezi celá čísla. Platí ale, že součin tohoto výrazu s číslem \(2020\) náleží do množiny \(M\)? Ano, protože prvky množiny \(M\) jsou definovány jako celočíselné násobky čísla 2020. Výsledkem je násobek čísla 2020 vynásobený celým číslem, což odpovídá definici prvků množiny \(M\). Proto je operace sčítání uzavřená i vůči množině \(M\).

Asociativita

Existence neutrálního prvku

Neutrální prvek v grupě \(G(M, +)\) existuje a je to \(0\).

Existence inverzního prvku

Závěry

Množina \(M = \{2020 \cdot m \mid m \in \mathbb{Z}\}\)

1. Netvoří multiplikativní grupu \(G(M, \cdot)\), protože neexistuje neutrální a inverzní prvek, který by byl součástí množiny \(M\).
2. Tvoří aditivní grupu \(G(M, +)\) s neutrálním prvkem \(e = 0\) a inverzním prvkem \(i = -2020 \cdot m\).

Řešení k testu 4.3.2021

Úloha 1

Úloha 2

Úloha 3

Úloha 4

Úloha 5

Řešení k testu 9.2.2021

Úloha 2

Zápis ve tvaru disjunktních cyklů.