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

Fermat's little theorem states that for a prime $p$ and an integer $a$,Wilson theorem states that for a prime $p$,All the following modular congruences are taken modulo the indicated prime.

Suppose $x^2\equiv -1(\mathrm{mod}p)$. Then $p\nmid x$, so Fermat's little theorem gives $x^{p-1}\equiv 1$. But $p\equiv 3(\mathrm{mod}4)$ makes $(p-1)/2$ odd, and henceSince this $p$ is odd, $1\not\equiv -1(\mathrm{mod}p)$, a contradiction. There is no square root of minus one in this case.

Set $m=(p-1)/2$. Pairing each of $1,\dots ,m$ with its negative residue givesHere $p\equiv 1(\mathrm{mod}4)$ makes $m$ even. By Wilson theorem,satisfies $x^2\equiv -1(\mathrm{mod}p)$. Its negative is the other root. This proves existence by an explicit factorial construction.

Write $p=3k+2$. A solution has $p\nmid x$, so Fermat's little theorem givesThus $x\equiv (-1{)}^k(\mathrm{mod}p)$. If $p$ is odd, then $k$ is odd and $x\equiv -1$. The remaining prime case $p=2$ has $k=0$ and $x\equiv 1\equiv -1(\mathrm{mod}2)$ as well. Since $-1$ itself always satisfies the equation, the unique solution is $x\equiv -1(\mathrm{mod}p)$.

Factor the equation asFor the nontrivial roots, the quadratic formula over residues givesThe supplied square root is $14$, and $2^{-1}\equiv 100(\mathrm{mod}199)$. ThereforeIndeed $107^2-107+1=11343=57\cdot 199$, so $107^3+1$ is divisible by $199$, and $107\not\equiv -1$. The other nontrivial root is $(1-14)100\equiv 93$; it satisfies $93^2-93+1=43\cdot 199$. Together with $198\equiv -1$, these are the three cube roots of minus one. The complex-number hint reflects the same quadratic factor: the two roots there are $(1\pm \sqrt{-3})/2$.