---- > [!definition] Definition. ([[Euler phi function]]) > The **Euler $\phi$ function** is defined by $\phi(n)=| \{ 1 \leq a \leq n, \text{ gcd}(a,n) =1\} | = |\{ x \in [n]: x \not{|} p \ \forall p \in P(n) \}|,$ > where $P(n)$ denotes the [[prime factorization|set of prime factors]] of $n$. > In words: $\phi(n)$ is the number of integers in $[n]$ [[relatively prime integers|coprime]] to $n$. > \ > An explicit formula in terms of the [[Fundamental Theorem of Arithmetic|prime factorization]] $p_{1}^{j_{1}}p_{2}^{j_{2}}\dots p_{m}^{j_{m}}$ of $n$ is $\phi(n)=\prod_{\ell=1}^{m} p_{\ell}^{j_{\ell}-1}(p_{\ell}-1).$ ^08c407 > [!justification] Derivation of Explicit Formula. First we observe that if $p^{k}$ is a power of a [[prime number]] $p$, then $\phi(p^{k})=p^{k}-p^{k-1}=p^{k-1}(p-1)$. This is because the [[divides|divisors]] of $p^{k}$ are $1,p, \dots, p^{k}$, so $\text{gcd}(p^{k},m) \neq 1$ only if $m$ is a multiple of (a power of) $p$. There are $p^{k-1}$ choices not greater than $p^{k}$. The other $p^{k}-p^{k-1}$ choices are all [[relatively prime integers|coprime]] to $p^{k}$. \ Let $p_{1}^{j_{1}}p_{2}^{j_{2}}\dots p_{m}^{j_{m}}$ be the [[prime factorization]] of $n$. Then [[greatest common divisor]]$(p_{i},p_{q})=1$ for all $i,q \in [m]$ and hence we can use the fact that $\phi$ is [[multiplicativity of Euler phi function|multiplicative]] to conclude $\begin{align} \phi(n)= & \phi\left( \prod_{\ell=1}^{m} p_{\ell}^{j_{\ell}} \right) \\ = & \left( \prod_{\ell=1}^{m} \phi(p_{\ell}^{j_{\ell}}) \right) \\ = & \prod_{\ell=1}^{m} p_{\ell}^{j_{\ell}-1}(p_{\ell}-1). \end{align}$ ^a58eb1 ---- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```