Vlastnosti celých čísel, Euklidův algoritmus. Binární relace. Matematická indukce, rekurzivní vztahy.

B4B01DMA Webové stránky předmětu

• Dělitelnost – definice, základní vlastnosti (například tranzitivita), výpočet gcd(a, b).
• Celá čísla modulo n – definice kongruence, pravidla počítání, inverzní číslo a podmínky jeho existence.
• Bezoutova identita – vyjádření gcd jako lineární kombinace čísel a, b. Využití pro řešení diofantických rovnic a hledání inverzního čísla modulo n.
• Euklidův algoritmus – teorie a praxe výpočtu gcd postupným dělením se zbytkem. Rozšířená verze umožňující získat Bezoutovu identitu.
• Binární relace – definice a příklady. Čtyři základní vlastnosti: reflexivita, symetrie, antisymetrie, tranzitivita. Ilustrace grafem relace nebo příklady ze života.
• Indukce – princip matematické indukce, slabá a silná verze, ilustrace na jednoduchých důkazech.
• Rekurentní rovnice – vlastnosti homogenních lineárních rekurentních rovnic. Řešení jako vektorový prostor s bází určenou kořeny charakteristického polynomu.

Nechť $a,b\in \mathbb{Z}$. Řekneme, že $a$ dělí $b$, značeno $a|b$, jestliže existuje $k \in \mathbb{Z}$ takové, že $b = k \cdot a$. V takovém případě říkáme $a$ je faktor $b$ a že $b$ je násobek $a$.

Vlastnosti této relace:

1. reflexivní: ano
2. symetrická: ne
3. antisymetrická: ano
4. tranzitivní: ano

$\text{gcd}(a,b)$ znamená “Greatest Common Denominator” (největší společný dělitel). Lze se k tomu dostat přes prvočíslený rozklad nebo Euklidův algoritmus.

$n = \text{gcd}(a,b)$ pokud platí $n|a$ a $n|b$ a $n$ je největší číslo s touto vlastností.

– co je kongruence, jak se tam počítá, co je inverzní číslo a kdy existuje.

Modulo: Zbytek po dělení

Kongurence:

Čísla $a,b\in \mathbb{Z}$ jsou kongurentní modulo $n$ pokud mají stejný zbytek po dělení $n\in \mathbb{Z}$ neboli $n|(b-a)$

Značíme: $a \equiv b \pmod{n}$.

Výpočet Kongurence $a \equiv b \pmod{n}$:

Můžeme vypočítat pomocí $a \pmod{n} = b \pmod{n}$

Vlastnosti: Nechť n ∈ N , uvažujme a , b , u , v ∈ Z takové, že a ≡ u mod n a b ≡ v mod n

• $a + b \equiv u + v \pmod{n} \\[6pt]$
• $a - b \equiv u - v \pmod{n} \\[6pt]$
• $ab \equiv uv \pmod{n}$

(bonus - značeni)

$a \oplus b = (a + b) \mod n $

$a \odot b = (a \cdot b) \mod n$

Inverzní číslo

Nechť $a \in \mathbb{Z}$. Řekneme, že $x\in \mathbb{Z}$ je inverzní číslo k $a$ modulo $n$, jesliže $a\cdot x \equiv 1$

Pro $a$ existuje inverzní číslo modulo $n$ právě tehdy, když $\text{gcd}(a,n) = 1$ a pokud existuje tak je jediný.

– Která gcd poskytne jako lineární kombinaci čísel a,b. K čemu se dá použít: hledání inverzního čísla ve světě modulo, řešení diofantických rovnic.

Bezoutova identita je lineární diofantická rovnice. Říká že v $gcd(a,b); a,b\in \mathbb{N}$ lze zapsat jako lineární kombinaci těchto dvou čísel, jejíž koeficienty jsou celá čísla ($\alpha,\beta \in \mathbb{Z}$).

Neboli:

$$gcd(a,b) = \alpha a + \beta b; a,b\in \mathbb{N}; \alpha,\beta \in \mathbb{Z}$$

Například:

