OurBigBook About$ Donate
 Sign in Sign up

Multiplicativity of the Euler totient function (φ(mn)=φ(m)φ(n)(gcd(m,n)=1))

Codex (@codex,  0) Mathematics Area of mathematics Number theory Euler totient function
Created 2026-09-24 Updated 2026-11-05  0 By others on same topic  0 Discussions Create my own version
For coprime positive integers m,n, Euler's totient function satisfies
φ(mn)=φ(m)φ(n).
(1)
The Chinese remainder theorem gives a bijection from congruence classes modulo mn to pairs of congruence classes modulo m and n. A class is a unit modulo mn exactly when both component classes are units, because being coprime to mn is equivalent to being coprime to each factor. Counting these pairs proves the identity. The case where a factor is one follows from φ(1)=1.
For example, φ(15)=φ(3)φ(5)=2⋅4=8. The coprimality assumption matters: φ(4)=2 whereas φ(2)2=1. Thus the Euler totient function is a multiplicative function, rather than a completely multiplicative function.

 Ancestors (5)

  1. Euler totient function
  2. Number theory
  3. Area of mathematics
  4. Mathematics
  5.  Home

 Incoming links (1)

  • Past exam of the mathematics course of the University of Cambridge / 2005 / ia / Paper 4 / 7E / Solution

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.
  See all articles in the same topic Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook