How do I generalize the equation to be able to plug in any result for $\phi(n)=12$ and find any possible integer that works?

  • 3
    $\begingroup$ Welcome to math.SE! It would be useful to provide some more context for your problem (for example, the definition of $\mu$, which I simply assume denotes the Mobius function here). We have guidelines for asking good questions (which usually mean good answers!) in the faq, which I suggest you take a look at. $\endgroup$ – Alex Becker Jan 23 '12 at 8:24
  • 3
    $\begingroup$ I am guessing when you write $\mu$ you mean something other then the Mobius function? Perhaps you are asking for which $n$, $\phi(n)=12$ (the totient function) It we be good to clarify, since $\mu(n)$ can only take the values $-1,0,1$. (ie, not $12$) $\endgroup$ – Eric Naslund Jan 23 '12 at 8:32
  • $\begingroup$ I've taken the liberty of changing $\mu$ to $\phi$ since it seems that's what's intended. $\endgroup$ – Gerry Myerson Jan 23 '12 at 11:41
  • $\begingroup$ Possible duplicate of How to solve the equation $\phi(n) = k$? $\endgroup$ – Yanior Weg May 7 at 6:56

Assuming you mean to solve $\phi(n)=12$, you can use the formula for $\phi(n)$ that consists of factoring $n$ and then replacing one copy of every prime $p$ that occurs by $p-1$. You need such $p-1$ to divide $12$, so the only $p$ that can occur are $2,3,5,7,13$, and since occurrence with multiplicity at least $2$ also gives a factor $p$, this cannot happen for $5,7,13$. Also you need a factor $3$, which means you need one of $3,7,13$. Now it is not hard to write down the complete list of (factored) values for $n$: $13,2\times 13,2^2\times7,3\times 7,2\times3\times7,2^2\times3^2$.


Note that $\lim_{n \rightarrow \infty} \varphi(n) = \infty$, so for any $k \in \mathbb{Z}^+$, the equation $\varphi(n) = k$ has at most finitely many solutions. How to find all of them?

Solutions to $\varphi(n) = k$ for very small values of $k$ can easily be worked out by hand and probably should be as a good exercise. For instance if $\varphi(k) \leq 4$ then $n$ can only be divisible by primes $2$, $3$ and $5$, i.e., $n = 2^a 3^b 5^c$ for natural numbers $a,b,c$. Since $\varphi(5^2) = 5(5-1) = 20$, we must have $c \in \{0,1\}$. Since $\varphi(3^2) = 3(3-1) = 6$, we must have $b \in \{0,1\}$. Since $\varphi(2^4) = 2^3(2-1) = 8$, we must have $a \in \{0,1,2,3\}$, which leaves us with $2 \cdot 2 \cdot 4 = 16$ values of $n$ to check.

The above method will work for any value of $k$, but it gets very slow as $k$ grows. You could still do it for $k = 12$ -- the value you asked about -- but I wouldn't want to do it by hand even for $k = 50$, say.

In fact for even moderately large $k$ this a problem to get your computer to solve. However, you should and can do something faster than the method sketched out above. Better is to use one of the known explicit lower bounds for $\varphi$. In fact this problem came up in a research project for graduate students that I led at UGA a few years back, and the following simple lower bound was perfectly adequate for our purposes:

(1) $\varphi(n) \geq \sqrt{n}$, for $n > 6$

(I learned this originally from wikipedia, although its article on the totient function seems no longer to include this result.)

Thus, assuming $k > 4$ (we did the other case above!) so $n > 6$, using this inequality to find all values of $\varphi(n) = k$ you just need to evaluate the $\varphi$ function at all positive integers in the range $[1,k^2]$: no problem for a computer.

What if you are working with really large $k$? Well, there is in fact a much better inequality

(2) $\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}$, for $n > 2$.

This is extremely close to being sharp: if we omitted the $\frac{3}{\log \log n}$ term in the denominator, the right hand side would get ever so slightly larger, but this is large enough for the inequality to be false for infinitely many $n$. I have not given the matter any deep thought, but if anyone knows a faster way to enumerate the solution set to $\varphi(n) = k$ for large $k$ than by a brute-force search using (2) above, I would be interested to know.

  • $\begingroup$ I'm not convinced that brute-force search using (2) is any faster than (a computerized form of) the algorithm you give in the first few paragraphs. $\endgroup$ – Gerry Myerson Jan 24 '12 at 1:14

If there are more than 12 primes between n and n!, then $\phi(n!)>12$ and there is no $m>n!$ such that $\phi(m)>12$.

$n<120$ and a brute force search can be used.

  • 1
    $\begingroup$ I think you mean $\phi(m)=12$, not $\phi(m)\gt12$. But I think you need some argument to show that, under the hypotheses, there is no $m\gt n!$ such that $\phi(m)=12$. It is, I think, possible to have $m\gt n!$ with $\phi(m)\lt\phi(n!)$. Take $m$ to be the lcm of the numbers up to $k$, where $k$ is chosen as small as possible, subject to $m\gt n!$. $\endgroup$ – Gerry Myerson Jan 23 '12 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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