proof that Euler φ function is multiplicative

Suppose that t=mn where m,n are coprimeMathworldPlanetmathPlanetmath. The Chinese remainder theoremMathworldPlanetmathPlanetmathPlanetmath ( states that gcd(a,t)=1 if and only if gcd(a,m)=1 and gcd(a,n)=1.

In other words, there is a bijectiveMathworldPlanetmathPlanetmath correspondence between these two sets:

  • {a:a1(modt)}

  • {a:a1(modm) and a1(modn)}

Now the number of positive integers not greater than t and coprime with t is precisely φ(t), but it is also the number of pairs (u,v), where u not greater than m and coprime with m, and v not greater than n and coprime with n. Thus, φ(mn)=φ(m)φ(n).

Title proof that Euler φ function is multiplicative
Canonical name ProofThatEulervarphiFunctionIsMultiplicative
Date of creation 2013-03-22 15:03:40
Last modified on 2013-03-22 15:03:40
Owner Wkbj79 (1863)
Last modified by Wkbj79 (1863)
Numerical id 12
Author Wkbj79 (1863)
Entry type Proof
Classification msc 11A25
Related topic EulerPhiFunction
Related topic MultiplicativeFunction
Related topic EulerPhifunction