= Solution
<Euler's totient function> is
$$
\varphi(n)=\#\{1\leq r\leq n:\gcd(r,n)=1\},\qquad n\geq1.
$$
<Euler's theorem> states that $\gcd(a,n)=1$ implies $\boxed{a^{\varphi(n)}\equiv1\pmod n}$. For $n>1$, let $r_1,\ldots,r_{\varphi(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 gives
$$
a^{\varphi(n)}r_1\cdots r_{\varphi(n)}\equiv r_1\cdots r_{\varphi(n)}\pmod n.
$$
Every 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,\ldots,pq$ gives
$$
\boxed{\varphi(pq)=pq-q-p+1=(p-1)(q-1).}
$$
For the <RSA cryptosystem>, choose distinct large primes $p,q$, put $N=pq$, and choose $e$ coprime to $\varphi(N)$. Compute $d$ with $ed\equiv1\pmod{\varphi(N)}$. The public key is $(N,e)$; the private exponent $d$ is retained secretly. Represent a message by $0\leq m<N$, encrypt by $c\equiv m^e\pmod N$, and decrypt by $m'\equiv c^d\pmod 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\equiv0$; 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\pmod N$, and the chosen representative recovers $m$. Thus \b[decryption works for every message residue], not merely the units.
Back to article page
