Solutions to phi(x) phi(y) = constant

Question

Let $\phi(x)$ be Euler's totient function: The number of positive integers at most $x$ and relatively prime to $x$. Solutions to the equation $$ \phi(x) \, \phi(y) = c $$ where $c \in \mathbb{N}$ is a constant approximate a hyperbola, which is not surprising because $\phi(x) \, \phi(y) = \phi(x y )$ (when $x$ and $y$ are relatively prime). For example, for $c=48$, solutions include \begin{eqnarray} \phi(2) \, \phi(210) & = & 1 \cdot 48 \\ \phi(7) \, \phi(15) & = & 6 \cdot 8 \\ \phi(10) \, \phi(26) & = & 4 \cdot 12 \end{eqnarray} and here is a plot of solutions:

---

         

---

For $c=72$, a solutions plot looks like this:

---

         

---

My question is:

Q. Have the solutions to $\phi(x) \, \phi(y) = c$ been detailed / enumerated / thoroughly described?

Likely the answer is Yes, in which case pointers would be appreciated. In lieu of a detailed enumeration, qualitative descriptions would be useful: e.g., curves that sandwich solutions from below and from above.

---

Where this question arose. I was thinking of connecting every point $(x,y) \in \mathbb{N}^2$, gcd$(x,y)=1$, to its "number-theoretic cousins" (and then studying the properties of the resulting graph). One notion of cousin-hood might be the same $\phi(x y)$ value. Which led me to the posed Q.

Answer 1

Consider first the problem of finding the set $S_c=\{n\mid \phi(n)=c\}.$ After all, the set of $(x,y)$ with $\phi(x)\phi(y)=c$ will include all the points $(n,1)$ with $n \in S_c$ and they all lie on different hyperbolas. There are also the points $(n,2).$ The points with $\phi(x)\phi(y)=c$ are the union of the various rectangles $S_{c_1}\times S_{c_2}$ over all solution of $c_1c_2=c.$

Everything in $S_c$ has the form $n=q_1^{e_1}\cdots q_s^{e_s}p_1\cdots p_t$ where the $q_i$ are prime divisors of $c$ and the $p_j$ are distinct primes with $p_j-1\mid c.$ So it is a matter of finding all such possible $p$ and doing an organized search to obtain all the solutions. This is a rough description. For example, if $29^2 \mid c$ then one might be able to use $29^2$ or $29^3$ in the front provided that $2^27=28 \mid c. $ Otherwise, to get the $17^2$, one would need to make use of either two unequal primes such as $p=233=8\cdot 29+1$ or one such as $p=10093=12\cdot 29^2+1.$

This is implemented in Maple as InverseTotient$(c)$. If I recall correctly, in older versions it was invphi$(c)$ and for a while it missed some solutions.

For some good information on this problem check the answers to this question.

Assuming the current implementation is correct, this make some investigation easy. $c=5760=2^73^25$ is interesting. The primes $p \gt 5$ of the form $d+1$ where $d \mid 5760$ turn out to be $7,11,13,17,19,31,37,41,61,73,97,181,193,241,577,641,1153.$

Maple tells me that $S_{5760}$ has $129$ elements ranging from $5917=61\cdot 97$ to $30030=2\ 3\ 5\ 7\cdot 11 \cdot 13.$ This is a ratio of a little over $5.075$ to $1$ and give $129$ points $(n,1)$ which anchor a hyperbola among the points of $\phi(x)\phi(y)=5760.$. The points $(n,2)$ anchor another $102$ hyperbolas.

In all there are (Maple says) $3150$ points belonging to $455$ hyperbolas. Of course some of those "hyperbolas" only have two points. The outer hyperbola is $xy=97020$ with the 4 points $(2310,42),(462,210)$ and their reflections. The hyperbola $xy=30030$ has $64$ points on it (distribute the $6$ prime divisors, some to $x$ and some to $y$) so it goes from $[30030,1]$ to $[1,30030]$ while the $32$ points on $xy=60060$ run from $(30030,2)$ to $(2,30030).$ These are the rightmost and topmost points. This explains why a plot , as in the question, of all $(x,y)$ with $\phi(x)\phi(y)=5760$ looks like the two coordinate axes with fuzz on them.

Here are plots restricted to $\max(x,y) \leq 400$ and $\max(x,y) \leq 800.$ Portions of some of the rectangles $S_{c_1}\times S_{c_2}$ seem discernible. The first has $1500$ points and the second $2718.$ The second thus has a little over $85\%$ of the points. I leave it to you to decide how much it looks like a hyperbola.

The graph for $\phi(x)\phi(y)=5760^2$ would include a square of $129^2$ points with corners $(5917,5917)$ and $(30030,30030).$ These are the points with $\phi(x)=\phi(y)=5760.$ This alone gives hyperbolas $xy=m_1$ and $xy=m_2$ with $\frac{m_1}{m_2} \sim 5.075^2 \sim 25.76.$ It appears that there $6025$ hyperbolas intersecting points of that square. There are $6750$ points $(n,1)$ with $\phi(n)=5760^2.$ Of them, $805$ belong to hyperbolas already mentioned and the rest do not.

The outer "hyperbola" is $xy=30030^2$ with the one point $(30030,30030).$ The inner "hyperbola" is $xy=p=3317761=2^{14}3^45^2+1$ with the two points $(p,1)$ and $(1,p).$

Answer 2

Some observations to make.

For a prime $p$, let $q=\phi(p)$. For any solution of $\phi(x)\phi(y)=c$ and for any $p$ dividing $xy$ one has $q$ dividing $c$. Sometimes $p$ also divides $c$ when $q$ does.

If $x,y$ is a solution then so is $y,x$ also a solution. If $xy$ is odd , then $2x,y$ is another solution, as are obvious variations. Indeed, if there is a "core" of solution to $c/2^k$, then they can be used by multiplication by $2^k$ or $2^{k+1}$ to form some solutions for $c$, with additional ones possibly given by multiplying by Fermat primes.

Some even numbers like 14 are not values of $\phi$. Because $7$ and other large odd numbers are also not values, one cannot choose $c=14$ and expect a solution. However, there may be other values which are not $\phi$ values but may be values for $c$ and have solutions for the equation above. This might be of interest to the number theory community.

Gerhard "Call Them Rectangular Nontotients, Maybe?" Paseman, 2017.11.25.