# Euler function - all values of n give $\phi(n)=10$

How do I find the equation that will give me the result for $\phi (n)=10$ and find any possible values of $n$ that works?

• Why do you believe there is an equation that will do this? – Chris Eagle Jan 5 '13 at 13:59
• I think there is no formula to get that (as Chris Eagle says). However, you can just look at the graph en.wikipedia.org/wiki/File:EulerPhi.svg to get what you want – Alan Simonin Jan 5 '13 at 14:04
• actually I think that there may be .. not sure – Anna Jan 5 '13 at 14:04
• @AlanSimonin thank you but I dont need just the values but also a way... – Anna Jan 5 '13 at 14:05
• Well you can use the properties of the Euler's totient function : if $n$ is prime, then $\phi (n) = n-1$, so $n=11$. Then you can use the fact that if $n=p_1^{k_1} \cdots p_n^{k_n}$ then $\phi(n) = \phi(p_1^{k_1}) \cdots \phi(p_n^{k_n})$ and try the values of the divisors of 10... – Alan Simonin Jan 5 '13 at 14:13

$$\phi(n)=n\prod_{p|n}(1-\cfrac 1 p) =\cfrac n {p_1p_2p_3p_4\dots}(p_1-1)(p_2-1)(p_3-1)(p_4-1) \dots$$
(for the distinct prime factors $p_i$ of $n$).
Now note that the fraction on the right hand side of the expression is an integer, so that $(p_i-1)$ must be a factor of 10, and this restricts the options. Then also observe that you need a factor 5 from somewhere, but if n were a multiple of 5 you'd get $\phi(n)$ being a multiple of 4 - so where is the 5 to come from? That should restrict the options enough to work things out pretty easily.
Note that if $n=\prod_p p^{e_p}$ then $$\phi(n)=\prod_{e_p\ge1}(p-1)p^{e_p-1}.$$ Each factor must be $\le 10$ and in fact a divisor of $10$. This excludes all primes $p>11$. Also, $p=7$ is excluded ($p-1$ is a multiple of $3$), and so is $p=5$ ($p-1$ is a multiple of $4$). Since at least one factor must be a multiple of $5$, we conclude therefore that $p=11$ occurs. To make its contribution $\le 10$, we must have $e_{11}=1$; but that already makes $(11-1)11^0=10$, so all other factors must equal $1$. Thus $3$ cannot occur as it would contribute at least $3-1=2$. However, $2$ can occur, but only with $e_2=1$. Thus we find that $\phi(n)=10$ implies $$n=11\text{ or }n=22.$$