Euler's Totient Function on Odd and Even Natural Numbers

# Euler's Totient Function on Odd and Even Natural Numbers

Recall from the Euler's Totient Function page that if $n \in \mathbb{N}$ then $\phi(n)$ denotes the number of positive integers less than or equal to $n$ that are relatively prime to $n$. The function $\phi$ is called Euler's totient function.

We will now look at two very simple and nice properties of the Euler totient function.

 Theorem 1: If $n \in \mathbb{N}$ is odd then $\phi (2n) = \phi(n)$.
• Proof: Let $n \in \mathbb{N}$ be odd. Then $(2, n) = 1$, and thus:
(1)
 Theorem 2: If $n \in \mathbb{N}$ is even then $\phi (2n) = 2 \phi(n)$.
• Proof: Let $n \in \mathbb{N}$ be even. Then there exists $k, m \in \mathbb{N}$ where $m$ is odd such that:
(2)
\begin{align} \quad n = 2^k m \end{align}
• So then:
(3)
\begin{align} \quad \phi(n) = \phi(2^k) \phi(m) = (2^k - 2^{k-1}) \phi(m) = 2^{k-1} \phi(m) \quad (*) \end{align}
• Using $(*)$ with $(**)$ gives us: