Diskrétní matematika (obsah)

Dokonalé číslo je takové přirozené číslo, které má stejnou hodnotu, jako součet všech jeho kladných dělitelů (kromě jeho samého). První dokonalá čísla jsou 6, 28, 496, 8128 a všechna jsou ve tvaru . Řecký matematik Euklides dokázal, že tento vzorec vrátí vždy dokonalé číslo, pokud je prvočíslo. Dosud byla nalezena pouze sudá dokonalá čísla, ale existence lichých nebyla doposud vyvrácena. Dle současných poznatků musí být liché dokonalé číslo ...

Euklidův algoritmus, který byl uveřejněn řeckým matematikem Euklidem v knize základy cca 300 let př.n.l., slouží k nalezení nejvyššího společného dělitele dvou čísel (značíme gcd – greatest common divisor), jeho rozšířená verze pak i k nalezení multiplikativní inverze čísla . Princip Mějme dvě čísla – 133 a 15, jejich nejvyšší společný dělitel nalezneme takto: Zápis Euklidova algoritmu do tabul...

Eulerova věta je zobecněním malé Fermatovy věty a říká, že kde je Eulerova funkce a . Eulerova funkce Eulerova funkce , kde , je definována jako počet čísel nesoudělných s . Platí, že . Výpočet Eulerovy funkce Číslo n rozložíme na prvočísla a dosadíme do následujícího vzorce: Důkaz Eulerovy věty Každé číslo od 0 do , které je nesoudělné s m má inverzi v a má podle Eulerovy funkce přesně invertibilních prvků, označme si je...

Faktoriál je funkce, jejímž argumentem je přirozené číslo n a výstupem je součin všech čísel menších nebo rovných (v případě je výsledkem 1). Faktoriál čísla se značí . Příklady Kód Java PHP Common Lisp /** * Vypocita faktorial cisla * @param number cislo >= 0 * @return faktorial cisla */ public static int factorial(int number) { if (number < 0) t...

Faktorizace je proces převedení čísla na součin jeho faktorů, čili rozklad na prvočísla. Rozklad je dle základní věty aritmetiky jednoznačný. Předpokládá se, že faktorizace není jednoduchý problém, na čemž je založena bezpečnost některých šifrovacích algoritmů (například RSA). Prvočíselný rozklad má také využití při výpočtu největšího společného dělitele a nejmenšího společného násobku. Obě tyto hodnoty lze ovšem lépe vypočíst pomocí Euklidova al...

Fibonacciho posloupnost je nekonečná řada čísel, ve které je prvním číslem 0, druhým 1 a každé následující číslo je definováno jako součet dvou předchozích čísel. Řada proto začíná čísly 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... Řada byla vymyšlena italským matematikem Leonardem Pisanem (Fibonacci) ve dvanáctém století jako popis pro růst počtu králíků. Na začátku se narodí 1 pár králíků. Králící se mohou množit od druhého měsíce života. Každý...

Kongruence modulo m je relace, kterou označujeme, že dvě čísla a a b mají stejný zbytek po celočíselném dělení číslem m. Jinými slovy platí, že . Zápis: a ≡ b mod(m), čteme a je kongruentní b modulo m. Příklady: Jak jste si asi všimli, tak množství kongruencí modulo m je nekonečné, proto se obvykle používá nejmenší nezáporné reziduum, což je nejmenší zbytek po dělení, který je ještě nezáporný....

Malá Fermatova věta je věta z teorie čísel, která říká, že pro každé prvočíslo p nesoudělné s číslem a platí: Důkaz Věta je speciálním případem Eulerovy věty, která byla dokázána, proto i tato věta platí. Příklad: Kolik je ? Úkrok stranou – velká Fermatova věta Na tomto místě bývá zvykem říci něco o velké Fermatově větě. Velká (také zvaná poslední) Fermatova věta z nejzapeklitější problém, který amatérský matematik 17. století Pierre de F...

Multiplikativní inverze čísla x na tělese Zp (p je prvočíslo) je takové číslo x-1, pro které platí, že x*x-1 ≡ 1. Inverze může existovat i pro čísla na Zm (m je přirozené číslo), ale není to zaručeno. Pro zjištění její hodnoty se využívá dvou postupů. Prvním je hádání, případně zkoušení všech ostatních čísel. Tento postup je efektivní pro malá p, když je hádajícím člověk (je to často vidět). Druhým postupem je rozšířený Euklidův algoritmus. Příkl...

Nejmenším společným násobkem (nsn, least common multiple - zkratka: lcm) přirozených čísel je číslo, které je násobkem každého z čísel a je minimální. Nejmenší společný násobek čísel značíme jako: Výpočet Rozklad na prvočísla Nejjednodušším způsobem výpočtu nejmenšího společného násobku čísel je tato čísla rozložit na prvočísla a z rozkladů vybrat prvočinitele v nejvyšších mocninách. Jejich následným vynásobením získáme . Příklad Ja...

Největším společným dělitelem (nsd, greatest common divisor (zkratka: gcd)) přirozených čísel je číslo, které dělí každé z těchto čísel, a je maximální. Výpočet Rozklad na prvočísla Nejjednodušším způsobem výpočtu největšího společného dělitele je rozložit jednotlivá zkoumaná čísla na prvočísla a z nich vybrat prvočinitele v maximální společné mocnině. Vynásobením prvočinitelů v příslušných mocninách získáme největšího společného dělitele ...