Euler Phi Function of Product with Prime

Theorem

Let $p$ be prime and $n \in \Z: n \ge 1$.

Then: $\phi \left({p n}\right) = \begin{cases} \left({p - 1}\right) \phi \left({n}\right) & : p \nmid n \\ p \phi \left({n}\right) & : p \backslash n \end{cases}$

Thus for all $n \ge 1$ and for any prime $p$, we have that $\phi \left({n}\right)$ divides $\phi \left({p n}\right)$.

Corollary

If $d \backslash n$ then $\phi \left({d}\right) \backslash \phi \left({n}\right)$.

Proof

• First suppose that $p \nmid n$.

Then by Prime Not Divisor then Coprime, $p \perp n$.

So by Euler Phi Function is Multiplicative, $\phi \left({p n}\right) = \phi \left({p}\right) \phi \left({n}\right)$.

It follows from Euler Phi Function of a Prime that $\phi \left({p n}\right) = \left({p - 1}\right) \phi \left({n}\right)$.

• Now suppose that $p \backslash n$.

Then $n = p^k m$ for some $k, m \in \Z: k, m \ge 1$ such that $p \perp m$.

Then:

	\(\displaystyle \)	\(\displaystyle \phi \left({p n}\right)\)	\(=\)	\(\displaystyle \phi \left({p^{k+1} m}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \phi \left({p^{k+1} }\right) \phi \left({m}\right)\)	\(\displaystyle \)	Euler Phi Function is Multiplicative
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p^{k+1} \left({1 - \frac 1 p}\right) \phi \left({m}\right)\)	\(\displaystyle \)	Euler Phi Function of a Prime

At the same time:

	\(\displaystyle \)	\(\displaystyle p \phi \left({n}\right)\)	\(=\)	\(\displaystyle p \phi \left({p^k m}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p \phi \left({p^k}\right) \phi \left({m}\right)\)	\(\displaystyle \)	Euler Phi Function is Multiplicative
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p p^k \left({1 - \frac 1 p}\right) \phi \left({m}\right)\)	\(\displaystyle \)	Euler Phi Function of a Prime
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p^{k+1} \left({1 - \frac 1 p}\right) \phi \left({m}\right)\)	\(\displaystyle \)

$\blacksquare$

Proof of Corollary

Let $d \backslash 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 $n$.

Thus, repeatedly using the above result:

	\(\displaystyle \)	\(\displaystyle \phi \left({d}\right)\)	\(\backslash\)	\(\displaystyle \phi \left({d p_1}\right)\)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle \phi \left({d p_1}\right)\)	\(\backslash\)	\(\displaystyle \phi \left({d p_1 p_2}\right)\)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle \phi \left({d p_1 p_2}\right)\)	\(\backslash\)	\(\displaystyle \phi \left({d p_1 p_2 p_3}\right)\)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle \)	\(\cdots\)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle \phi \left({d p_1 p_2 \cdots p_{r-1} }\right)\)	\(\backslash\)	\(\displaystyle \phi \left({d p_1 p_2 \cdots p_{r-1} p_r}\right)\)	\(\displaystyle \)

As the last expression is $\phi \left({n}\right)$, the result follows from Divides is Partial Ordering on Positive Integers.

$\blacksquare$