In an entrance test for admission into an undergraduate course in mathematics the following question was asked.
Consider the number $110179$ this number can be expressed as a product of two distinct prime numbers $p$ and $q$, also The number of integers less than it and relatively prime to it are $109480$. Find the value of $p+q$ and also mention the values of $p$ and $q$ in your answer.
What I knew- I knew that the number of integers less than $n$ and relatively prime to it is $\phi(n)$ called the Euler's totient function and the fact that it is multiplicative.
What I want to know- How is this $ \phi(n)$ has anything to do with factoring $n$?. And also ofcourse the solution of the problem using mathematics.(I wrote a piece of code to find out the factors but ofcourse without $\phi(110179))$.