6
$\begingroup$

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

$\endgroup$
16
  • 1
    $\begingroup$ Check out the accepted answer here: math.stackexchange.com/questions/265397/… $\endgroup$ Commented Jul 31, 2019 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
    Commented Jul 31, 2019 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
    Commented Jul 31, 2019 at 18:26
  • 1
    $\begingroup$ @coffeemath Sorry, I thought I had the proof, but it was flawed. I have to rethink... $\endgroup$ Commented Aug 1, 2019 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$ Commented Aug 3, 2019 at 22:14

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

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

compare to phi(x):

enter image description here

$\endgroup$
3
  • 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
    Commented Aug 1, 2019 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$ Commented Aug 1, 2019 at 1:16
  • 1
    $\begingroup$ That's fine. It's just my opinion. $\endgroup$
    – The Count
    Commented Aug 1, 2019 at 1:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .