Past exam of the mathematics course of the University of Cambridge / 2020 / ia / Paper 2 / 7D (Numbers and Sets)

The Euler totient function $\varphi (n)$ is the number of residue classes modulo $n$ that are coprime to $n$. The Chinese remainder theorem says that for pairwise coprime moduli $m_i$, reduction induces a bijectionIt restricts to a bijection of unit groups. If $n=p_1\cdots p_r$ is squarefree, thenEach of the primes $3,5,17,257$ is one more than a power of two, so every squarefree product of them has power-of-two totient. Ten odd examples are

The Fermat-Euler theorem states that if $\gcd (a,n)=1$, thenLet $r_1,\dots ,r_{\varphi (n)}$ be a reduced residue system modulo $n$. Multiplication by $a$ permutes these classes, because $a{r}_i\equiv a{r}_j(\mathrm{mod}n)$ implies $r_i\equiv r_j(\mathrm{mod}n)$. HenceEvery $r_i$ is invertible modulo $n$, so cancellation gives $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$.

In the RSA cryptosystem, choose distinct large primes $p,q$, put $N=pq$, and choose $e$ coprime toThe decryption exponent is the modular multiplicative inverseThus $ed=1+k\varphi (N)$. For a message with $\gcd (m,N)=1$, the Fermat-Euler theorem givesFor $N=187=11\cdot 17$, $\varphi (N)=160$. The extended Euclidean algorithm givesso