Loading...

​​01. Vlastnosti celých čísel, euklidův algoritmus, binární relace, matematická indukce, rekurzivní vztahy

​​Vlastnosti celých čísel

• ​​celá čísla ​​$Z$​ se skládají z přirozených čísel, nuly a záporných celých čísel

• ​​množina je uzavřena na operaci sčítání, odčítání a násobení

​​Dělitelnost

​​Definice: Nechť ​​$a,b \in Z$​. Řekneme, že ​​$a$​ dělí ​​$b$​, značeno ​​$a|b$​, jestliže existuje ​​$k \in Z$​ takové, že ​​$b=a \cdot k$​. V takovém případě říkáme, že ​​$a$​ je faktor ​​$b$​ a že ​​$b$​ je násobek ​​$a$​. Také říkáme, že ​​$b$​ je dělitelné číslem ​​$a$​. Pokud toto není pravda, tak píšeme ​​ ​a ⫮ b.

• ​​Číslo ​​$d \in N$​ je společný dělitel (common divisor) čísel ​​$a,b$​, jestliže ​​$d\mid a$​ a ​​$d \mid b$​.

• ​​největší společný dělitel (greatest common divisor), značeno ​​$gcd(a, b)$​ je největší prvek množiny jejich společných dělitelů, pokud je alespoň jedno z ​​$a,b$​ nenulové.

• ​​Číslo ​​$d \in N$​ je společný násobek (common multiple) čísel a, b, jestliže a|d a b|d.

• ​​nejmenší společný násobek (least common multiple), značeno lcm(a, b) je nejmenší prvek množiny jejich společných násobků, pokud jsou obě a,b nenulové.

• ​​​​$lcm(a, 0) = lcm(0, b) = 0$​

• ​​​​$gcd(0, 0) = 0$​

• ​​​​ ​​​$lcm(a, b) \cdot gcd(a, b) = |a| \cdot |b|$​

• ​​čísla ​​$a,b \in Z$​ jsou nesoudělná, jestliže ​​$gcd(a,b)=1$​

​​Prvočíslo

• ​​je přirozené číslo, které je beze zbytku dělitelné právě dvěma různými přirozenými čísly, a to číslem jedna a sebou samým (tedy 1 není prvočíslo)

• ​​Přirozená čísla různá od jedné, která nejsou prvočísla, se nazývají složená čísla.

​​Eukleidův algoritmus

​​Lze jím vypočítat největšího společného dělitele dvou přirozených čísel.

• ​​vychází z lemmatu: Nechť ​​$a,b \in N$​, nechť ​​$q,r \in N_0$​ splňují ​​$a = q \cdot b + r$​ a ​​$0 \leq r < b$​. Pak platí následující: ​​$d \in N$​ je společný dělitel ​​$a,b$​ právě tehdy, když je to společný dělitel ​​$b,r$​.

• ​​​​$gcd(a, b) = gcd(b, r)$​

• ​​opakovaně hledáme ​​$gcd$​ pro dvojici ​​$b, r$​ místo ​​$a,b$​

​​Binární relace

​​Definice: Nechť ​​$A,B$​ jsou množiny. Libovolná podmnožina ​​$R \subseteq A \times B$​ se nazývá relace z ​​$A$​ do ​​$B$​. Jestliže  ​​$(a, b) \in R$​, pak to značíme ​​$aRb$​ a řekneme, že a je v relaci s b vzhledem k R. Jestliže (a, b) / ∈ R, pak řekneme, že a není v relaci s b vzhledem k R.

​​Druhy relací

• ​​R je reflexivní, jestliže pro všechna a ∈ A platí aRa. např. “je stejný”

• ​​R je symetrická, jestliže pro všechna a, b ∈ A platí (aRb ⇒ bRa). “je sourozencem”

• ​​R je antisymetrická, jestliže pro všechna a, b ∈ A platí ([aRb ∧ bRa] ⇒ a = b). “<=”

• ​​R je tranzitivní, jestliže pro všechna a, b, c ∈ A platí ([aRb ∧ bRc] ⇒ aRc). “je vyšší; A je vyšší než B, B je vyšší než C ⇒ A je vyšší než C”

​​Ekvivalence

​​Definice: Nechť R je relace na nějaké množině A. Řekneme, že R je ekvivalence, jestliže je reflexivní, symetrická a tranzitivní.

​​0.2.1.1 Třída ekvivalence

​​Každá ekvivalence rozdělí množinu A na systém disjunktních množin, které pak nazýváme třídy ekvivalence.

​​Definice: Nechť R je relace ekvivalence na nějaké množině A. Pro a ∈ A definujeme třídu ekvivalence prvku a (equivalence class of a) vzhledem k R jako [a] R = {b ∈ A; aRb}.

​​Částečné uspořádání

​​Definice: Nechť R je relace na nějaké množině A. Řekneme, že R je částečné uspořádání, jestliže je reflexivní, antisymetrická a tranzitivní. V tom případě řekneme, že dvojice (A, R) je částečně uspořádaná množina.

​​Hasseův diagram

• ​​Uspořádané množiny můžeme zakreslit pomocí Hasseova diagramu.

• ​​vrcholy představují prvky množiny

• ​​hrana mezi vrcholy (a, b) nám říká, že a < b a zároveň neexistuje c takové, že a < c < b. Tedy mezi prvky a a b už žádný jiný prvek není. Přitom musí platit, že v grafu je vrchol a níže než vrchol b.

​​ Počítání modulo

• ​​Definice Nechť ​​$n \in N$​. Řekneme, že čísla ​​$a,b \in Z$​ jsou kongruentní modulo n, značeno a ≡ b (mod n), jestliže n|(a−b).

​​Nechť n ∈ N. Pro čísla a, b ∈ Z jsou následující podmínky ekvivalentní:

• ​​​​$a\equiv b (\mod n)$​

• ​​existuje ​​$k \in Z$​ takové, že ​​$a=b+k \cdot n$​

• ​​​​$a \mod n = b \mod n$​, tj. jsou si rovny zbytky po dělení číslem n.

​​Vlastnosti

​​Nechť ​​$n \in N$​, uvažujme ​​$a, b, u, v \in Z$​ takové, že ​​$a \equiv u \mod n$​ a ​​$b \equiv v \mod n$​:

• ​​​​$a+b \equiv u +v \mod n$​

• ​​​​$a-b \equiv u -v \mod n$​