As the title indicates, I'm looking for what is known about solutions to $\varphi(\varphi(a))=\varphi(\varphi(b))$ [other than "trivial cases" for which $\varphi(a)=\varphi(b),$] where $\varphi$ is the totient function, i.e. at $n$ it is the number of positive integers at most $n$ and coprime to it.

I became interested in the question while looking at primitive roots, for which it's known that, if $n$ has any primitive roots at all, then there are $\varphi(\varphi(n))$ of them. I did find the primes $11,13$ each have $4$ primitive roots, and began to wonder if there were more examples. However due to my lack of expertise/software, I decided to ignore the assumption about $a,b$ in my question having primitive roots. Then I could find more examples, and besides that I thought such a question about the totient composed with itself might be of interest, or maybe had been investigated already somewhere. Any info appreciated.

Edit--I did a search using table for primes (and a few prime powers) below $100$ and found several examples. (Still interested in the general situation but now more in the odd prime power case.)

  • 1
    $\begingroup$ Check out the accepted answer here: math.stackexchange.com/questions/265397/… $\endgroup$ – Adrian Keister Jul 31 '19 at 17:54
  • 1
    $\begingroup$ 3 times any number that gives back half of $\varphi(a)$ as long as it's not a multiple of 3 will do. $\endgroup$ – user645636 Jul 31 '19 at 18:18
  • 1
    $\begingroup$ The condition for there to be a primitive root mod $a$ is for $a$ to be $2,4,p^n$ or $2p^n$ for an odd prime $p$ and $n\geq 1$. If you are really only interested in those $a,b$, then you can try looping over $p$ and $n$. $\endgroup$ – Wojowu Jul 31 '19 at 18:26
  • 1
    $\begingroup$ @coffeemath Sorry, I thought I had the proof, but it was flawed. I have to rethink... $\endgroup$ – Sungjin Kim Aug 1 '19 at 4:35
  • 1
    $\begingroup$ If $p=4k+1$, $q=6k+1$ are primes and $gcd(k,6)=1$, then $\phi(p-1)=\phi(q-1)$. This assumption is similar to Sophie Germain primes problem. $\endgroup$ – Sungjin Kim Aug 3 '19 at 22:14

The question on the title

$\varphi(\varphi(a))=\varphi(\varphi(b))$ with $\varphi(a)\neq \varphi(b)$. There are infinitely many solutions.

Let $a=2^{k-1}3^2$ and $b=2^{k+1}$ for $k\geq 2$.

Then we have $\varphi(a)= 2^{k-2}\cdot (3^2-3) = 2^{k-1}\cdot 3$, and $\varphi(b)=2^k$.

This yields $\varphi(a)\neq \varphi(b)$. But, we have $\varphi(\varphi(a)) = 2^{k-2}\cdot 2=2^{k-1}$ and $\varphi(\varphi(b))=2^{k-1}$.

Consider the equation (1): $\phi(p-1)=\phi(q-1)$, $p\neq q$ are primes.

Conditional Proof of Infinitude of Solutions to (1)

If there are infinitely many $k$ satisfying $p=4k+1$, $q=6k+1$ are primes, and $(6,k)=1$, we have infinitely many nontrivial pairs of primes $p$ and $q$ such that $\varphi(p-1)=\varphi(q-1)$.

Requiring both $4k+1$ and $6k+1$ be primes is similar to Sophie Germain primes problem. In which, we require both $p$ and $2p+1$ be primes.

Unconditional Proof of Infinitude of Solutions to (1)

We apply the multidimensional Selberg sieve developed in James Maynard's paper.

We say $\mathcal{H}=\{h_1,\ldots, h_k\}$ is an admissible set if there is $x_p\in\mathbb{Z}$ such that $x_p\not\equiv h_i$ mod $p$ for all $1\leq i\leq k$.

The main result in Maynard's paper is that for any admissible set with $105$ elements, there are infinitely many positive integer $n$ such that at least two of $n+h_i$'s are prime. An example of such admissible set contains $105$ integers from $0$ to $600$. Thereby, proving that there are infinitely many prime gaps of size at most $600$.

A remark in Andrew Granville's paper states that Maynard's result can be applied to any admissible $k$-tuple of linear forms. A $k$-tuple of linear forms $\{g_i x + h_i| i=1,\ldots k\}$ is said to be admissible if for any prime $p$ there is $x_p\in\mathbb{Z}$ such that $p\nmid \prod_{i=1}^k (g_i x_p + h_i)$. So, if we obtain an admissible $105$-tuple $\{g_i x + h_i| i=1,\ldots, 105\}$ of linear forms, then there exists infinitely many positive integers $n$ such that at least two of $g_i n + h_i$ are prime.

First, we obtain $1271$ integers whose $\phi$ function value is $1000000000000000$. This could be found from here. By writing a python code, it is possible to obtain $300$ integers among them such that none of them is $1$ mod $p$ for any $p\leq 107$. Then take $105$ integers $b_1,\ldots, b_{105}$ from these $300$ integers.

Then for each prime $p$, there exists $x_p\in\mathbb{Z}$ such that $x_p\not\equiv 0$ mod $p$, and $p\nmid \prod_{i\leq 105}(b_i x_p +1 )$. Let $Q=\mathrm{LCM}(\prod_{p|b_1\cdots b_{105}}p, \prod_{p<107}p)$. By Chinese remainder theorem, there is a single congruence $v_0$ mod $Q$ such that $v_0\equiv x_p$ mod $p$ for each $p|Q$. Then $(v_0,Q)=1$ and $(b_i,Qy+v_0)=1$ for any $y\in\mathbb{Z}$ and $i\leq 105$. The $k$-tuple of linear forms $\{b_iQy+b_iv_0+1|i\leq 105\}$ becomes admissible. Thus, there are infinitely many positive integers $n$ such that at least two of $b_i(Qn+v_0)+1$ are primes. Let $p=b_i(Qn+v_0)+1$ and $q=b_j(Qn+v_0)+1$ are distinct primes. Then $\phi(p-1)=\phi(b_i)\phi(Qn+v_0)= \phi(b_j) \phi(Qn+v_0) = \phi(q-1)$. Hence there are infinitely many solutions to (1).


It is possible to remove the 'computer-assisted' part of proof by invoking Kevin Ford's paper. It is also possible to extend the result to the equation $$\phi(p_1-1)=\phi(p_2-1)=\cdots = \phi(p_k-1), \ \ p_i \ \textrm{'s are distinct primes}$$ that there are infinitely many solutions to the above.


Not an answer, just a visualization:

import math
import matplotlib.pyplot as plt

def phi(x):
    result = []
    for n in x:
        amount = 0
        for k in range(1, n + 1):
            if math.gcd(n, k) == 1:
                amount += 1
    return result

x = list(range(2000))

fig,axes = plt.subplots()

graph of phi(phi(x))[1]

compare to phi(x):

enter image description here

  • 1
    $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review $\endgroup$ – The Count Aug 1 '19 at 0:05
  • 3
    $\begingroup$ @The Count I can't add the graphs to a comment, so I felt this was more appropriate. I therefore prefaced it with "not an answer, just a visualization." I thought it might be helpful to others seeking to answer the question. $\endgroup$ – Laurel Turner Aug 1 '19 at 1:16
  • 1
    $\begingroup$ That's fine. It's just my opinion. $\endgroup$ – The Count Aug 1 '19 at 1:25

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.