Euler's totient function is multiplicative
ProvedFamousTheorems.totient_multiplicative_7bEuler's totient function is multiplicative. If and are coprime natural numbers, then
where is the number of integers in coprime to .
With the value at prime powers, this gives the product formula . It follows from the Chinese remainder theorem, which gives . It is used throughout number theory, for instance in the RSA cryptosystem.
Formalization note. Mathlib's Nat.totient_mul. Nat.totient 0 = 0, and the statement holds for all coprime pairs including those involving or .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem totient_multiplicative_7b {m n : ℕ} (h : Nat.Coprime m n) : Nat.totient (m * n) = Nat.totient m * Nat.totient n := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Nat.totient_mul`. Proof here reduces to that Mathlib result.