Solution:
Let $d = (m, n)$, the greatest common divisor of $m$ and $n$. Let $r = n/d$, $s = nhk - m/d$, where $h$ is any integer sufficiently large to ensure that $s > 0$. Now $rm + sn = mn/d + nnhk - mn/d = nnhk$, which is a multiple of $k$. If $e$ divides $r$, then it also divides $rdhk = nhk$. So if $e$ divides $r$ and $s$, then it also divides $s - nhk = -m/d$. But $n/d$ and $m/d$ are relatively prime, so $e$ must be $1$. Hence $r$ and $s$ are relatively prime.