2
$\begingroup$

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:


          c=48
For $c=72$, a solutions plot looks like this:
          c=72
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.

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – M.G. Nov 25 '17 at 2:00
  • 2
    $\begingroup$ $\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)$. $\endgroup$ – Arturo Magidin Nov 25 '17 at 4:41
  • 1
    $\begingroup$ 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 $\endgroup$ – Will Jagy Nov 25 '17 at 19:59
  • 1
    $\begingroup$ Hardy and Wright, Theorem 330, the average order of $\phi(n)$ is $Cn,$ where the constant $C = 6 / \pi^2$ $\endgroup$ – Will Jagy Nov 26 '17 at 1:55
  • 1
    $\begingroup$ @WillJagy: Ah, yes, the ubiquitous $6/\pi^2$: What fraction of the integer lattice can be seen from the origin?. $\endgroup$ – Joseph O'Rourke Nov 26 '17 at 2:01
3
$\begingroup$

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. enter image description here

enter image description here

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Insightful analysis---Thanks! Incidentally, Mathematica does not seem to have the equivalent of Maple's InverseTotient( ). $\endgroup$ – Joseph O'Rourke Nov 29 '17 at 12:13
  • $\begingroup$ 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}. $\endgroup$ – Joseph O'Rourke Nov 29 '17 at 13:37
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joseph O'Rourke Nov 26 '17 at 3:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Nov 26 '17 at 3:26
  • $\begingroup$ $\phi(23)\phi(23)=484$, but there is no solution to $\phi(x)=484$. $\endgroup$ – Gerry Myerson Nov 26 '17 at 12:22

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.