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))$.
$\Phi(n)$ is related to the prime factors of $n$ because (exercise: prove this) $$\Phi(n) = n(1 - 1/p_1)(1 - 1/p_2)\dotsm (1 - 1/p_k)$$ where $n = p_1^{a_1}p_2^{a_2}\dotsm p_k^{a_k}$. Even if there are reciprocals of primes, the product works out to be an integer.
Since you know that $n = 110179 = pq$, you also know that $\Phi(110179) = 110179(1 - 1/p)(1 - 1/q)$ and this is given to be $109480$. Simplifying a little, we have $$\frac{109480}{110179} = 1 - \frac{1}{p} - \frac{1}{q} + \frac{1}{pq} \\ \implies 109480 - 110179 = 1 - (p + q) \\ \implies p + q = 700$$
Now that you have the sum and the product of $p$ and $q$, working out the values is solving a simple quadratic, giving $p = 239$ and $q = 461$.