_Posted on April 19, 2024_ _Updated on November 02, 2024_ Euler's Totient Function, defined as $\varphi: \mathbb{Z^+} \rightarrow \mathbb{N}$ maps a positive integer $n$ to the number of positive integers through $n$ that are coprime to $n$. For $p$ prime, $\varphi(p)$ is clearly $p -1$, since no integers less than $p$ contain $p$ in their [[Fundamental Theorem of Arithmetic|unique factorization]]. Now, we consider the more general case of $\varphi(p^k)$ for $k \in \mathbb{Z^+}$: By the [[Fundamental Theorem of Arithmetic|FTA]], the divisors of $p^k$ less than $p^k$ are those containing $p$ in thier prime factorization. Therefore, the integers coprime to $p^k$ are all those integers which do _not_ contain $p$ in thier prime factorization. So, to compute the number of integers coprime to $p^k$, we take the $p^k$, the total number of positive integers through $p^k$ and subtract the number of multiples of $p$ less than $p^k$. The multiples of $p$ up to $p^k$ can be written as $pm$ for $0 < m \leq p^{k-1}$. It follows that there are $p^{k-1}$ multiples of $p$ up to $p^k$, so that $\varphi(p^k) = p^k - p^{k-1} = p^{k}(1 - \frac{1}{p})$. Towards deriving a formula for the general case $\varphi(n)$, we will prove the following theorem: > [!theorem] **Multiplicativity of Euler's Totient Function:** _If $m$ and $n$ are coprime, then $\varphi(mn)=\varphi(m)\varphi(n)$._ (also it is not completely multiplicative) Proof: #TODO (come up with proof myself!! ) Using this, we can derive a formula for all $\varphi(n)$. Recall (from [[Prime Exponent Theorem for LCM and GCD]]) that $n$ can be expressed as $\Pi_{k=1}^{\infty}p_k^{m_k}$ and so $\displaystyle \varphi(n) = \varphi(\Pi_{k=1}^{\infty}p_k^{m_k}) = \Pi_{k=1}^{\infty}\varphi(p_k^{m_k}) = \Pi_{k=1}^{\infty}p_k^{m_k}(1 - \frac{1}{p_k^{m_k}}) = n * \Pi_{k=1}^{\infty}(1 - \frac{1}{p_k})$