Factoring $n$ when $\phi(n)$ is given? I am stuck on a problem where I am given the value of $\phi(n)=31615577098574867424$ for $n=pq=31615577110997599711$ where $p$ and $q$ are prime numbers. Now, I need to find the values of $p$ and $q$ but I am not able to get an idea as to how I can solve it. I know that $\phi(n)$ gives the number of relative prime to a given number $n$ but I can use Euler-totient function to factorize $n$?
 A: When $\phi(n)$ is given when $n=pq$ where $p$ and $q$ are prime numbers, then we have 
$\phi(n)=(p-1)(q-1)=pq-(p+q)+1$
But $pq=n$, therefore , $\phi(n)=n-(p+q)+1$ and $p+q=n+1-\phi(n)$.
Now, $p$ and $q$ are the roots of the equation, $x^2-(p+q)x+pq=(x-p)(x-q)$.
Substituting for $p+q$,
$x^2-(n+1-\phi(n))x+n$
$=x^2-(31615577110997599711+1-31615577098574867424)x+31615577110997599711$
$=(x-3572144239)(x-8850588049)$
Therefore, $31615577110997599711=3572144239.8850588049$
A: Note that if $n = pq$, with $p \ne q$ prime, we have 
$$ \phi(n) = (p-1)(q-1) = n - p - q + 1 = (n+1)-(p+q)$$
so you know $n = pq$ and $p+q = n+1 - \phi(n)$. If this doesn't give you primes $p$ and $q$, you need to consider the case $p = q$, that is $n = p^2$. Here we have
 $$ \phi(n) = p(p-1) = n - p $$
so in that case $p = q = n -\phi(n)$.
A: Since $\phi(n) = n + 1 - (p+q)$ as mentioned by Will Jagy in the comments, consider the polynomial $$(x-p)(x-q) = x^2 - (p+q)x + pq = x^2 - (n + 1 - \phi(n)) x + n.$$
As you know the coefficients of the polynomial on the right hand side, can you use this to find $p,q$?
