Prove RSA formula to be correct

Question

How can I mathematically prove that if:

n = pq

then

$\phi$(n) = n + 1 - (p + q)

I could prove it ofcourse with an example, but I'm sure there must be a better way.

Any help would be appreciated

Answer 1

Well since $p$ and $q$ are prime, then by definition of totien function, we have

$$\phi(n) = \phi(pq) = (p - 1)(q - 1) = pq - p - q + 1 = n + 1 - (p + q) $$

Answer 2

The totient function is (weakly) multiplicative. If $a$ and $b$ are relatively prime, then $\phi(ab) = \phi(a)\phi(b)$. Also, $\phi(p) = p - 1$ if $p$ is prime. That should give you the result.

Proving this is somewhat harder. The $\phi(p) = p - 1$ is easy, but proving multiplicativity is harder. Hopefully this will get you started (there's a lot of proofs, with varying assumptions).