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)

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

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

• Additionally:

(4)

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

(5)

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