 Solution

Euler's totient function isEuler's theorem states that $\gcd (a,n)=1$ implies $\boxed{a^{\phi (n)}\equiv 1(\mathrm{mod}n)}$. For $n>1$, let $r_1,\dots ,r_{\phi (n)}$ be the invertible residue classes modulo $n$. Multiplication by $a$ permutes these classes, since it has an inverse modulo $n$. Multiplying the resulting congruences givesEvery factor is a unit, so the product can be cancelled, proving the theorem. The case $n=1$ is immediate. For distinct prime numbers $p,q$, removing multiples of either prime from $1,\dots ,pq$ gives

For the RSA cryptosystem, choose distinct large primes $p,q$, put $N=pq$, and choose $e$ coprime to $\phi (N)$. Compute $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. The public key is $(N,e)$; the private exponent $d$ is retained secretly. Represent a message by $0\le m<N$, encrypt by $c\equiv m^e(\mathrm{mod}N)$, and decrypt by $m^{\prime }\equiv c^d(\mathrm{mod}N)$.

To prove correct decryption even for messages not coprime to $N$, write $ed=1+k(p-1)(q-1)$. Modulo $p$, if $p\mid m$ then $m^{ed}\equiv m\equiv 0$; otherwise Fermat's little theorem gives $m^{ed}\equiv m$. The same reasoning holds modulo $q$. The Chinese remainder theorem therefore gives $m^{ed}\equiv m(\mathrm{mod}N)$, and the chosen representative recovers $m$. Thus decryption works for every message residue, not merely the units.