# Solutions to $\varphi(\varphi(a))=\varphi(\varphi(b))$

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

• Check out the accepted answer here: math.stackexchange.com/questions/265397/… – Adrian Keister Jul 31 '19 at 17:54
• 3 times any number that gives back half of $\varphi(a)$ as long as it's not a multiple of 3 will do. – user645636 Jul 31 '19 at 18:18
• 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$. – Wojowu Jul 31 '19 at 18:26
• @coffeemath Sorry, I thought I had the proof, but it was flawed. I have to rethink... – Sungjin Kim Aug 1 '19 at 4:35
• 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. – 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).

Remark

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
result.append(amount)
return result

x = list(range(2000))

fig,axes = plt.subplots()
plt.scatter(x,phi(phi(x)),s=1)
fig.suptitle('phi(phi(x))')
plt.show()


compare to phi(x):

• 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 – The Count Aug 1 '19 at 0:05
• @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. – Laurel Turner Aug 1 '19 at 1:16
• That's fine. It's just my opinion. – The Count Aug 1 '19 at 1:25