## Finding Phi is Equivalent to Factoring

*Claim: If $n = pq$, where $p$ and $q$ are primes, then knowledge of $\phi(n)$ is equivalent to factoring $n$.*

*Proof:*

Certainly, if we can discover $p$ and $q$ by factoring $n$, then we can evaluate $\phi(n)$ using its multiplicative property:
$$\phi(n) = (p-1)(q-1)$$

On the flip side, suppose $\phi(n)$ is known. Then we can find $p$ and $q$, thus factoring $n$, in the following way:

Note that
$$\begin{array}{rcl}
\phi(n) &=& (p-1)(q-1)\\
&=& pq - p - q + 1\\
&=& n - (p+q) + 1\\
\end{array}$$
So,
$$p+q = n - \phi(n) + 1$$
However, we also know that
$$pq = n$$
The latter we can solve for $q$ and substitute into the first to find
$$p + n/p = n - \phi(n) + 1$$
Clearing the fractions by multiplying by $p$, we discover a quadratic in $p$
$$p^2 + n = (n-\phi(n)+1)p$$
or equivalently
$$p^2 - (n-\phi(n)+1)p + n = 0$$
We can apply the quadratic formula to find $p$ and $q$:
$$p = \frac{(n-\phi(n)+1) \pm \sqrt{(n-\phi(n)+1)^2-4n}}{2}$$
$$q = n/p$$