I think the bound on n for part a is wrong... Through brute force checking, there seems to be no solution for n=53. However, here is a solution for part b: Assume that $ q_1,q_2,...,q_m$ are all of the distinct primes dividing an integer $ a$. Then \begin{align*} \phi(a)&=a\left(\frac{q_1-1}{q_1}\right)\left(\frac{q_2-1}{q_2}\right)\cdots\left(\frac{q_m-1}{q_m}\right)\\ \frac{\phi(a)}{a}&=\left(\frac{q_1-1}{q_1}\right)\left(\frac{q_2-1}{q_2}\right)\cdots\left(\frac{q_m-1}{q_m}\right) \end{align*} For $ n=5$ or $ 6$ we can take $ (a,b)=(2,3)$ or $ (3,3)$ respectively, since \[ \frac{\phi(2)}{2}+\frac{\phi(3)}{3}=\frac{1}{2}+\frac{2}{3}=\frac{7}{6}>1\\ \frac{\phi(3)}{3}+\frac{\phi(3)}{3}=\frac{2}{3}+\frac{2}{3}=\frac{4}{3}>1\] Now suppose $ n\ge 7$. Let $ p_1,p_2,...$ be all of the primes listed in increasing order, and say that $ a=p_t$ is the largest prime less than $ n-1$ and $ b=n-a$. We can do this since $ a$ which is a prime must be greater than $ 1$ and $ b=n-a>n-(n-1)=1$. Any factor of $ \phi(b)$ of the form $ \left(\frac{q_i-1}{q_i}\right)<1$ will decrease $ \phi(b)$, so $ \phi(b)$ is lowest if all primes less than or equal to $ p_t$ divide $ b$, so \[ \frac{\phi(b)}{b}\ge\prod_{i=1}^{t}\left(\frac{p_i-1}{p_i}\right)>\prod_{i=2}^{p_t}\left(\frac{i-1}{i}\right)=\frac{1}{p_t}=\frac{1}{a}\] The inequality is strict because we insert the factor of $ \frac{4-1}{4}$ (Since $ n\ge 7$, we have $ p_t\ge 5$ so $ p_t>4$). And of course, as $ a$ is prime, $ \frac{\phi(a)}{a}=\frac{a-1}{a}$. Then \[ \frac{\phi(a)}{a}+\frac{\phi(b)}{b}>\frac{a-1}{a}+\frac{1}{a}=1\].

tjhance wrote: I think the bound on n for part a is wrong... Through brute force checking, there seems to be no solution for n=53. Indeed, and it's wrong for 79 as well, and possibly for higher values too. Hojoo, could you check the problem statement?

I think it should work for n>79, based on a computer program I wrote. I think I can prove it easily for n>181, and I'm close to the rest.

Here, I will just post my solution assuming it is n>79. If $ p_1,p_2,...,p_m$ are distinct primes dividing $ a$, then $ \frac{\phi(a)}{a}$ is at most $ \left(\frac{p_1-1}{p_1}\right)\left(\frac{p_2-1}{p_2}\right)\cdots\left(\frac{p_m-1}{p_m}\right).$ If $ n$ is even and greater than $ 79$ then we can set $ a=6$ and $ b=n-6$. $ b$ is even, so $ \frac{\phi(b)}{b}\le \frac{1}{2}$, and $ \frac{\phi(6)}{6}=\frac{1}{3}$, so \[ \frac{\phi(a)}{a}+\frac{\phi(b)}{b}\le\frac{1}{3}+\frac{1}{2}=\frac{5}{6}<1\] Now suppose $ n$ is odd and greater than or equal to $ 107$. Then we can pick $ a=105$ and $ b=n-105$. Again, $ b$ is even so $ \frac{\phi(b)}{b}\le \frac{1}{2}$. $ a=3\cdot 5\cdot 7$ so $ \frac{\phi(a)}{a}=\left(\frac{2}{3}\right)\left(\frac{4}{5}\right)\left(\frac{6}{7}\right)=\frac{16}{35}$. Then, \[ \frac{\phi(a)}{a}+\frac{\phi(b)}{b}\le\frac{16}{35}+\frac{1}{2}=\frac{67}{70}<1\] Now assume $ n$ is a multiple of $ 3$. Then $ n=3n'$ where $ n'>26$. Then $ n'$ can be expressed as the sum of positive multiples of $ 2$ and $ 5$; $ n'=2m_1+5m_2$. Then set $ a=6m_1$ and $ b=15m_2$ and we have \[ \frac{\phi(a)}{a}+\frac{\phi(b)}{b}\le\left(\frac{1}{2}\right)\left(\frac{2}{3}\right)+\left(\frac{2}{3}\right)\left(\frac{4}{5}\right)=\frac{13}{15}<1\] Now assume $ n$ is a multiple of $ 5$. Then $ n=5n'$ where $ n'>15$. Then $ n'$ can be expressed as the sum of positive multiples of $ 2$ and $ 3$; $ n'=2m_1+3m_2$. Then set $ a=10m_1$ and $ b=15m_2$ and we have \[ \frac{\phi(a)}{a}+\frac{\phi(b)}{b}\le\left(\frac{1}{2}\right)\left(\frac{4}{5}\right)+\left(\frac{2}{3}\right)\left(\frac{4}{5}\right)=\frac{14}{15}<1\] So now I have taken care of all $ n$ at least $ 107$, and all numbers below $ 107$ that are multiples of $ 2$, $ 3$, or $ 5$. This leaves only $ 83,89,91,97,101,$ and $ 103$. Because \[ \left(\frac{2}{3}\right)\left(\frac{6}{7}\right)+\left(\frac{1}{2}\right)\left(\frac{4}{5}\right)=\frac{34}{35}<1\\ \left(\frac{2}{3}\right)\left(\frac{4}{5}\right)+\left(\frac{1}{2}\right)\left(\frac{6}{7}\right)=\frac{101}{105}<1\\ \left(\frac{2}{3}\right)\left(\frac{4}{5}\right)+\left(\frac{1}{2}\right)\left(\frac{10}{11}\right)=\frac{163}{165}<1\] $ a$ and $ b$ will always work if $ a=21m_1,b=10m_2$ or $ a=15m_1,b=14m_2$ or $ a=15m_1,b=22m_2$. \[ 83=3\cdot 21+2\cdot 10\\ 89=5\cdot 15+1\cdot 14\\ 91=1\cdot 21+7\cdot 10\\ 97=5\cdot 15+2\cdot 11\\ 101=1\cdot 21+8\cdot 10\\ 103=3\cdot 21+4\cdot 10\] Thus the statement is valid for all $ n>79$.