Eulerova funkce (funkce fí)

Vysvětlení Eulerovy 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).