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:

\begin{align} \quad \phi(2n) = \phi(2) \phi(n) = \phi(n) \quad \blacksquare \end{align}

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:

\begin{align} \quad n = 2^k m \end{align}

- So then:

\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}

- Additionally:

\begin{align} \quad \phi(2n) = \phi(2^{k+1}) \phi(m) = 2^{k} \phi(m) = 2(2^{k-1} \phi (m)) \quad (**) \end{align}

- Using $(*)$ with $(**)$ gives us:

\begin{align} \quad \phi (2n) = 2 \phi (n) \quad \blacksquare \end{align}