Past exam of the options II course of the University of Oxford / 2006 / C / 2

A primitive root modulo $p$ is an integer whose residue generates the multiplicative group ${\mathbb{F}}_p^{\times }$, equivalently has order $p-1$.

The Chinese remainder theorem states that, for pairwise coprime positive integers $m_1,\dots ,m_r$, the system $x\equiv a_i(\mathrm{mod}{m}_i)$ has a unique solution modulo $M={\prod }_i{m}_i$. For a constructive proof put $M_i=M/m_i$. Bézout's identity gives an integer $u_i$ with $M_i{u}_i\equiv 1(\mathrm{mod}{m}_i)$. Then $x={\sum }_i{a}_i{M}_i{u}_i$ has all the required residues. If two solutions exist, their difference is divisible by every $m_i$; pairwise coprimality makes it divisible by their product, proving uniqueness modulo $M$.

Here $3,5,7$ divide $p-1$, and none is zero modulo $p$. Choose a primitive root $g$ and exponents $a,b,c$ withUse the theorem with moduli $3,5,7$ to choose $r$ such that $r\equiv a(\mathrm{mod}3)$, $r\equiv b(\mathrm{mod}5)$, $r\equiv c(\mathrm{mod}7)$. Define nonzero residuesThe exponents are integers; negative ones are interpreted using inverses in ${\mathbb{F}}_p^{\times }$. Taking integer representatives now givesThe theorem aligns the exponent modular congruences, which is why a primitive root converts the three power conditions into a linear modular congruence problem.