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.
On
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)$
On
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.
On
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.$
On
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}).$$
On
As others have stated, this is not necessarily the case, but there is a general formula for the Euler function:
Given the prime factorization of some number $n = p_1^{t_1}p_2^{t_2} \cdots p_r^{t_r}$ ($n \in \mathbb{N}$), the number of relatively prime numbers to $n$ is $$ \varphi(n) = n \cdot p_1^{t_1 - 1}(p_1 - 1)p_2^{t_2 - 1}(p_2 - 2) \cdots p_r^{t_r - 1}(p_r - 1) = n \cdot \left(1 - \dfrac{1}{p_1}\right) \left(1 - \dfrac{1}{p_2}\right) \cdots \left(1 -\dfrac{1}{p_r} \right)$$
More on this formula and some of its proofs can be found at the following sites: https://en.wikipedia.org/wiki/Euler%27s_totient_function
https://faculty.etsu.edu/gardnerr/3000/notes-MR/Gerstein-6-6.pdf
https://www.math.cmu.edu/~af1p/Teaching/Combinatorics/F03/Class17.pdf
, but I think it's an interesting function, so I will walk through the proof as well.
Proof:
In this proof, we will utilize the principle of inclusion-exclusion and consider the numbers not relatively prime to $n$. So $$C = \{ k \in \{1,...,n\} : gcd(n, k) = 1\}$$ $(k < m)$ is the set of all numbers relatively prime to $n$ and we'll let $$\overline{C} = \{ k \in \{1,...,n\} : gcd(n, k) \neq 1\}$$ be the complement of $C$ meaning in consists of all numbers not relatively prime to $n$.
By the prime factorization theorem, we know $n$ has a unique prime factorization, $n = p_1^{t_1}p_2^{t_2} \cdots p_r^{t_r}$. If some natural number $k$ less than or equal $n$ is not relatively prime to $n$, then $gcd(n, k) \neq 1$ and it is a multiple of at least one prime number $p_i$ in the prime factorization of $n$ (otherwise, the number could not be less than $n$).
We will now define $$\overline{C}_i = \{k \in \{1,...,n\} : p_i \mid k\}$$ $(i \in \{1, ...,r\}$ such that $\overline{C} = \overline{C}_1 \cup \overline{C}_2 \cup \cdots \cup \overline{C}_r$. In other words, $\overline{C}_i$ is the set of all multiples of $p_i$ less than or equal to $n$, and the cardinality of this set is $\dfrac{n}{p_i}$ (we know $\dfrac{n}{p_i} \in \mathbb{N}$ because $p_i$ is in the prime factorization of $n$). Let's extend this logic to an arbitrary intersection: $$\overline{C}_{i_1} \cap \overline{C}_{i_2} \cap \cdots \cap \overline{C}_{i_k} = \{ k \in \{1, ..., n\} : p_{i_1}p_{i_2} \cdots p_{i_k} \mid n\}\: (i_j \in \{1,...,n\}, j \in \{1,...,k\}, \text{ and } k \leq r)$$ The interpretation of this intersection is the set of numbers divisible by the primes $p_{i_1}, p_{i_2}, ..., p_{i_k}$. Thus, $$| \overline{C}_{i_1} \cap \overline{C}_{i_2} \cap \cdots \cap \overline{C}_{i_k} | = \dfrac{n}{p_{i_1}p_{i_2} \cdots p_{i_k}}$$.
Now, to find the total number of natural numbers relatively prime to $n$ we'll want to subtract the total number of natural numbers not relatively prime to $n$ from the total number of natural numbers less than or equal to $n$ (which is just $n$). But to obtain the number of natural numbers not relatively prime to $n$, we cannot simply sum together the sizes of the previously defined arbitrary intersections, though, because there is some overlap between them (an integer can appear in several arbitrary intersections given that it has more than one prime number in its prime factorization). Instead, we need $|\overline{C}_1 \cup \overline{C}_2 \cup \cdots \cup \overline{C}_r|$, which we obtain through the principle of inclusion-exclusion:
$$ \begin{align*} \varphi (n) = |C| = n - |\overline{C}_1 \cup \overline{C}_2 \cup \cdots \cup \overline{C}_r | &= n - \displaystyle\sum_{k = 1}^r (-1)^{k - 1} \displaystyle\sum_{I \in {\{1, ..., r\} \choose k}} \left\lvert \bigcap_{i \in I} \overline{C}_i \right\rvert\\ &= n - \displaystyle\sum_{\emptyset \neq I \subseteq \{1,...,r\}} (-1)^{|I| - 1} \left\lvert \bigcap_{i \in I} \overline{C}_i \right\rvert\\ \text{(distribute -1)}\:\: &= n + \displaystyle\sum_{\emptyset \neq I \subseteq \{1,...,r\}} (-1)^{|I|} \left\lvert \bigcap_{i \in I} \overline{C}_i \right\rvert\\ \text{(substitute formula for size of arbitrary intersection)} &= n + \displaystyle\sum_{\emptyset \neq I \subseteq \{1,...,r\}} (-1)^{|I|} \dfrac{n}{\displaystyle\prod_{i \in I} p_i}\\ &= n \cdot (1 + \displaystyle\sum_{\emptyset \neq I \subseteq \{1,...,r\}} (-1)^{|I|} \dfrac{1}{\displaystyle\prod_{i \in I} p_i}\\ \left( \dfrac{1}{\displaystyle\prod_{i \in I} p_i} \text{is 1 for } I = \emptyset \right) \: \: &= n \cdot \displaystyle\sum_{I \subseteq \{1,...,r\}} (-1)^{|I|} \dfrac{1}{\displaystyle\prod_{i \in I} p_i}\\ &= n \left(1 - \dfrac{1}{p_1} \right)\left(1 - \dfrac{1}{p_2} \right) \cdots \left(1 - \dfrac{1}{p_r} \right)\\ \end{align*} $$
The last step uses the following identity when $x_i = -\dfrac{1}{p_i}$:
$$(1 + x_1)(1 + x_2) \cdots (1 + x_n) = \displaystyle\sum_{I \subseteq \{1,2,...,n\}} \displaystyle\prod_{i \in I} x_i$$
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.