Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 1 / 1I (Number Theory)

The Chinese remainder theorem says that if the positive integers $m_1,\dots ,m_r$ are pairwise coprime and $M={\prod }_i{m}_i$, then for arbitrary residue classes $a_i(\mathrm{mod}{m}_i)$ there is a unique residue class $x(\mathrm{mod}M)$ satisfyingEquivalently, reduction is a ring isomorphism

For existence, put $M_i=M/m_i$. Pairwise coprimality gives $\gcd (M_i,m_i)=1$, so Bézout's identity supplies an integer $u_i$ with $u_i{M}_i\equiv 1(\mathrm{mod}{m}_i)$. Thenhas the required residues, because every term except the $i$th is divisible by $m_i$. If $x$ and $y$ are two solutions, each $m_i$ divides $x-y$. Pairwise coprimality then implies that their product $M$ divides $x-y$, proving uniqueness modulo $M$.

An odd composite number $N$ with $\gcd (b,N)=1$ is a Fermat pseudoprime to base $b$ whenFor $N=35$, the Chinese remainder theorem for unit groups reduces this condition to congruences modulo $5$ and $7$. Modulo $5$, Fermat's little theorem givesso $b^{34}\equiv 1(\mathrm{mod}5)$ exactly when $b\equiv \pm 1(\mathrm{mod}5)$. Modulo $7$, the unit group has order $6$, soThe equation $b^4=1$ in the cyclic group $(\mathbb{Z}/7\mathbb{Z}{)}^{\times }$ has $\gcd (4,6)=2$ solutions, namely $b\equiv \pm 1(\mathrm{mod}7)$.

Combining the two independent sign choices by the Chinese remainder theorem givesand hence