Past exam of the mathematics course of the University of Cambridge / 2025 / ia / Paper 4 / 6E (Numbers and Sets)

For pairwise coprime positive integers $n_i$, every system $x\equiv a_i(\mathrm{mod}{n}_i)$ has a unique solution modulo ${\prod }_i{n}_i$.

Euler's totient is $\varphi (n)=|\{1\le a\le n:(a,n)=1\}|$, equivalently the number of units modulo $n$.

If $(a,n)=1$, then $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$.

The Chinese remainder isomorphism $\mathbb{Z}/(nm)\cong \mathbb{Z}/n\times \mathbb{Z}/m$ restricts to a bijection on units. Counting those units gives $\varphi (nm)=\varphi (n)\varphi (m)$.

Write squarefree $n=\prod p$. For each $p\mid n$, either $p\mid a$, when both sides vanish modulo $p$, or Fermat's theorem applies. Since $p-1\mid \varphi (n)$ and $k\equiv 1(\mathrm{mod}\varphi (n))$, it gives $a^k\equiv a(\mathrm{mod}p)$. The Chinese remainder theorem combines these congruences to give $a^k\equiv a(\mathrm{mod}n)$.

RSA chooses $n=pq$ and exponents $e,d$ with $ed\equiv 1(\mathrm{mod}\varphi (n))$. The public key is $(n,e)$, encryption is $c\equiv m^e(\mathrm{mod}n)$, and the secret exponent decrypts via $c^d\equiv m(\mathrm{mod}n)$. Security relies on the difficulty of recovering $\varphi (n)$ from a large unfactored $n$.

Choose a prime with $p^2\mid n$, and set $a=0$, $b=n/p$. Then $b\not\equiv 0(\mathrm{mod}n)$, but $b^2=n^2/p^2$ is divisible by $n$. Therefore $a^k\equiv b^k\equiv 0(\mathrm{mod}n)$ for every $k>1$.