Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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

5 Answers 5

up vote 9 down vote accepted

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.

share|improve this answer
2  
$\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)$

share|improve this answer
    
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

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.

share|improve this answer

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

share|improve this answer
    
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
3  
Because that's the standard convention. Makes it easier to tell words and variables apart. –  tomasz Feb 17 '13 at 15:33

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.