Euler Phi Function of Product with Prime/Corollary

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $\phi \left({n}\right)$ denote the Euler $\phi$ function of $n$.


Then:

$d \mathrel \backslash n \implies \phi \left({d}\right) \mathrel \backslash \phi \left({n}\right)$

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


Proof

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

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

\(\displaystyle \phi \left({d}\right)\) \(\backslash\) \(\displaystyle \phi \left({d p_1}\right)\)
\(\displaystyle \implies \ \ \) \(\displaystyle \phi \left({d p_1}\right)\) \(\backslash\) \(\displaystyle \phi \left({d p_1 p_2}\right)\)
\(\displaystyle \implies \ \ \) \(\displaystyle \phi \left({d p_1 p_2}\right)\) \(\backslash\) \(\displaystyle \phi \left({d p_1 p_2 p_3}\right)\)
\(\displaystyle \implies \ \ \) \(\displaystyle \) \(\cdots\) \(\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)\)

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

$\blacksquare$