Originally Posted by

**demode** Suppose we have a huge number $\displaystyle n$ (in this case $\displaystyle n =20800309729538371074209$). We know that $\displaystyle n = pq$, where $\displaystyle p$ and $\displaystyle q$ are *distinct* primes. We also know that

$\displaystyle \phi(n)=20800309725991259351316$

How can we factorise $\displaystyle n$ using only the given information?

__Attempt:__

So, here's the equation for Euler's totient function of n to realate all we know:

$\displaystyle \phi(n)=n \left(1 - \frac{1}{p} \right) \left(1 - \frac{1}{q} \right)$

I rearranged it to:

$\displaystyle \phi(n) . n = \left(1 - \frac{1}{p} \right) \left(1 - \frac{1}{q} \right)$

I'm stuck here. What can I do after that to find out $\displaystyle p$ and $\displaystyle q$?