Max value of x/phi(x)

hv at crypt.org hv at crypt.org
Tue Aug 31 13:22:57 CEST 2004


Alonso Del Arte <alonso.delarte at gmail.com> wrote:
:Does anyone know what the maximum possible value of x/phi(x) can be
:(where phi is Euler's totient function)? Is there a theorem in regards
:to this?
:
:From some playing around with Mathematica it seems to me that the
:value can be made as large as one wants by choosing a sufficiently
:large highly composite number, but I'm wondering if x/phi(x) is
:bounded by some property of x, such as its square root.

Since phi(x) = x prod{ 1 - 1/p_i } for all distinct primes p_i that divide x,
this is the same as asking for a lower bound on prod{ 1 - 1/p_i }.

Clearly there is no absolute lower bound, and any new minimum on that
product will first be reached when x is the product of the first k primes
for some k; I guess you can use prime density theorems to get a rough
idea of what k needs to be for a given minimum, but I'm not sure exactly
how you'd go about that.

Hugo van der Sanden





More information about the SeqFan mailing list