Eulerova funkce

Euler pokračoval ve zkoumání vlastností čísel. Zvláště se věnoval rozložení prvočísel. Definoval jednu důležitou funkci, které se říká "funkce Fí". Tato funkce je mírou rozpadnutelnosti čísla. Vezmeme-li například číslo 'N', tak funkce vrátí počet celých čísel, které jsou menší nebo rovna 'N' a nemají společného prvočíselného dělitele s 'N'. Pokud budeme chtít vědět, kolik je například Fí(8), tak se podíváme na všechny hodnoty čísel od 1 do 8 a spočítáme počet celých čísel, se kterými nemá 8 společného dělitele většího než 1. Vynecháme 6, neboť 6 a 8 mají společného dělitele 2, ale 1, 3, 5 a 7 se započítají, protože společným dělitelem je pouze 1. Proto platí Fí(8) = 4. Zajímavé je, že výpočet funkce Fí je složitý až na jediný případ. Podívejte se na tento graf, kde jsou vyneseny hodnoty Fí pro celá čísla od 1 do 1000. Vidíte nějaký předvídatelný vzor? Rovná čára bodů kolem vrcholu představuje všechna prvočísla. Prvočísla nemají žádného společného dělitele, kromě čísla 1, takže Fí jakéhokoliv prvočísla 'p' je (p mínus 1). Abychom spočetli Fí(7), což je prvočíslo, tak spočítáme všechna celá čísla kromě 7, protože žádné nemá společného prvočíselného dělitele se 7. Fí(7) = 6. Takže když máte najít Fí(21 377), což je prvočíslo, tak pouze odečtete 1 a máte výsledek: 21 376. Fí jakéhokoliv prvočísla je jednoduché spočítat. To má zajímavé důsledky díky faktu, že funkce Fí je 'multiplikativní'. To znamená, že Fí(A krát B) = Fí(A) krát Fí(B). Pokud víme, že nějaké číslo 'N' je součinem dvou prvočísel P1 a P2, tak Fí(N) je jen součin hodnot Fí daných prvočísel neboli (P1 mínus 1) krát (P2 mínus 1).