Question: Suppose that n is the product of distinct primes p and q, so n=pq
Show that p and q are the roots of the quadratic equation
x^2 -(n+1 -φ(n))x + n
Hence if n and φ(n) are known then n can be easily factored.
So far I know that φ(n)=(p-1)(q-1) and that φ(n)= #{1≤x≤n : gcd(x,n)=1}
Any guidance on how to proceed to start generating this quadratic would be greatly appreciated!
In general, when $A,B$ are the roots of $x^2 + ax + b = 0$, we know that $(x-A)(x-B) = x^2 + ax + b$, and so $x^2 - (A+B)x + AB = x^2 + ax + b$ (for all $x$), so that $a = -(A + B), b = AB$, or $A+B = -a, AB = b$. So the coefficients of the quadratic are just the negative sum of the roots, and their product respectively.
When $n = pq$, we know that $\phi(n) = (p-1)(q-1) = pq - (p+q) + 1 = n - (p+q) + 1$. Hence $p+q = n - \phi(n) + 1$, and so we know that $p,q$ are the roots of $x^2 - (p+q) + pq = x^2 - (n + 1 - \phi(n)) + n$.