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))$.

  • 3
    $\begingroup$ I guess you know that $\phi(n)=(p-1)(q-1)$. Together with $n=pq$ you have two equations for $p,q$. You can setup a quadratic equation for either $p$ or $q$, e.g. $$p^2 - (n + 1 - \phi(n))p + n = 0$$ $\endgroup$ – gammatester May 19 '16 at 6:56
  • $\begingroup$ @gammatester true I get it .But is $\phi(n)$ related with factorization of $n$ in a general scheme? $\endgroup$ – Love Everything May 19 '16 at 7:02
  • $\begingroup$ If you have the factorization of $n$ you can compute $\phi(n)$. The other way around (computing $\phi(n)$ without factorization) is 'hard', it is for example essential for the security of the RSA crypto system. $\endgroup$ – gammatester May 19 '16 at 7:06

$\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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.