Alex's Notes

Eulers product formula (totient function)

2 min read

Statement

Euler's product formula

Given some with prime decomposition with distinct primes and . Then the Euler’s totient function of is

Proof

For , is coprime to . So by repeated application of Claim 1 we have Which from Claim 2 we get the result

Claim 1

Claim 1

Let be coprime then

Proof of Claim 1

As and are coprime the Chinese remainder theorem gives has a bijection where (mod ) and (mod ).

Note if if and only if and as and are coprime. Therefore

Missing \begin{array} or extra \end{array}\ \{y \in \mathbb{N} \ \vert \ 0 < x \leq n, \ gcd(x,n) = 1 \} \end{array} \mapsto \left \{b(x,y) \in \mathbb{N} \ \Bigg \vert \begin{array} \ 0 < b(x,y) \leq mn, \\ \ gcd(b(x,y),mn) = 1 \end{array} \right \}$$ and we have $$\phi(mn) = \phi(m) \phi(n).$$ ## Claim 2 >[!important] Claim 1 > >If $p$ is prime and $k \geq 1$, then >$$\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1) = p^k\left ( 1 - \frac{1}{p} \right ).$$ ## Proof of Claim 2 As $p$ is [[Prime|prime]] we know the positive divisors of $p^k$ are powers of $p^i$ for $0 \leq i \leq k$. Therefore of $gcd(p^k, x) > 1$ we know $x$ will have to be a multiple of $p$. So $x = mp$ with $m \in \mathbb{Z}_{\not = 0}$ and for $0 < x < p^k$ we have $0 < m \leq p^{k-1}$. So $$\phi(p^k) = \big \vert \left \{x \in \mathbb{N} \ \vert \ 0 < x \leq p^k, \ gcd(x,p^k) = 1 \right \} \ \big \vert = p^k - p^{k-1}$$ giving the desired result.

Graph View

Backlinks