Eulerova funkce

Eulerova funkce (také Eulerova funkce totient, Eulerův totient), je důležitá aritmetická funkce v teorii čísel. Značí se jako φ(n) nebo ϕ(n) a jejím úkolem je spočítat počet kladných celých čísel menších nebo rovných $n$, která jsou relativně prvočíselná k n.

Definice

Funkce $ϕ: ℕ → ℕ$, kde $n ∈ ℕ$ Vrací nám počet kladných celých čísel, která jsou v intervalu $(1, n-1)$ a jsou nesoudělná s n.

Vlastnosti

$φ ( 1 ) = 1$

$φ ( p ) = p − 1$

$φ ( p^𝑎 ) = (p − 1) ⋅ p^{𝑎 − 1} = p^𝑎 - p^{𝑎-1}$

$φ ( a⋅b ) = φ(a) ⋅ φ(b)$.

Toto tvrzení se dokazuje pomocí čínské věty o zbytcích.

Využití

Má důležité uplatnění v kryptografii, zejména v asymetrických šifrovacích algoritmech, jako je RSA.