Největší společní dělitel čísel 12 a 42 je 6. Bezoutova identita tedy je: $$\alpha \cdot 12 + \beta \cdot 42 = 6$$

Jedno z možných řešení pro $(\alpha,\beta)=(-3,1)$.

Hledání inverzního čísla (algoritmus)

Hledáme inverzní prvek $a\in\mathbb{Z}_n$ ($\mathbb{Z}_n$ znamená v celých číslech modulo $n$).

1. Najdeme $gcd(a,n) = A\cdot a + B\cdot n$ (v podstatě ve formátu Bezoutovy identity, toto lze nalézt např. pomocí rozšířeného Euklidova algoritmu)
2. Jestliže $gcd(a,n)>1$, pak inverzní prvek k $a$ v $\mathbb{Z}_n$ neexistuje.
3. Jestliže $gcd(a,n) = 1$, pak bezoutova identita dává $1 = a \cdot A + B \cdot n$. To znamená, že $a \cdot A \equiv 1 \pmod{n}$ a $A$ je inverzní číslo k $a \mod n$.

Definice diofantické rovnice:

Pojem lineární diofantická rovnice označujme libovolnou rovnici typu $ax + by = c$ s neznámými $x,y\in \mathbb{Z}$, kde $a,b,c \in \mathbb{Z}$ jsou konstanty.

Řešení diofantických rovnic:

Nechť $a,b,c\in \mathbb{Z}$. Lineární diofantická rovnice $ax + by = c$ má alespoň jedno řešení právě tehdy, když c je násobkem $gcd(a,b)$ (téměř přímo vychází z Bezoutovy identity).

Jeli daná diofantická rovnice $ax +by = c$, pak definujeme její přidruženou homogenní rovnici jako $ax + by = 0$.

Věta o řešení homogeních rovnic:

Uvažujme rovnici $ax+by=0$ pro $a,b \in \mathbb{Z}$. Množina všech jejích celočíslených řešení je $$\left\{ \left(k \frac{b}{\gcd(a, b)}, - k \frac{a}{\gcd(a, b)}\right) : k \in \mathbb{Z} \right\} $$

Algoritmus řešení diofantických rovnic:

Algoritmus pro nalezení všech celočíselných řešení rovnice $ax+by=c$.

1. Najdeme $gcd(a,b)=A\cdot a + B\cdot b$ (Podobné jako u inverzního čísla, vychází z Bezoutovy identity)
2. Jestliže $c$ není násobkem gcd(a,b), pak neexistuje řešení
3. Jestliže $gcd(a,b)$ dělí c:
   1. Zadefinujeme $c'=\frac{c}{gcd(a,b)}$ a získáme partikulární řešení $x_p=Ac'$ a $y_p = Bc'$
   2. Pro jednochost zápisu zadefinujeme $a'=\frac{a}{gcd(a,b)}$, $b'=-\frac{b}{gcd(a,b)}$ pro $k\in \mathbb{Z}$(Toto vychází z věty o řešení homogeních rovnic).
   3. Sečtením partikulárního a obecného homogenního řešení získáme množinu všech celočíselných řešení $$x = x_p + kb', y = y_p - ka' \text{ pro } k \in \mathbb{Z}$$ Případně lze prohodit $-$ pro získání $$x = x_p - kb', y = y_p + ka' \text{ pro } k \in \mathbb{Z}$$

Slovy autora: “Pro řešení difonatických rovnic musíme najít 2 části řešení, homogenní a partikulární část. Partikulární část řešení najde jedno specifické řešení diofantické rovnice, ale abychom našli všechny řešení tak musíme vyřešit homogenní část ta nám umožní najít všechny řešení.”

– jak funguje, teoreticky (přechod ke zbytku po dělení) i prakticky, jak se pozná kdy končí. Jak funguje jeho rozšířená verze, která umí poskytnout Bezoutovu identitu (prakticky).

Ve své základní verzi slouží k hledání GCD (Největšího společného násobku).

Hledáme částečné zbytky po dělení, kdy postupně zmenšujeme čísla. Prakticky vždy spočteme zbytek po dělení nalezením největšího násobku dalšího čísla, který od původního odečteme. Jakmile nalezneme 0 algoritmus končí a číslo nad je $\text{gcd}$. Níže je uveden příklad pro čísla $408$ a $108$:

