Eulerova funkce

@andrea@andrea

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 nn, která jsou relativně prvočíselná k n.

Definice

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

Vlastnosti

φ(1)=1φ ( 1 ) = 1

φ(p)=p1φ ( p ) = p − 1

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

φ(ab)=φ(a)φ(b)φ ( 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.