Definice

ϕ: ℕ → ℕ
Eulerova funkce ϕ(n), kde n ∈ ℕ a n > 1, je definována jako 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^m ) = (p − 1) ⋅ p^{m − 1},
φ ( a⋅b ) = φ(a) ⋅ φ(b). Toto tvrzení se dokazuje pomocí čínské věty o zbytcích.