# Proof of the formula for Euler's totient function

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.

-
This was mentioned in one or more answers, but just to restate as a comment: the totient function is not always the product of one less than the prime factors; if a number has n multiples of the same prime factor, you use p^n - p^(n-1); in the case where n==1, you would use p - p^0 which is p - 1. –  Foon Feb 17 '13 at 17:46

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.

-
$\phi(4) \neq \phi(2) \cdot \phi(2)$ because $gcd(2,2) \neq 1$ –  Cortizol Feb 17 '13 at 15:07
@Cortizol Reworded. –  Parth Kohli Feb 17 '13 at 15:11

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)$

-
I might be wrong, but it seems to be that what OP is asking is precisely the question of why is the function multiplicative. –  tomasz Feb 17 '13 at 15:20
@tomasz, even the accepted answer did not prove it.To me, the question was when we can write $\phi(N)=\prod(b_i-1)$ where $N=\prod b_i$ –  lab bhattacharjee Feb 17 '13 at 15:23
When it comes to the accepted answer not containing the proof, you're absolutely right. But still, the question does ask about a formal proof... nevermind. I think OP slightly derailed his question himself. –  tomasz Feb 17 '13 at 15:25
In any event, you probably meant numbers divisible by $p_r$ in the penultimate line. –  tomasz Feb 17 '13 at 15:27
If $n=p_1^{\alpha_1} p_2^{\alpha_2}\dots p_k^{\alpha_k}$ then $\phi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\dots \left(1-\frac{1}{p_k}\right).$ Now, proof of multiplication is pretty "easy" –  Cortizol Feb 17 '13 at 15:28

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.$

-
Why did you \rm your math? –  tomasz Feb 17 '13 at 15:23
@tomasz Why do you italicize yours? –  Math Gems Feb 17 '13 at 15:29
Because that's the standard convention. Makes it easier to tell words and variables apart. –  tomasz Feb 17 '13 at 15:33

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.

-

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}).$$

-