# Euler Phi Function of Product with Prime/Corollary

## Theorem

Let $n \in \Z_{>0}$ be a positive integer.

Let $\map \phi n$ denote the Euler $\phi$ function of $n$.

Then:

$d \divides n \implies \map \phi d \divides \map \phi n$

where $d \divides n$ denotes that $d$ is a divisor of $n$.

## Proof

Let $d \divides n$.

We can write $n$ as $n = d p_1 p_2 p_3 \cdots p_r$, where $p_1, p_2, \ldots, p_r$ are all the primes (not necessarily distinct) which divide $\dfrac n d$.

Thus, repeatedly using Euler Phi Function of Product with Prime:

 $\displaystyle \map \phi d$ $\divides$ $\displaystyle \map \phi {d p_1}$ $\displaystyle \leadsto \ \$ $\displaystyle \map \phi {d p_1}$ $\divides$ $\displaystyle \map \phi {d p_1 p_2}$ $\displaystyle \leadsto \ \$ $\displaystyle \map \phi {d p_1 p_2}$ $\divides$ $\displaystyle \map \phi {d p_1 p_2 p_3}$ $\displaystyle \leadsto \ \$ $\displaystyle$ $\cdots$ $\displaystyle$ $\displaystyle \leadsto \ \$ $\displaystyle \map \phi {d p_1 p_2 \cdots p_{r - 1} }$ $\divides$ $\displaystyle \map \phi {d p_1 p_2 \cdots p_{r - 1} p_r}$

As the last expression is $\map \phi n$, the result follows from Divisor Relation on Positive Integers is Partial Ordering.

$\blacksquare$