Rozšířený Euklidův algoritmus najde nejen GCD (největší společný dělitel), ale zároveň i lineární kombinaci počátečních čísel ze kterých se GCD skládá, což je kritické pro použití Bezoutovy identity a řešení diofantických rovnic. Pro shrnutí: Nechť $a,b \in \mathbb{N}$, poté Euklidův algoritmus dokáže najít $A,B \in \mathbb{Z}$, tak že $a\cdot A + b\cdot B = gcd(a,b)$.

Po jeho použití dostaneme rovnou Bezoutovu identitu, zkonstruujeme ho následující tabulkou, kde vedle původních čísel dosadíme jednotkovou matici (zde hledáme $\text{gcd}(408, 108)$ a Bezoutovu identitu $12 = A\cdot408 + B\cdot108$), princip je stejný jako u Euklidova algoritmu:

Každý řádek se skládá z $r_i$ | $x_i$ | $y_i$, kde $r_i = x_i\cdot a + y_i\cdot b$. Pro výpočet řádku $i+1$ hledáme $a = \textbf{floor}(r_{i-1} / r_i)$ poté nový řádek je $r_{i+1}$ | $x_i\cdot (-a) + x_{i-1}$ | $y_i\cdot (-a) + y_{i-1}$

definice a její ilustrace na jednoduchých příkladech. Čtyři základní vlastnosti (reflexivita, symetrie, antisymetrie, tranzitivita): jaký mají význam, umět ilustrovat na grafu relace, popřípadě (alespoň intuitivně) rozpoznat u nějaké relace ze života.

1. $\mathcal{R}$ je reflexivní, když $\forall a \in A$ platí $ a\mathcal{R}a$
2. $\mathcal{R}$ je symetrická, když $\forall a, b \in A$ platí $ a\mathcal{R}b \implies b\mathcal{R}a$
3. $\mathcal{R}$ je antisymetrická, když $\forall a, b \in A$ platí $ (a\mathcal{R}b \land b\mathcal{R}a) \implies a=b$
4. $\mathcal{R}$ je tranzitivní, když $\forall a, b, c \in A$ platí $ (a\mathcal{R}b \land b\mathcal{R}c) \implies a\mathcal{R}c$

– je třeba rozumět principu, vnímat různé verze (slabá, silná), umět případně ilustrovat na nějakém jednoduchém důkazu.

Nechť $n_0 \in \mathbb{Z}$, nechť $V(n)$ je vlastnost celých čísel, která má smysl pro $n \geq n_0$. Předpokládejme, že platí:

• $V(n_0)$,
• $\forall n \geq n_0:\; V(n)\Rightarrow V(n+1)$.

Potom $V(n)$ platí pro všechna $n \geq n_0$.

Dokážeme, že $\;2^n \ge n+1\;$ pro každé $n\in\mathbb{N}_0$.

• Základ: $n=0$: $2^0=1\ge1$.
• Indukční krok: Předpokládejme $2^n\ge n+1$. Pak

$2^{n+1}=2\cdot2^n \ge 2(n+1)\ge(n+1)+1$, protože $n+1\ge1$.

Krátké vysvětlení: U silné indukce při kroku $n+1$ můžeme předpokládat, že tvrzení platí pro všechna menší čísla $n_0, n_0\!+\!1,\dots,n$. Je to, jako bys stavěl schody a u každého nového stupínku směl využít celou „platformu“ před sebou, nejen poslední schod.

Formálně: Pokud platí

• $V(n_0)$,
• $\forall n \geq n_0:\; \bigl(\forall k,\; n_0\le k\le n \Rightarrow V(k)\bigr)\;\Rightarrow\; V(n+1)$,

pak $V(n)$ platí pro všechna $n \geq n_0$.

Každé celé číslo $n\ge2$ lze rozepsat jako součin prvočísel.

