RSA: Why must e be relative prime to phi(n)
Because RSA takes advantage of the fact that:

$a^{\phi(n)} \equiv 1 \mod n$

Which means:

$a^{\phi(n)+1} \equiv a \mod n$

So, in order to encrypt and decrypt using $e$ and $d$, we need:

$ed \equiv 1 \mod \phi(n)$

Which can only be true if $gcd(e,\phi(n)) = gcd(d,\phi(n)) = 1$