Pravděpodobnostní algoritmy
Přihlásit se
Pravděpodobnostní algoritmy (4/5) · 6:06

Malá Fermatova věta Úvod do klíčového výsledku v základech teorie čísel s vizualizací pomocí korálků.

Navazuje na Test prvočíselnosti.
Bob objevil něco velmi zajímavého při výrobě barevných náušnic z korálků pro svůj obchod. Nyní mají jeho zákazníci rádi pestrost, takže se rozhodl udělat všechny možné způsoby pro každou velikost. začal velikostí 3, a zjišťoval všechny možné způsoby. Každá náušnice začala jako řetěz korálků a konce jsou spojeny tak, aby tvořili kruh. Takže, kolik je možných řetězů? S 2 barvami a 3 korálky jsou 3 způsoby, každá ze dvou barev. Tedy, 2 krát 2 krát 3 je rovno 8 možných jedinečných řetězů. Pak odečte řetězy, které mají pouze 1 barvu. Jednobarevné řetězy. Poněvadž vytváříme pouze vícebarevné náušnice. Následně je slepí všechny dohromady a vytvoří kruhy. Předpokládá, že vytvoří 6 různých náušnic, ale něco se stane: nemůže rozpoznat rozdíl mezi většinou z nich. Ukáže se, že má pouze 2 způsoby, protože každý způsob je nyní součástí skupiny s 2 identickými partnery. Všimni si, že se ti mohou vždy shodovat na základě rotací. Velikost těchto skupin musí být založena na počtu rotací, které jsou potřeba, abychom dostali původní. Nebo: kolik rotací je potřeba k dokončení cyklu. To znamená, že původní množina vícebarevných řetězů se nakonec rozdělila do skupin o velikosti 3. Bude toto pravda i pro ostatní velikosti? To by bylo vhodné, poněvadž chce vždy stejný počet každého způsobu. Zkusí to tedy se 4 korálky. Prvně vytvoří všechny možné řetezy a se 4 korálky si může vybrat ze 2 barev pro každý korálek, takže 2 krát 2 krát 2 krát 2 krát je rovno 16. Poté odstraní 2 jednobarevné řetězy, a spojí všechny zbylé v kruhy. Budou nyní tvořit skupiny o stejné velikosti? Podle všeho ne. Co se stalo? Všimni si, jak se původní množina řetězů rozdělila do variant. Pokud jsou řetězy stejného způsobu, to znamená, že můžeš jeden přeměnit na jiný jednoduše tak, že vezmeš korálky z jednoho konce, a přilepíš je na druhý konec. Je zde jedna varianta, která má pouze 2 členy. To je proto, že jsou vytvořeny z opakujících se jednotek o délce 2, takže jsou potřeba pouze 2 rotace k dokončení cyklu. Proto tato skupina obsahuje pouze 2. Nemůže je rozdělit na varianty o stejném počtu. Co velikost 5? Rozdělí se na varianty o stejném počtu? Počkat! Najednou si uvědomil, že je nemusí vytvářet, aby to zjistil. Musí to fungovat, poněvadž 5 se nemůže skládat z opakujícího se vzorce, protože 5 nemůže být rozděleno na stejné části. Je to prvočíslo. Nezáleží jakým vícebarevným řetězem začneš, vždy bude potřeba 5 rotací, nebo výměn korálků, aby se vrátil na původní. Délka cyklu každého řetězu musí být 5. Pojďme to ověřit. Prvně vytvoříme všechny možné řetězy a odstraníme oba jednobarevné řetězce. Pak řetězce rozdělíme do skupin podle toho, jestli jde o stejnou variantu, a vytvoříme jednu náušnici pro každou variantu. Všimni si, že každá náušnice se otočí přesně 5 krát, aby dokončila cyklus. Proto, pokud je všechny slepíme do kruhů, musí se rozdělit do stejně velkých skupin o 5. Pak jde ještě dál. Nyní používá pouze 2 barvy, ale uvědomil si, že tohle musí platit pro jakýkoliv počet barev. Protože jakýkoliv vícebarevný kruh s prvočíselným počtem korálků P, musí mít cyklus o délce P, poněvadž prvočísla se nemohou rozdělit na stejně velké jednotky. Pokud ale je počet korálků složené číslo, například 6, vždy bude mít určité řetězy s kratší délkou cyklu, poněvadž budou vytvořeny s opakujících se jednotek a proto vytvoří menší skupiny. A překvapivě, zrovna narazil na Malou Fermatovu větu. Méjme 'A' barev a řetězy o délce P, což bude prvočíslo. Počet možných řetězů je 'a' krát 'a' krát 'a' krát 'a', .. p krát, nebo 'a' umocněné na p. Když odstraní jednobarevné řetězy, odečte přesně 'a' řetězů, poněvadž je zde 1 každé barvy. Tím mu zbude ('a' na p) mínus 'a' řetězů. Když přilepí tyto řetězy dohromady, rozdělí se do skupin o velikosti p, poněvadž každý kruh musí mít délku cyklu velikosti p. Proto, p dělí ('a' na p) mínus 'a'. A to je vše. Můžeme toto tvrzení vyjádřit také v modulární aritmetice. Pokud vydělíš ('a' na p) číslem p, vyjde ti zbytek 'a'. Toto můžeme zapsat jako: (a na p) je kongruentní s p (modulo n). A zde narážíme na jeden ze základů teorie čísel, pouhým hraním si s korálky.
video