 Totient divisibility along divisors

ID: totient-divisibility-along-divisors

Write

n = \prod p^{a_{p}}

and

d = \prod p^{b_{p}}

, with

0 \leq b_{p} \leq a_{p}

φ (n) / φ (d)

from each prime: it is

p^{a_{p} - b_{p}}

when

b_{p} > 0

, and

p^{a_{p} - 1} (p - 1)

when

b_{p} = 0 < a_{p}

. Multiplying proves the divisibility assertion, including

d = 1

with

φ (1) = 1

 New to topics? Read the docs here!