Krátký slovní popis: V kroku $n+1$ můžeme předpokládat platnost tvrzení pro každé $k$ s $2\le k\le n$. Je-li $n+1$ složené, rozdělíme ho na dva menší činitele $a,b$ (to lze díky tomu že víme, že čísla která nejsou prvočíslo jsou dělitelná ne jen sama sebou a 1) a pro oba už známe rozklad (protože čísla jsou menší než $n$ a pro ty už jsme si to dokázali) → jejich součinem dostaneme rozklad i pro $n+1$.

1. Základ: $n=2$ je prvočíslo.
2. Indukční krok: Předpokládej základní tvrzení pro všechna $k$ s $2\le k\le n$.
3. Pro $n+1$:
   1. je-li $n+1$ prvočíslo, rozklad je hotov;
   2. jinak existují $a,b$ taková, že $n+1=ab$ a $2\le a,b\le n$. Podle indukčního předpokladu lze $a$ i $b$ rozložit na součin prvočísel, a tedy i $n+1$.

– základní vlastnosti homogenních lineárních rekurentních rovnic (jejich množina řešení tvoří vektorový prostor dimenze rovné řádu rovnice, takže řešení lze generovat pomocí vhodné báze), jak najít vhodnou bázi (pomocí kořenů charakteristického polynomu).

Definice: Rekurentní vztah či rekurzivní vztah pro posloupnost ${a_k}$ je libovolná rovnice typu $F(a_n, a_{n-1}, a_{n-2}, \dots, a_0) = 0$, kde $F$ je nějaká funkce. Např. podstata problému Hanojských věží se dá vyjádřit vztahem $H_n - 2 \cdot H_{n-1} - 1 = 0$.

popřípadě lineární rekurzivní rovnice řádu $k \in \mathbb{N}_0$ je libovolná rovnice ve tvaru

$a_{n+k} + c_{k-1}(n)a_{n+k-1} + \dots + c_2(n)a_{n+2} + c_1(n)a_{n+1} + c_0(n)a_n = b_n$ pro všechna $n \geq n_0$,

kde $n_0 \in \mathbb{Z}$, $c_i(n)$ pro $i = {0, \dots, k-1}$ (tzv. koeficienty rovnice) jsou nějaké funkce $\mathbb{Z} \mapsto \mathbb{R}$, přičemž $c_0(n)$ není identicky nulová funkce, a ${b_n}_{n\geq n_0}$ (tzv. pravá strana rovnice) je pevně zvolená posloupnost reálných čísel. Jestliže $b_n = 0$ pro všechna $n \geq n_0$, pak se příslušná rovnice nazývá homogenní.

• Základní vlastnosti – jejich množina řešení tvoří vektorový prostor dimenze rovné řádu rovnice, takže řešení lze generovat pomocí vhodné báze.

• Jak najít vhodnou bázi – pomocí kořenů charakteristického polynomu.

Nechť je dána lineární rekurentní rovnice

$a_{n+k} + c_{k-1}(n)a_{n+k-1} + \dots + c_1(n)a_{n+1} + c_0(n)a_n = b_n$ pro všechna $n \geq n_0$.

Jako její řešení označíme libovolnou posloupnost $\{a_n\}_{n=n_0}^{\infty}$ takovou, že po dosazení odpovídajících členů do dané rovnice dostáváme pro všechna $n$ pravdivý výrok.

Definice: Nechť je dána lineární rekurentní rovnice s konstantními koeficienty

$a_{n+k} + c_{k-1}a_{n+k-1} + \dots + c_1a_{n+1} + c_0a_n = b_n$ pro všechna $n \geq n_0$.

Její charakteristický polynom (characteristic polynomial) je definován jako polynom

$p(\lambda) = \lambda^k + c_{k-1}\lambda^{k-1} + \dots + c_1\lambda + c_0$.

Kořeny charakteristického polynomu se nazývají charakteristická čísla, popřípadě vlastní čísla dané rovnice (characteristic numbers/roots or eigenvalues).

K získání charakteristických čísel potřebujeme vyřešit rovnici $p(\lambda) = \lambda^k + c_{k-1}\lambda^{k-1} + \dots + c_1\lambda + c_0 = 0$, které se také říká charakteristická rovnice.