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,
φ ( pm ) = (p − 1) ⋅ pm − 1,
φ ( a⋅b ) = φ(a) ⋅ φ(b). Toto tvrzení se dokazuje pomocí čínské věty o zbytcích.