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.

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?

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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer

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

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.