| | |
Claim: If $n = pq$, where $p$ and $q$ are primes, then determining the value of $\phi(n)$ leads directly to a way to factor $n$. In this way, determining $\phi(n)$ is at least as hard as 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$$