Euler's totient function

Question

I read on a forum somewhere that the totient function can be calculated by finding the product of one less than each of the number's prime factors. For example, to find $\phi(30)$, you would calculate $(2-1)\times (3-1)\times (5-1) = 8$.

I can't seem to get my head round why this works and don't know what to type in to google to find a formal proof. Could someone please explain in an easy to understand way why this works.

Answer 1

By definition, $\phi(30)$ is the count of numbers less than $30$ that are co-prime to it. Also, $\phi(abc) = \phi(a)\times \phi(b)\times \phi(c)$. Note that $\phi(p)$ for all primes is always $p - 1$ because there are $p - 1$ numbers less than any given prime $p$, and all numbers less than a prime are coprime to it.

This means $\phi(30) = \phi(2\cdot 3 \cdot 5) = \phi(2) \cdot \phi(3) \cdot \phi(5) = (2-1)(3-1)(5-1) = 8$. But $\phi(60) = 16 \ne (2 - 1)(3 - 1)(5 - 1)$ so what you said is not always true. It is true only if you have an order $1$ of all the prime divisors.

Answer 2

First of all, the Totient Function is Multiplicative

If $N=\prod_{1\le r\le n}p_r^{a_i},\phi(N)=\prod_{1\le r\le n}\phi(p_r^{a_i})$ where $p_i$ are distinct primes and $a_i$ are positive integers.

Now, $p_r^{a_i}$ is relatively prime with any number which is not divisible by $p_r$

The number of numbers which are $\le p_r^{a_i}$ and are divisible by $p_r$ is $\frac{p_r^{a_i}}{p_r}=p_r^{a_i-1}$

So, $\phi(p_r^{a_i})$ is equal to $p_r^{a_i}-p_r^{a_i-1}=p_r^{a_i-1}(p_r-1)$

Answer 3

Hint $\ $ Examining the units (invertibles) in the CRT decomposition $\rm\: \Bbb Z/n \cong \Bbb Z/p^j \oplus \cdots \oplus \Bbb Z/q^k \:$ shows that $\rm\:\phi(n) = \phi(p^j)\cdots \phi(q^k),\:$ and one easily shows $\rm\:\phi(p^j) = p^j - p^{j-1} = p^{j-1}(p-1)\:$ by counting (non)units mod $\rm\,p^j;$ they are integers in $\rm[1,p^j]$ that are not coprime to $\rm\,p,\,$ hence they are precisely the $\rm\,\color{#C00}{p^{j-1}}$ multiples of $\rm\,p \le p^j,\:$ i.e. $\rm\: \color{#C00}1\cdot p,\: \color{#C00}2\cdot p,\ldots,\:\color{#C00}{p^{j-1}}\cdot p.$

Answer 4

This work only if $n$ is squarefree ($30=2\cdot3\cdot5$ is squarefree).
It can be proved that if $n=p_1^{k_1}\cdot p_2^{k_2}\cdots p_r^{k_r}$ (where $p_i$ are primes with $p_i\neq p_j \ \forall i\neq j$) then $$\phi(n)=p_1^{k_1-1}\cdot p_2^{k_2-1}\cdots p_r^{k_r-1}\cdot(p_1-1)\cdot(p_2-1)\cdots(p_r-1).$$ Therefore if $n$ is squarefree integer, meaning that $k_i=1 \ \forall \ i=1,2,\ldots r$,$$\phi(n)=(p_1-1)\cdot(p_2-1)\cdots(p_r-1).$$

See this.

Answer 5

Here is an alternative explanation that some might find easy to understand. The fraction $\phi(n)/n$ represents the probability that a random number $k$ chosen from $\{1,\ldots,n\}$ is relatively prime to $n$. This event occurs precisely when $k$ is not divisible by any of the prime factors of $n$.

For each prime $p$ dividing $n$, let $E_p$ be the event that $k$ is divisible by $p$. Note that $\mathbb P(E_p) = \tfrac1p$ (can you see why this is only accurate when $p$ divides $n$?).

The key step is using the Chinese Remainder Theorem to see that if $p_1, p_2, \ldots, p_r$ are any distinct primes dividing $n$, then the events $E_{p_1}, E_{p_2}, \ldots, E_{p_r}$ are independent: being even does not affect your chances of being divisible by $3$ (again, note that this is only precisely true because $n$ is a multiple of the LCM of those primes).

In particular we might as well choose $p_1, p_2, \ldots, p_r$ to be all the primes dividing $n$. In this case, since $\phi(n)/n$ is the probability that none of these events occur, we have

$$\frac{\phi(n)}{n} = \mathbb P(\overline{E_{p_1}} \cap \overline{E_{p_2}} \cap \cdots\cap\overline{E_{p_r}}) = \mathbb P(\overline{E_{p_1}})\mathbb P(\overline{E_{p_2}})\cdots \mathbb P(\overline{E_{p_r}}) = (1-\tfrac1{p_1})(1-\tfrac1{p_2})\cdots(1-\tfrac1{p_r}).$$