Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

From this article on Sum of Euler totient function we have the following tree:

enter image description here

We know that if $p$ is prime, $\phi(p) = p - 1$, that is, $\phi(11) = 11 - 1 = 10$.

It's obvious that the above tree has a main stem and the $\phi$ branches finally reach this stem. The important number to obtain is the power of $2$ at which the $\phi$ of a number reach to the stem. This would help to determine the $\phi(n)$ for arbitrary n, specifically if it becomes possible, it would lead to prime numbers identification.

Another important note can be the reverse scan of tree. As an example, consider the number $4$ in the main stem. The numbers ${5, 13, 11}$ reach to main stem on number $4$. What if we could obtain that list for arbitrary $2^n$?

Any solution to these problems?

share|cite|improve this question
Suppose you know the 73rd iteration of $\phi$ on $n$ is $2^{100}$. How does that help you determine $\phi(n)$? How does it help you to identify primes? Note also that $\phi(2^n+1)=2^n$ if and only if $2^n+1$ is prime, so finding the numbers that reach the stem at $2^n$ is no easier than finding the Fermat primes --- which is hard. – Gerry Myerson Dec 6 '12 at 0:48
@GerryMyerson, every mathematics mystery has been solved by a conjecture and then proving, extending and correcting that.. The visual appearance of tree seems interesting so I asked to extend the idea – Mohsen Afshin Dec 6 '12 at 6:32
Maybe so, but...what does that have to do with the topic at hand? Have you made a conjecture here? I don't see one. – Gerry Myerson Dec 6 '12 at 10:27
Look at here… – Mohsen Afshin Dec 6 '12 at 11:28
Sorry, I don't see what that has to do with my first comment on this question. – Gerry Myerson Dec 6 '12 at 11:45

Factoring and computing the Euler totient function are known to be equivalent for arbitrary numbers, not just semiprimes. See the response here:

You can see some approaches and algorithms here:'s_totient_function or

This might also be useful in exploring the problem more:

Here is a calculator for up to 20 digit numbers:

You could always use a Computer Algebra System (CAS) or use WA:

Lastly, you could type things like this in WA: Table[{k, EulerPhi[k]}, {k,0,100}].

Regards - A

share|cite|improve this answer
Useful for small numbers but not for thousand digits numbers – Mohsen Afshin Dec 5 '12 at 13:35
Recall that this problem is equivalent to the Factoring problem. Does that make sense? – Amzoti Dec 5 '12 at 13:39
Nice, Amzoti! $\;+\,\uparrow\,$ – amWhy May 16 '13 at 2:04
It is, indeed, a slow night! I took a break and went to get a prescription filled/bit of shopping. I prefer to shop in "off hours" to avoid crowds! E.g., 8-9 pm-ish, my time. – amWhy May 16 '13 at 2:09

Your Answer


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.