Solving $\phi (n) < (n-1) \cdot \frac{15499}{94744} $

Question

I am working on challenge 243 from Project Euler (PE 243). The question is:

$$\text{Solve } \phi (n) < (n-1)\cdot \frac{15499}{94744}$$

I can calculate $\phi(n)$ for any $n$, but I think the $n$ which solves the problem is larger than the range I can brute force. I have never before worked with $\phi(n)$ before, but I'd love to learn how to solve this kind of problem.

Research on Google gave me definitions of $\phi(n)$, which I already know, but nothing to help me solve the problem. If you could give me any tips in the right direction, and NOT the answer. Thanks in advance.

---

Edit: I found a clue: $\phi(n) \ge \sqrt{n}$ This should give me a limit where $n$ will always give me a number larger than the desired result. I'm working on it.

Answer 1

Some information that may be useful: Let $n$ have prime power decomposition $$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},$$ where the $p_i$ are distinct primes. Then $$\varphi(n)=(p_1-1)p_1^{a_1-1}(p_2-1)p_2^{a_2-1}\cdots (p_k-1)p_k^{a_k-1}.$$ (For details about the $\varphi$-function, see this.) By using the above formula for $\varphi(n)$, we can see that $$\frac{\varphi(n)}{n-1}=\frac{n}{n-1}\frac{\varphi(n)}{n}=\frac{n}{n-1}\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_k}\right).$$ So to make $\varphi/(n-1)$ smallish "cheaply" it is good to use small primes, all to the first power. Decorating the primes with powers $a_i$ greater than $1$ has only a minor effect on the ratio.

Answer 2

For $$\displaystyle n=\prod p_i^{e_i}$$

we have that $$\phi(n)=n\prod \left(1-\frac1 p_i\right)$$

so to get small $\dfrac{\phi(n)}n$ you want lots of small prime factors, $n=2\cdot3\cdot5\cdots$