How to find a number $n$ such that $\frac{n}{\phi(n)} > 10$?

Question

How to find a number $n$ such that $$\frac{n}{\phi(n)} > 10,$$ where $\phi(n)$ denotes the Euler's phi function?

I was trying to find the smallest one, so was keeping each prime once. I tried with the number $$n = 2\times3\times5\times7\times11\times13\times17\times19$$ and some more numbers, but not working. Need some help!

Note that $$\phi(n) = n \times \prod_{p} \left(1-\frac1p \right) = n \times \prod_{p} \left(\frac{p-1}{p} \right)$$ hence $$\frac{n}{\phi(n)} = \prod_{p} \left(\frac{p}{p-1} \right).$$

Answer 1

The solution in the comments, done by several people, is saying that, with $f(n)=\frac{n}{\phi(n)}$ we have $$ f(p_{55}\#)=10.003719732091010383325131639818913973 $$ where $$ p_{55}\#=16516447045902521732188973253623425320896207954043566485360902980990824644545340710198976591011245999110 $$ and that this is the smallest such integer with $f(n)>10$.

More information is found in the following post, by considering $1/f(n)$:

$\frac{\phi(m)}{m}$ is dense in $[0,1]$

Answer 2

The other answer covers the $x=10$ case, but I'll show that if you want $\frac n{\varphi(n)}>x$ for any real number $x$ that is always possible.

I'm going to use the notation

$$f(x)\sim g(x)\iff \lim_{x\to\infty}\frac{f(x)}{g(x)}=1$$

It is unfortunately not standard. I lifted it from "An Introduction to the Theory of Numbers" by Hardy and Wright.

Mertens' third theorem tells us that

$$\prod_{p\leq a}1-\frac 1 p \sim \frac{e^{-\gamma}}{\ln(a)}$$

For a primorial $n$ we then have

$$\frac n{\varphi(n)}\sim\ln(a)e^\gamma$$

Since we want the quantity on the LHS to be greater than $x$ we need to $a$ to be approximately

$$a \sim\exp\left(e^{-\gamma}x\right)$$

This increases exponentially in $x$ which explains why the answer to your question is so big. For $x=10$ that gets you $a\approx 274$, close to the true value of 257.

Answer 3

A more "manual" approach, considering $$\log{(1+x)}\geq \frac{x}{1+x}, \forall x>-1$$ We can build an estimation as per the following: $$\frac{n}{\varphi(n)}= \prod\limits_{p}\frac{p}{p-1}= \prod\limits_{p}\left(1+\frac{1}{p-1}\right)\geq \prod\limits_{p} e^{\frac{\frac{1}{p-1}}{1+\frac{1}{p-1}}}=\\ \prod\limits_{p} e^{\frac{1}{p}}=e^{\sum\limits_{p}\frac{1}{p}}$$ or, we are forcing for $$\sum\limits_{p}\frac{1}{p} \geq \log{10}$$ But $$\sum\limits_{p\leq x}\frac{1}{p}\geq \log{\log{(x+1)}}-\log{\frac{\pi^2}{6}}$$ then forcing further for $$\log{\log{(x+1)}} \geq\log{10}+ \log{\frac{\pi^2}{6}} \iff\\ \log{(x+1)}\geq 10\cdot\frac{\pi^2}{6} \iff \\ x \geq e^{10\cdot\frac{\pi^2}{6}} -1=13927008.866545...$$ reveals we have to consider all the primes between $1$ and $13927009$.

---

The crude estimates above can be fine tuned further, given $$\lim _{x\to \infty }\left(\sum _{p\leq x}{\frac {1}{p}}-\log \log x\right)=M\approx 0.261497...$$ for sufficiently large $x$ $$\sum _{p\leq x}{\frac {1}{p}} > \log \log x + \frac{M}{2}$$ then $$x\geq e^{e^{\log{10} -\frac{M}{2}}}\approx 6466.46...$$