Malá Fermatova věta

Bob objevil něco velmi zajímavého při výrobě barevných náušnic z korálků pro svůj obchod. Jeho zákazníci mají 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ězec korálků a konce jsou spojeny tak, aby tvořily kruh. Nejprve zjistěme, kolik takových různých řetězců existuje? Se 2 barvami a 3 korálky jsou 3 způsoby, každá ze dvou barev. Tedy, 2 krát 2 krát 2 je rovno 8 možných jedinečných řetězců. Pak odečte řetězce, které mají pouze 1 barvu. Jednobarevné řetězce. 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 stalo: nemůže rozpoznat rozdíl mezi většinou z nich. Ve skutečnosti existují pouze 2 způsoby, protože každý způsob je nyní součástí skupiny se dvěma identickými partnery. Všimněte si, že se tito partneři liší pouze rotací. Velikost těchto skupin musí být založena na počtu rotací, které jsou potřeba, abychom dostali původní náušnici. Nebo jinak: kolik rotací je potřeba k dokončení cyklu? To znamená, že původní množina vícebarevných řetězců se nakonec rozdělila do skupin o velikosti 3. Bude to 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. Nejprve vytvoří všechny možné řetězce 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 je rovno 16. Poté odstraní 2 jednobarevné řetězce, a spojí všechny zbylé v kruhy. Budou nyní tvořit skupiny o stejné velikosti? Podle všeho ne. Co se stalo? Všimněte si, jak se původní množina řetězců rozdělila do variant. Pokud jsou řetězce stejného způsobu, to znamená, že můžeme jeden přeměnit na jiný jednoduše tak, že vezmete korálky z jednoho konce, a přilepíte 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ůžeme 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 jsem 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čneme, 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ězce 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šimněte si, že každá náušnice se otočí přesně pětkrát, aby dokončila cyklus. Pokud je tedy všechny slepíme do kruhů, musí se rozdělit do stejně velkých skupin po pěti. Bob jde ještě o krok 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ězce s kratší délkou cyklu, poněvadž budou vytvořeny z opakujících se jednotek, a proto vytvoří menší skupiny. Takto zrovna narazil na Malou Fermatovu větu. Méjme 'A' barev a řetězce o délce P, což bude prvočíslo. Počet možných řetězců je 'a' krát 'a' krát 'a' krát 'a',... p krát, neboli 'a' umocněné na p. Když odstraní jednobarevné řetězce, odečte přesně 'a' řetězců, poněvadž je zde 1 každé barvy. Tím mu zbude ('a' na p) minus 'a' řetězů. Když přilepí tyto řetězy dohromady, rozdělí se do skupin o velikosti p, protože každý kruh musí mít délku cyklu velikosti p. Proto p dělí ('a' na p) minus 'a'. A to je vše. Můžeme toto tvrzení vyjádřit také v modulární aritmetice. Pokud vydělíte ('a' na p) číslem p, vyjde nám zbytek 'a'. Toto můžeme zapsat jako: (a na p) je shodné s a (modulo p). A zde narážíme na jeden ze základů teorie čísel, i když jsme si jen hráli s korálky.