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

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.

• Have the solutions of $\phi(x)=c$ been detailed? Since $\phi$ is multiplicative only on coprime numbers, your question appears to be more general than that, but perhaps only superficially so, since it boils down to the divisors of $c$. In other words, one only needs to study $\phi(x)=d$ for $d|c$. – M.G. Nov 25 '17 at 2:00
• $\phi(xy) = \phi(x)\phi(y)$ holds when $\gcd(x,y)=1$, and a few other instances; e.g., $\phi(4)\neq\phi(2)\phi(2)$. – Arturo Magidin Nov 25 '17 at 4:41
• It is also true that $\phi(x)$ resembles $x.$ Lower bounds are achieved at the primorial numbers, see math.stackexchange.com/questions/301837/… and my other answer there – Will Jagy Nov 25 '17 at 19:59
• Hardy and Wright, Theorem 330, the average order of $\phi(n)$ is $Cn,$ where the constant $C = 6 / \pi^2$ – Will Jagy Nov 26 '17 at 1:55
• @WillJagy: Ah, yes, the ubiquitous $6/\pi^2$: What fraction of the integer lattice can be seen from the origin?. – Joseph O'Rourke Nov 26 '17 at 2:01

## 2 Answers

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

• Insightful analysis---Thanks! Incidentally, Mathematica does not seem to have the equivalent of Maple's InverseTotient( ). – Joseph O'Rourke Nov 29 '17 at 12:13
• Turns out Mathematica does have InverseTotient, but it is undocumented and not immediately visible (thanks to Michael E2): e.g., Reduce`EulerPhiInverse[48] returns {65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210}. – Joseph O'Rourke Nov 29 '17 at 13:37

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.

• Maybe just understanding for which $c$ is there is at least one solution, would be an advance. E.g., neither $\phi(x) \, \phi(y) = 14$ (your example) nor $=26$ have solutions, despite $c$'s evenness. – Joseph O'Rourke Nov 26 '17 at 3:06
• It may be that the parameters are identical, that there is a solution to $\phi(x)\phi(y)=c$ implies that there is a solution to $\phi(x)=c$. But I don't see how to show that. Gerhard "Can Show The Simpler Direction" Paseman, 2017.11.25. – Gerhard Paseman Nov 26 '17 at 3:26
• $\phi(23)\phi(23)=484$, but there is no solution to $\phi(x)=484$. – Gerry Myerson Nov 26 '17 at 12:22