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$
10
  • 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.
    Commented Nov 25, 2017 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$ Commented Nov 25, 2017 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
    Commented Nov 25, 2017 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
    Commented Nov 26, 2017 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$ Commented Nov 26, 2017 at 2:01

2 Answers 2

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

$\endgroup$
2
  • $\begingroup$ Insightful analysis---Thanks! Incidentally, Mathematica does not seem to have the equivalent of Maple's InverseTotient( ). $\endgroup$ Commented Nov 29, 2017 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$ Commented Nov 29, 2017 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.

$\endgroup$
3
  • $\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$ Commented Nov 26, 2017 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$ Commented Nov 26, 2017 at 3:26
  • $\begingroup$ $\phi(23)\phi(23)=484$, but there is no solution to $\phi(x)=484$. $\endgroup$ Commented Nov 26, 2017 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.