Euler phi at a product


If the positive greatest common divisorMathworldPlanetmathPlanetmath of the integers a and b is d, then

φ(ab)=φ(a)φ(b)dφ(d).

Proof.  Using the positive prime factorsMathworldPlanetmathPlanetmath p, the right hand side of the asserted equation is

dapap-1pbpbp-1pdpa,pbp-1p =abpa,pbp-1ppa,pbp-1ppb,pap-1ppb,pap-1ppa,pbp-1p
=abpapbp-1p=abpabp-1p=φ(ab),

Q.E.D.

Title Euler phi at a productPlanetmathPlanetmath
Canonical name EulerPhiAtAProduct
Date of creation 2014-02-18 14:02:24
Last modified on 2014-02-18 14:02:24
Owner pahio (2872)
Last modified by pahio (2872)
Numerical id 6
Author pahio (2872)
Entry type Theorem
Classification msc 11A25
Classification msc 11-00
Related topic EulerPhifunction
Related topic DivisibilityByPrimeNumber